OCaml - Accumulator Using Fold Left

Question

Learning OCaml from here.

I want to verify if I have understood how this snippet of OCaml code works

List.fold_left (fun acc x -> acc + x) 0 [ 1; 2; 3; 4 ]

I have an intuition that this is an equivalent to the reduce function in Python. Specifically, I think it is equivalent to

reduce(lambda x, y: x + y, [1, 2, 3])

The anonymous function is taking two parameters - acc and x and returns a single value acc + x. I understand that initially, the first argument acc will be 0 but how does it know that the second argument has to be the first element of the list?

What I think is happening is that fold_left provides the two arguments to the anonymous function and then recursively calls itself with new arguments until the list becomes empty.

To confirm this I saw this.

When I define a function like let inc x = x + 1 I get something like val inc : int -> int = <fun> but in this case the signature is : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>

What is 'a and how should I interpret this function signature so that List.fold_right f [a1; ...; an] b becomes f a1 (f a2 (... (f an b) ...))?

Answer 1

A little late, but the comparison between OCaml's folds and Python's reduce may be easier if you incorporate reduce's initializer argument.

Summing a list of ints in OCaml using a fold:

let sum = List.fold_left (+) 0 [1; 2; 3]

And using reduce in Python.

from functools import reduce

sum = reduce(int.__add__, [1, 2, 3], 0)

Here you can see the order of arguments is a bit different, but they're all there.

Python feels it's less likely you'll need the initializer, so leaves it at the end as an optional argument as a convenience. OCaml features the list as the last argument also as a convenience, as partial application makes it easy to write something like a sum function.

let sum = List.fold_left (+) 0

Rather than:

let sum lst = List.fold_left (+) 0 lst

Answer 2

If I remember correctly, reduce is a simpler version of fold, which takes the first element of the list as starting element. I'd define it this way:

let reduce f = function 
   | x::xs -> fold_left f x xs
   | [] -> failwith "can't call reduce on empty lists!"

If you enter it in OCaml, it will display its type:

val reduce : ('a -> 'a -> 'a) -> 'a list -> 'a 

You can contrast it with fold_left's type:

('b -> 'a -> 'b) -> 'b -> 'a list -> 'b

The type variables 'a and 'b here mean that they can stand for any type. In your example, both 'a and 'b become int. If we insert the types, fold_left has the signature:

(int -> int -> int) -> int -> int list -> int

That's what we expected: + is a function which takes two ints and returns a new one, 0 is an int and the [1;2;3;4;] is a list of ints. The case that fold_left has two type variables and reduce only has one already gives a hint that it is more general. To see why we can look at the definition of reduce. Since the starting element of the fold is an element of the list, the types 'a' and 'b must be the same. That's fine for summing up elements, but say, we'd like to construct an abstract syntax tree for our summation. We define a type for this:

type exp = Plus of exp * exp | Number of int 

Then we can call:

fold_left (fun x y -> Plus (x, (Number y))) (Number 0) [1; 2; 3; 4]

Which results in the expression:

Plus (Plus (Plus (Plus (Number 0, Number 1), Number 2), Number 3), Number 4)

A benefit of this tree is that you can nicely see what is applied first (0 and 1) - in case of addition this is not a problem, since it is associative (this means a+(b+c) = (a+b)+c) which is not the case for subtraction (compare e.g. 5-(3-2) and (5-3)-2).

If you want to do something similar with reduce, you will notice that OCaml complains about type errors:

reduce (fun x y -> Plus (x, (Number y))) [1; 2; 3; 4] ;; Error: This expression has type exp but an expression was expected of type
int

In this case, we can wrap each integer as an expression in our input list, then the types agree. Since we already have Numbers, we don't need to add the Number constructor to y:

let wrapped = map (fun x -> Number x) [1; 2; 3; 4] in
reduce (fun x y -> Plus (x, y)) wrapped

Again, we have the same result, but we needed an additional function call to map. In the case of fold_left, this is not necessary.

P.S.: You might have noticed that OCaml gives the type of fold_left as ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a. I guess you will quickly realize that the name of the type variables doesn't play a role. To make it easier to compare, I switched the names such that the function is always applied to a list of 'a.

Answer 3

You are asking many questions.

I'm pretty sure that Python reduce is a fold, so your intuition is probably right.

You ask "how does it know that the second argument has to be the first element of the list?" Unfortunately, I don't think this is a well formed question. There's no "it" that knows anything. Most likely the answer is given by the definition of fold_left. It knows what to do because somebody wrote the code that way :-)

Here is the definition of fold_left from the standard library:

let rec fold_left f accu l =
  match l with
    [] -> accu
  | a::l -> fold_left f (f accu a) l

In some sense, this should answer all your questions.

The type 'a in the type of fold_left is the type of the accumulator. The point is that you can use any type you want for the accumulator. This is why the fold is so powerful. As long as it matches the values accepted and returned by the folded function, it can be anything you want.