reversing a list in OCaml using fold_left/right
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 r开发者_JS百科ec 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.
let rev =
List.fold_left ( fun lrev b ->
b::lrev
) [];;
test:
# rev [1;2;3;4];;
- : int list = [4; 3; 2; 1]
精彩评论