How do I use List.fold_left?

Question

I'm still trying to understand how fold_left exactly works. Does it iterate through the list like List.iter? Or is there just something else wrong with my code? I'm thinking that e is the element in the list (so it's a tuple) and fst e takes the first element of the tuple and snd e takes the second element in the tuple.

let rec pow x n = 
    if n < 0 then
        0
    else if n = 0 then
        1
    else 
        x * pow x (n - 1);;    

let polynomial lst = function
    | x -> List.fold_left (fun e -> (fst e) * (pow x (snd e))) 1 lst;;

lst is a list of tuples where each tuple has two integers and makes a polynomial function, so polynomial is supposed to return a function. So an example of what should happen is this

# let f = polynomial [3, 3; -2, 1; 5, 0];;
val f : int -> int = <fun>
# f 2;; (* f is the polynomial function f(x) = 3x^3 + (-2)x + 5 *)
- : int = 25

But I get this error message

"Error: This expression has type int but an expression was expected of type 'a -> int * int".

ivg ivg · Accepted Answer · 2019-05-03T18:36:37

List.fold_left indeed iterates over a list, passing the value from one call to another, which basically works like a bucket brigade, with only one bucket, where on each iteration you can look into the bucket, take whatever is there and put something new.

More formally, fold_left f init elements has type

val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

and it takes three arguments, the function f, the initial value init, and a list of elements. The function f is called for each element x of elements as f acc x, where acc is either init if x is the first element of the list or a result returned by the previous invocation of f. Back to our analogy, it is either the initial empty bucket or a bucket passed from the previous call in the chain.

In your case, the role of the bucket is the final sum of all terms. Initially, it is empty, then each new term computes (fst e) * (pow x (snd e)) and adds it to the bucket so that at the end you will have the sum of all terms,

let polynomial coeffs x = 
  List.fold_left (fun sum (k,r) -> sum + k * pow x r) 0 coeffs

Note, that instead of using fst and snd to access the elements of the pair, I deconstructed the tuple directly in the parameter list. This makes code easier to understand and shorter.

The function, that is applied on each step takes two arguments, sum is the bucket (it is often called the "accumulator") and the element of the list, which is a pair (k,r) in our case. We multiply k by the value of the x variable raised to the power r and then we add the result to the accumulator.

For people with an imperative mindset the following pseudocode¹ might be more insightful than the bucket brigade analogy:

def fold_left(user_func, init, elements):
    acc = init
    for elt in elts:
       acc = user_func(acc, elt)
    return acc

¹) Any resemblance to Python is purely coincidental :)

How do I use List.fold_left?

1 Answers