List.fold_left in OCaml

Question

I wrote a function, which adds all elements from the given list:

let rec add = function []->0 | h::t->h+add(t);;

Now I want to write the same function, but using List.fold_left, but I tried several changes but I still have an error. First I tried this:

let rec add = function []->0 | h::t-> add List.fold_left((fun h t-> h+t) h t);;

But I had an error, and I noticed that List.fold_left returns an int value so the recursion is unnecessary. So I changed for:

let add = function []->0 | h::t -> List.fold_left ( fun h t-> h+t h t);;

But I still getting error about wrong type : Error: This expression has type int -> 'a -> 'b but an expression was expected of type 'a But I don't know how to fix that, can anybody explain my how to use List.fold_left in this example?

nlucaroni nlucaroni · Accepted Answer · 2013-01-16T16:47:34

fold_left operates on lists, as your function does, by applying a function and accumulating a result in a particular manner. It takes care of and abstracts the recursion for you. It deals with the structure of the list, so you can deal with how to combine the elements of the list in a particular manner. So, you need to figure out the higher-order function you want to apply to fold_left that operates on the list in the same way.

For example, here are two ways to get the maximum element of a list,...

let rec max_list smallest lst = match lst with 
    | []   -> smallest
    | h::t -> max_list (max smallest h) t

let max_list smallest lst =
    List.fold_left (fun acc x -> max acc x) smallest lst

You'll notice the similarity in some aspects of the functions; the base case (smallest) and how to combine elements (using the function max). You should see the same similarities in your function.

Looking back at your final implementation,

let add = function | []->0
                   | h::t -> List.fold_left (fun h t-> h+t h t)

The problem here is that you have a misplaced parenthesis...

let add = function | []->0
                   | h::t -> List.fold_left (fun h t-> h+t) h t

But this can be simplified, similar to my example above.

List.fold_left in OCaml

3 Answers