Modifying a List in OCaml with fold_left / right

Question

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 am learning various recursion methods in OCaml (for a class) and for some exercises, I am writing a function to modify 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 the inverse function using List.fold_left , but I'm stuck and can't figure it out. How to write this inverse function using folding?

In addition, if anyone has good references to functional programming, various types of recursion, higher order functions, etc. will be welcomed :)

Answer 1

It’s useful for me to think about dropping operations as a generalization of what to do with a sequence of operations

 a + b + c + d + e 

fold_right (+) 0 applies the + operation correctly associatively, using 0 as the base case:

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

fold_left 0 (+) is applied left-associative:

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

Now consider what happens if you replace + with :: and 0 with [] both the right and left sides.

---

It may also be useful to think about how fold_left and fold_right work as “replacing” operators :: and [] in a list. For example, the list [1,2,3,4,5] really just shortened for 1::(2::(3::(4::(5::[])))) . It might be useful to think of fold_right op base as "replacing" :: with op and [] with base : for example

 fold_right (+) 0 1::(2::(3::(4::(5::[])))) 

becomes

 1 + (2 + (3 + (4 + (5 + 0)))) 

:: became + , [] became 0 . From this point of view it is easy to see that fold_right (::) [] just returns you the original list. fold_left base op does something a little fold_left base op : it rewrites all the parentheses around the list to go in the other direction, moves [] from the back of the list to the beginning, and then replaces :: with op and [] with base . For example:

 fold_left 0 (+) 1::(2::(3::(4::(5::[])))) 

becomes

 (((((0 + 1) + 2) + 3) + 4) + 5) 

With + and 0 , fold_left and fold_right you will get the same result. But in other cases, this is not so: for example, 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.

Answer 2

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

test:

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