Как сделать неубывающий список списков из одного списка? Без использования рекурсии, используя fold_left/fold_right. OCaml

Question

Это моя идея вопроса, но я не могу правильно набрать 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.

Answer 1

Для построения списка с использованием 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
    []

Опять же, мы строим список справа налево, но на этот раз мы должны решить, к какому из двух списков мы добавим новый элемент. Либо мы добавляем его в начало внешнего списка, либо добавляем новый список, содержащий только текущий элемент, в начало внешнего списка.