# Argument order: Why does `fold_left` take the accumulator before the collection, but `fold` takes the collection before the accumulator?

If you make a module `IntSet = Set.Make(Int)`, the signature of `IntSet.fold` is `(int -> 'a -> 'a) -> IntSet.t -> 'a -> 'a`. So it takes the function first, then the collection, and then the initial value for the accumulator. (Same for `Map` and `Hashtbl`.)

For `List.fold_left`, `Seq.fold_left`, etc, the signature is `('a -> 'b -> 'a) -> 'a -> 'b list -> 'a`, so, function first, then initial value for the accumulator, then the collection.

Is there a specific reason for this (seeming?) inconsistency, or was it just a historical accident?

(I tried googling but was unable to find anything on it.)

In the case of lists and sequences, there are two canonical orderings in which the fold can be carried out: left to right, or right to left, so it is natural to write the accumulator argument accordingly.

However, for other data structures which do not have a canonical ordering associated with them, an arbitrary choice (accumulator argument on the right) was done.

Cheers,
Nicolas

1 Like

But there is a canonical order?

`fold f s init` computes `(f xN ... (f x2 (f x1 init))...)`, where `x1 ... xN` are the elements of `s`, in increasing order.

Let’s flip the `f`:

`fold (Fun.flip f) s init` computes `(f ... (f (f init x1) x2) ... xN)`, where `x1 ... xN` are the elements of `s`, in increasing order.

Now compare the documentation of `List.fold_left`:

`fold_left f init [b1; ...; bn]` is `f (... (f (f init b1) b2) ...) bn`

Same thing, modulo parentheses. Looks like a mistake to me: we can get a signature like `fold_left` by flipping the arguments of the function passed to `fold` as well as the last two arguments (initial accumulator and the set).

We can’t make it into a `fold_right` without reversing, because in `fold_right` we have the application `f aN init` instead of `f init b1`.

Indeed, it is true that with the current implementation of sets and maps one can also define an “increasing” and a “decreasing” fold over them. However, it is not clear which one should be the “left” or “right” one, so it doesn’t really influence the positioning of the accumulator argument.

Cheers,
Nicolas

It’s pretty clear which one should be “left”: the one which makes `fold_left f init t` equivalent to `Seq.fold_left f init (to_seq t)`. Sets already have a `to_seq` (which gives the elements in ascending order), but no `fold_left`. I think ultimately the order of arguments for `fold` can be excused, because it doesn’t claim to be a left nor right fold. The set signature could however be extended with `fold_left` and `fold_right` functions with the expected types.

First of all, because `'a -> 'b -> 'c`, `'b -> 'a -> 'c`, `'a * 'b -> 'c`, etc… are all equivalent, it really is just a matter of how nice it looks in your head… (except the world isn’t sunshine and rainbows and sometimes these things have subtle runtime implications, but let’s assume all is good in the world).
Also I’m no compiler engineer, so this below is just how I see it, there could be actual interesting justifications!

If going by just the higher order function’s argument order, it makes sense for what a `fold_right` is, a catamorphism*, that its hof arguments are like that. `fold_left` doesn’t have to conform to that, and it is convenient for it** not to, from a bikeshedding standpoint of course.

The real crime strangeness is making the list come before the null argument and breaking the data-last expectation IMO * a right fold’s parameters correspond to cons and nil. So an identity fold can be:

``````List.(fun xs -> fold_right cons xs [])
``````

You could even argue that `fold_righ`’s arguments should correspond to the order of the constructor declaration:

``````type 'a list = Nil | Cons of 'a -> 'a list -> 'a list
let rec fold (nil : 'b) (cons : 'a -> 'b -> 'b) : 'a list -> 'b = function
| Nil -> nil
| Cons (x, xs) -> cons x (fold nil cons xs)
``````

** because function application is also left-associative, it looks nicer in your head, like it’s being consumed down a drain or something.

1 Like

If `(&)` is a left-associative operator, then `List.fold_left (&) x1 [x2;x3]` is `x1 & x2 & x3` (ie `(x1 & x2) & x3`).
If it is right-associative, then `List.fold_right (&) [x1;x2] x3` is `x1 & x2 & x3` (ie `x1 & (x2 & x3)`).

1 Like