使用fold_left / right反转OCaml中的列表 [英] reversing a list in OCaml using fold_left/right

问题描述

更新 - 解决方案

感谢jacobm的帮助，我想出了一个解决方案。

  //折叠递归
 let reverse_list_3 theList = 
 List.fold_left（fun元素recursive_call  - > recursive_call :: element）[] theList ;; 
  

---

我正在学习递归的不同方法在OCaml（用于类）和一些练习中，我正在编写一个函数来使用不同的递归样式来颠倒列表。

  //向前递归
 let rec reverse_list_forward theList = 
与[]  - >>匹配， [] | （head :: tail） - > （reverse_list_1尾巴）@ [head] ;; 
 
 //尾递归
 let rec reverse_list_tail theList结果= 
与[]  - >匹配，结果| （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 + 会发生什么情况在左右两边都有 [] ds。

---

考虑 fold_left 和 fold_right 作为替换 :: 和 [] 运算符列表中。例如， [1,2,3,4,5] 列表实际上只是 1的简写：：:( 2：:( 3： ：（4：:( 5 :: []））））。将 fold_right op base 看作是让你用 :: 可能很有用> op 和 [] with base ：例如

  fold_right（+）0 1：:( 2：:( 3 :: :( 4：:( 5 :: []））））
  

变成

  1 +（2 +（3 +（4 +（5 + 0））））
  

:: 变成 + ， [] 变成 0 。从这个角度来看，很容易看到 fold_right（：:) [] 只是让你回到原来的列表。 fold_left base op 做了一些小事：它重写列表中的所有圆括号以转向另一个方向，移动 [] ，然后用 op :: c>和 [] 与 base 。例如：

  fold_left 0（+）1：:( 2：:( 3：:( 4：:( 5 :: b 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 $ b  （（（（（0 + 1）+2）+ 3）+ 4）+ 5）
  

  > 
 
 
使用 + 和 0 ， fold_left 和 fold_right 产生相同的结果。但在其他情况下，情况并非如此：例如，如果使用  -  而不是 + ，结果将会不同： （（（（（（ -  1）-2）-3）-4）-5）=  -  15。 p> 
UPDATE - Solution

Thanks to jacobm for his help, I came up with a solution. 
// Folding Recursion
let reverse_list_3 theList = 
    List.fold_left (fun element recursive_call -> recursive_call::element) [] theList;;




I'm learning about the different ways of recursion in OCaml (for class) and for some exercise, I'm writing a function to reverse a list using different recursion styles.
// 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);;
Now, I'm trying to write a reverse function using List.fold_left but I'm stuck and can't figure it out. How would I write this reverse function using folding?

Also, if anyone has good references on functional programming, the different types of recursion, higher-order-functions, etc..., links would be greatly appreciated :)
解决方案
I find it helpful to think of the fold operations as a generalization of what to do with a sequence of operations
a + b + c + d + e
fold_right (+) 0 applies the + operation right-associatively, using 0 as a base case:
(a + (b + (c + (d + (e + 0)))))
fold_left 0 (+) applies it left-associatively:
(((((0 + a) + b) + c) + d) + e)
Now consider what happens if you replace + with :: and 0 with [] in both right- and left-folds.



It may also be useful to think about the way fold_left and fold_right work as "replacing" the :: and [] operators in a list. For instance, the list [1,2,3,4,5] is really just shorthand for 1::(2::(3::(4::(5::[])))). It may be useful to think of fold_right op base as letting you "replace" :: with op and [] with base: for instance 
fold_right (+) 0 1::(2::(3::(4::(5::[]))))
becomes
1 + (2 + (3 + (4 + (5 + 0))))
:: became +, [] became 0. From this perspective, it's easy to see that fold_right (::) [] just gives you back your original list. fold_left base op does something a bit weirder: it rewrites all the parentheses around the list to go the other direction, moves [] from the back of the list to the front, and then replaces :: with op and [] with base. So for instance:
fold_left 0 (+) 1::(2::(3::(4::(5::[]))))
becomes
(((((0 + 1) + 2) + 3) + 4) + 5)
With + and 0, fold_left and fold_right produce the same result. But in other cases, that's not so: for instance if instead of + you used - the results would be different: 1 - (2 - (3 - (4 - (5 - 0)))) = 3, but (((((0 - 1) - 2) - 3) - 4) - 5) = -15.

                        
这篇关于使用fold_left / right反转OCaml中的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！