реверсирование списка в OCaml с использованием fold_left / right - PullRequest
Новая
       95

реверсирование списка в OCaml с использованием fold_left / right

4 голосов
/ 12 сентября 2011

ОБНОВЛЕНИЕ - Решение

Спасибо jacobm за помощь, я нашел решение.

// Folding Recursion
let reverse_list_3 theList = 
    List.fold_left (fun element recursive_call -> recursive_call::element) [] theList;;

Я изучаю различные способы рекурсии в OCaml (для класса) и для некоторого упражнения я пишу функцию для реверса списка с использованием различных стилей рекурсии. 

// Forward Recursion
let rec reverse_list_forward theList =
    match theList with [] -> [] | (head::tail) -> (reverse_list_1 tail) @ [head];;

// Tail Recursion
let rec reverse_list_tail theList result =
    match theList with [] -> result | (head::tail) -> reverse_list_2 tail (head::result);;

Теперь я пытаюсь написать обратную функцию, используя List.fold_left, но я застрял и не могу понять это.Как бы я написал эту обратную функцию, используя свертывание?

Кроме того, если у кого-то есть хорошие ссылки на функциональное программирование, будут приветствоваться ссылки на различные типы рекурсии, функции высшего порядка и т. Д.:)

Ответы [ 2 ]

8 голосов
/ 12 сентября 2011

Я считаю полезным рассматривать операции сгиба как обобщение того, что делать с последовательностью операций 

a + b + c + d + e

fold_right (+) 0 применяет операцию + вправо-ассоциативно, используя 0 в качестве базового варианта: 

(a + (b + (c + (d + (e + 0)))))

fold_left 0 (+) применяет его левоассоциативно: 

(((((0 + a) + b) + c) + d) + e)

Теперь рассмотрим, что произойдет, если вы замените + на :: и 0 с [] в правом и левом сгибах.

Может быть также полезно подумать о том, как fold_left и fold_right работают как "замена" :: и[] операторов в списке.Например, список [1,2,3,4,5] - это просто сокращение для 1::(2::(3::(4::(5::[])))).Может быть полезно думать о fold_right op base как о том, что он позволяет "заменить" :: на op и [] на base: например, 

fold_right (+) 0 1::(2::(3::(4::(5::[]))))

становится 

1 + (2 + (3 + (4 + (5 + 0))))

:: стало +, [] стало 0.С этой точки зрения легко увидеть, что fold_right (::) [] просто возвращает вам ваш первоначальный список.fold_left base op делает что-то немного страннее: он переписывает все скобки вокруг списка, чтобы переместиться в другом направлении, перемещается [] из задней части списка вперед, а , а затем заменяет :: наop и [] с base.Так, например: 

fold_left 0 (+) 1::(2::(3::(4::(5::[]))))

становится 

(((((0 + 1) + 2) + 3) + 4) + 5)

С + и 0, fold_left и fold_right дают одинаковый результат.Но в других случаях это не так: например, если вместо + вы использовали -, результаты будут другими: 1 - (2 - (3 - (4 - (5 - 0)))) = 3,но ((((((0 - 1) - 2) - 3) - 4) - 5) = -15.

0 голосов
/ 06 октября 2015 
let rev =
  List.fold_left ( fun lrev b ->
    b::lrev
  ) [];;

тест: 

# rev [1;2;3;4];;
- : int list = [4; 3; 2; 1]
...