[Caml-list] List.fold_left vs. Hashtbl.fold

[Gabriel Scherer <gabriel.scherer@gmail.com>]

(Sorry for duplicate send.)

There are two exported way to fold over lists:
  fold_left : ('acc -> 'e -> 'acc) -> ('acc -> 'e list -> 'acc)
  fold_right : ('e -> 'acc -> 'acc) -> ('e list -> 'acc -> 'acc)

The _left and _right suffixes indicate whether the "accumulator"
argument (the partial result of what has been folded so far) is passed
as the left or the right parameter of the function argument: ('acc ->
'e -> 'acc) for left, ('e -> 'acc -> 'acc) for right. The return type
of fold then lifts this argument type from processing an element to
processing the whole list: the initial 'acc value for is passed "on
the left" for fold_left (before the list argument), "on the right" for
fold_right (after the list argument).

That's for the type. Regarding the implementation, fold_left applies
the argument function starting from "the left" (the beginning) of the
list first, while fold_right begins "on the right" (at the end): for
some infix operator (++) :
  fold_left (++) init [x; y; z]     is  ((init ++ x) ++ y) ++ z
  fold_right (++) [x; y; z] init   is (x ++ (y ++ (z ++ init)))
(The evaluation "begins" in the innermost nested parentheses)

Those two iterations techniques are available for linear data
structures (those that essentially look like lists). For more general
algebraic datatypes there is a canonical "folding" method, that
happens to coincide with fold_right on lists. The reason why
fold_right is "canonical" is that it turns the list
  x :: (y :: (z :: []))
into
  (x ++ (y ++ (z ++ init)))
replacing each constructor with a passed-in operator.

This means that fold_left may not exist for arbitrary data structure
(think of binary trees), while fold_right is rather universal. Other
folding functions in the standard library (in Set and Map in
particular, but in Hashtbl as well) have therefore taken inspiration
from the fold_right structure, rather than fold_left.

On Wed, Nov 28, 2012 at 5:40 AM, William Smith <bills@wwayneb.com> wrote:
>
> Hashtbl.fold expects the Hasthbl as the second parameter with the 3rd
> parameter being the initial value... just the opposite of List.fold_left.