-2

这是我对这个问题的想法，但我无法正确输入fold_left方法。

例子：

nonDecreasing[1;4;3;2;5;6] == [[1;4];[3];[2;5;6]] 

let nonDecreasing list = 
    match list with
    | [] -> help(a, b, c) = b
    | h::[] -> 2 (*I don't know, "2" is only to compile*)
    | h::t -> let help = List.fold_left (fun(prev, lFinal, lTemp) h -> if(h<List.hd(t)) then (List.hd(t), lFinal, h::lTemp) else (List.hd(t), lTemp@lFinal, h::lTemp)) (h, [], []) list ;;

I can't make it properly. I don't know what I do wrong with fold-left function.
4

1 回答 1

0

使用 fold 构建列表可能更容易使用fold_right，因为您只能有效地将元素添加到列表中，因此您应该从右侧开始构建列表，这就是这样fold_right做的。（您也可以使用fold_left，但您需要在附加步骤中反转列表或使用昂贵的列表连接。）

构建列表的更简单示例是fold_right构建从列表末尾开始的列表元素总和的列表，例如，sums [a; b; c]给出[a+b+c; b+c; c]。代码如下所示。

let sums = List.fold_right
  (fun x ys ->
    match ys with
      | [] -> [x]
      | hd :: tl -> (x + hd) :: ys)
  [1; 2; 3; 4; 5]
  []

内部函数所做的是获取已构建列表的第一个元素并将其添加到当前元素。（请记住，元素是从右到左访问的。）然后将总和添加到已经存在的列表的前面。

定义non_decresing函数的工作方式类似。但是，我们必须使用嵌套列表，这会使事情变得更加复杂。代码如下。

let non_decreasing xs =
  List.fold_right
    (fun x outer ->
      match outer with
      | [] -> [[x]]
      | outer_hd :: outer_tl ->
          if x <= List.hd outer_hd then
            (x :: outer_hd) :: outer_tl
          else
            [x] :: outer)
    xs
    []

同样，我们是从右到左构建列表，但是这次我们必须决定向两个列表中的哪一个添加新元素。要么将其添加到外部列表的头部，要么将仅包含当前元素的新列表添加到外部列表的开头。

于 2018-11-29T16:44:18.203 回答