更新 - 解决方案
感谢 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
编写一个反向函数,但我陷入困境并且无法弄清楚。我如何使用折叠来编写这个反向函数?
此外,如果有人对函数式编程、不同类型的递归、高阶函数等有很好的引用,我们将不胜感激:)
最佳答案
我发现将折叠操作视为对一系列操作进行操作的概括很有帮助
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。
关于recursion - 使用fold_left/right反转OCaml中的列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7382140/