使用fold_left/right反转OCaml中的列表

Question

更新 - 解决方案

感谢 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 编写一个反向函数，但我陷入困境并且无法弄清楚。我如何使用折叠来编写这个反向函数？

另外，如果有人对函数式编程、不同类型的递归、高阶函数等有很好的参考，链接将不胜感激:)

Answer 1

我发现将折叠操作视为对一系列操作的概括是有帮助的

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 做了一些有点奇怪的事情：它重写列表周围的所有括号以向另一个方向移动，将 [] 从列表的后面移动到前面， then 将 :: 替换为 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。

Answer 2

let rev =
  List.fold_left ( fun lrev b ->
    b::lrev
  ) [];;

测试：

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