The puzzle is to express fold_left entirely in terms of fold_right. For example, an attempted solution like
let fold_left f e s = List.rev (fold_right (fun a acc -> f acc a) e (List.rev s))is inadmissible because it relies on
List.rev and thus is not entirely in terms of fold_right.
Recall that given a function $f$, a seed $e$ and a list $[a_{1}; a_{2}; \cdots; a_{N}]$, fold_left computes $f\;(\cdots f\;(f\;e\;a_{1})\;a_{2}\;\cdots)\;a_{N}$ whereas fold_right computes $f\;a_{1}\;(f\;a_{2}\;(\cdots\;(f\;a_{N}\;e)\cdots))$. There's really no choice but to delay computation and the expression that solves this problem is this.
let fold_left f e s = List.fold_right (fun a acc -> fun x -> acc (f x a)) s (fun x -> x) e
For example, in the top-level
# fold_left (fun acc x -> x * x :: acc) [] [1; 2; 3;] ;; - : int list = [9; 4; 1]
To see how this works, consider the right fold over the list $[a_{1}; a_{2}; a_{3}]$ (say)
- On encountering $a_{3}$ we compute $f_{3} = \lambda x_{3} . i\; (f\;x_{3}\;a_{3})$;
- On encountering $a_{2}$ we compute $f_{2} = \lambda x_{2} . f_{3}\;(f\;x_{2}\;a_{2})$;
- On encountering $a_{1}$ we compute $f_{1} = \lambda x_{1} . f_{2}\;(f\;x_{1}\;a_{1})$;
