List.Fold_Left type system in Ocaml?

Question

Write an Ocaml function list_print : string list -> unit that prints all the strings in a list from left to right:

So Lets say I've got an Ocaml function list_print: string list -> unit that prints all the strings in a list from left to write. Now the correct solution is:

let list_print lst = List.fold_left (fun ( ) -> fun s -> print_string s) () lst;;

But When writing my solution, I wrote it as such:

let list_print lst = List.fold_left (fun s -> print_string s) () lst;;

But this gave me

Error: This expression has type unit but an expression was expected of type 'a -> string

Why is it that I need that first parameter fun() -> before the fun s? I'm still new to Ocaml so this type system is quite confusing to me

Answer 1

The purpose of fold_left (and fold_right) is to accumulate a value as you go along. The extra parameter is this accumulated value.

You can use List.iter for your problem. It doesn't accumulate a value.

You could think of List.iter as a version of List.fold_left that accumulates values of type unit. And, in fact, you could implement it that way:

let iter f = List.fold_left (fun () a -> f a) ()

The point (as always with unit) is that there's only one value of the type, so it represents cases where the value isn't interesting.

Answer 2

You want to use List.fold_left, that's fine, but you should start by reading the documentation for that function. The official documentation is quite short:

val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
List.fold_left f a [b1; ...; bn] is f (... (f (f a b1) b2) ...) bn.

The first thing is the type of that function. The type is

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

In other words, the function fold_left has three arguments and one result value. The first argument has type ('a -> 'b -> 'a). The second argument has type 'a. The third argument has type 'b list. The result value of the function has type 'a.

Now, in your case, you want to print the strings. So you do not actually need any result value, you need a side effect. However, in OCaml all functions must have a result value. So you use the empty value, (), which has type unit. Therefore, the type parameter 'a will be equal to unit in your case.

The type parameter 'b is string because you are required to work on the list of strings.

Therefore, in your case the function fold_left must have the type

 (unit -> string -> unit) -> unit -> string list -> unit.     

The first argument of fold_left must have the type unit->string->unit. In other words, it must be a function with two arguments, first argument is the empty value, i.e. (), the second argument a string. So the first argument to fold_left must be a function of this kind,

 fun x y -> ...

where x must be of type unit and y of type string. Since x is going to be always equal to (), it is not necessary to write this argument as a variable x, instead we can simply write () or even the dummy argument _. (The syntax fun x -> fun y -> ... gives the same function as fun x y -> ....)

Now you can begin to figure out how fold_left works. Since this is obviously a homework question, I will leave this task to you.