使用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做一些事情有点怪异:它重写周围列表中的所有括号去另一个方向,移动[]从列表中的回前方,然后替换::用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.