Search code examples
smlnj

foldl definition possible wrong in SML/NJ 110.75

The signature of foldl in SML/NJ 110.75 is

foldl;
val it = fn : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b

Also if I give:

foldl (op -) 2 [1];

I will take as answer ~1 instead of 1

Can you confirm my findings?

Solution

  • From the basis library: http://www.standardml.org/Basis/list.html#SIG:LIST.foldl:VAL

    foldl f init [x1, x2, ..., xn] returns

    f(xn,...,f(x2, f(x1, init))...)

or init if the list is empty.

    thus in foldl (op -) 2 [1] the result is the evaluation of xn - init or 1 - 2

    What makes this particular example a bit harder to understand is that (op -) is a non-associative infix operator. So the f in the basis library definition gets moved between xn and init.

    The signature is only for static type checking, and it is worth remembering that 'a and 'b may be of the same type.