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

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

0 голосов
/ 21 ноября 2018

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

1 Ответ

0 голосов
/ 29 ноября 2018

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

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

...