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.
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.
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.
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)).
