OCaml: fold_left, fold_right conversion

Question

In http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html, we have:

val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

List.fold_left f a [b1; ...; bn] is f (... (f (f a b1) b2) ...) bn.

val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b

List.fold_right f [a1; ...; an] b is f a1 (f a2 (... (f an b) ...)). Not tail-recursive.

The question is how to implement "fold_left" function using the List.fold_right function. And this is the answer I found in the internet:

let rec my_fold_left f a l = List.fold_right (fun x g a -> g (f a x)) l (fun x -> x) a;;

val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

In the first time, I write:

let rec my_fold_left_old f a l = List.fold_right (fun x a -> f a x) l a;;

val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

the type check is right, but the my_fold_left_old is wrong because it scan the list from the last element to the first element.

Can anyone explain the function my_fold_left above, the List.fold_right can have only 3 arguments, but the my_fold_left above has 4 arguments?

Answer 1

It's currying. Essentially, List.fold_right has a type of ('a -> 'b -> 'b) -> 'a list -> 'b, and this definition uses that operation with a function type for 'b.

You can see how this can produce "four arguments" for List.fold_right if you substitute 'c -> 'd for 'b, skipping redundant parens:

('a -> 'c -> 'd -> ('c -> 'd)) -> 'a list -> 'c -> 'd

So the List.fold_right folds over the list to produce a function, which is applied to one argument to produce the final result. To make that clearer, let's rewrite it with a named temporary:

 let foldl f init list =
  let fold_result =
    List.fold_right
      (fun elt g acc -> g (f acc elt))
      list
      (fun x -> x) in
  fold_result init