OCaml 非递减列表，没有 List.function

Question

更新：我不能使用任何List.function的东西。

我是OCaml的新手，我正在学习这门课程，其中我应该从值列表中计算一个非递减值列表。

例如，我有一个列表 [1; 2; 3; 1; 2; 7; 6]

因此，接受列表的函数单声道返回以下内容：

# mono [1; 2; 3; 1; 2; 7; 6];;
- : int list = [1; 2; 3; 7]

我执行以下操作：

let rec calculateCheck value lst = (
    match lst with
     [] -> true
    | x :: xs -> (
        if (value < x) then
            false
        else
            calculateCheck value xs
    )
);;

let rec reverse_list lst = (
    match lst with
     [] -> []
    | x :: xs -> (
        reverse_list xs @ [x]
    )
);;
let shouldReverse = ref 1;; 
let cancelReverse somelist lst = (
    shouldReverse := 0;
    reverse_list lst
);;
let rec mono lst = (
    let somelist = ref lst in
        if (!shouldReverse = 1) then
            somelist := cancelReverse somelist lst
        else
            somelist := lst;
    match !somelist with
     [] -> []
    | x :: xs -> (
        if (calculateCheck x xs) then
            [x] @ mono xs
        else
            [] @ mono xs
    );
);;

问题？

1. 这只工作一次，因为应该反转。
2. 我无法反转该值; mono list应返回非递减列表。

问题？

1. 有什么简单的方法可以做到这一点吗？
2. 具体说明如何获取列表的子集。例如，对于 [1; 2; 3; 5; 6]，我希望 [1; 2; 3] 作为 5 的输出，以便我可以递归解决此问题。另一件事是，你可以有一个列表作为 [1; 2; 3; 5; 6; 5]：： 所以对于第二个 5，输出应该是 [1; 2; 3; 5; 6]。

有什么想法吗？

谢谢

Answer 1

解决这类问题的一个好方法是强迫自己在数学上正式表达你正在寻找的东西正确的方法。通过一些培训，这通常会让你接近您将编写的最终程序的描述。

我们正在尝试定义一个incr li包含li的严格递增子序列。正如杰弗里·斯科菲尔德(Jeffrey Scoffield(所问，您可能正在寻找长这样的子序列：这是一个有趣且不平凡的算法问题研究得很好，但鉴于您是初学者我想你的老师要求更简单的东西。这是我的更简单规格的建议：您正在寻找所有大于它们前面的所有元素的元素列表。

生成易于转动的数学定义的好方法进入算法是通过归纳推理：定义一个属性自然数P(n)根据前身P(n-1)，或定义给定列表中的属性与 1 列表中的此属性更少的元素。考虑您要定义incr [x1; x2; x3; x4] 。你可以用incr [x1; x2; x3]和x4来表达，也可以用x1和incr [x2; x3; x4]条款。

• incr [x1;x2;x3;x4]是incr[x1;x2;x3]，如果更大，则加x4比列表中它之前的所有元素，或者等效地，incr[x1;x2;x3]的最大元素

• incr [x1;x2;x3;x4]是所有元素incr[x2;x3;x4]小于 x1 已被移除(它们不大于全部元素(，并x1添加

这两个精确的定义当然可以推广到任何长度，他们给出了两种不同的方法来写incr.

(* `incr1` defines `incr [x1;x2;x3;x4]` from `incr [x1;x2;x3]`,
   keeping as intermediate values `subli` that corresponds to
   `incr [x1;x2;x3]` in reverse order, and `biggest` the biggest
   value encountered so far. *)
let incr1 li =
  let rec incr subli biggest = function
    | [] -> List.rev subli
    | h::t ->
      if h > biggest
      then incr (h::subli) h t
      else incr subli biggest t
  in
  match li with
    | [] -> []
    | h::t -> incr [h] h t
(* `incr2` defines `incr [x1;x2;x3;x4]` from `incr [x2;x3;x4]`; it
   needs no additional parameter as this is just a recursive call on
   the tail of the input list. *)
let rec incr2 = function
  | [] -> []
  | h::t ->
    (* to go from `incr [x2;x3;x4]` to `incr [x1;x2;x3;x4]`, one
       must remove all the elements of `incr [x2;x3;x4]` that are
       smaller than `x1`, then add `x1` to it *)
    let rec remove = function
      | [] -> []
      | h'::t ->
        if h >= h' then remove t
        else h'::t
    in h :: remove (incr2 t)