4

更新 - 解决方案

感谢 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但我被卡住了，无法弄清楚。我将如何使用折叠来编写这个反向函数？

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

4

2 回答 2

8

我发现将折叠操作视为对如何处理一系列操作的概括很有帮助

a + b + c + d + e

fold_right (+) 0+以关联方式应用操作，0用作基本情况：

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

fold_left 0 (+)左关联地应用它：

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

现在考虑如果在左右折叠中替换+with::和0with会发生什么。[]

考虑“替换”列表中的和运算符的方式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。

于 2011-09-12T00:11:35.083 回答
0 
let rev =
  List.fold_left ( fun lrev b ->
    b::lrev
  ) [];;

测试：

# rev [1;2;3;4];;
- : int list = [4; 3; 2; 1]
于 2015-10-05T21:11:45.677 回答