What's the difference between these two functions?

Question

I have two functions:

let rev_flatten l = 
  List.fold_left (fun acc x -> List.fold_left (fun acc y -> y::acc) acc x) [] l

The type is val rev_flatten : 'a list list -> 'a list = <fun>

and

let rev_flatten = 
  List.fold_left (fun acc x -> List.fold_left (fun acc y -> y::acc) acc x) []

The type is val rev_flatten : '_a list list -> '_a list = <fun>

---

I think it is the same functions, at least the same functionality, but why they have two different types? Why the second has the element type of _a? What is it?

Answer 1

A type variable with underscore as a prefix tells us that the variable is weakly polymorphic. A weakly polymorphic variable can be used only with one type, however a compiler can't deduce the exact type, so the type variable is mark with underscore.

When you provide an argument for the first time, a variable will no longer be polymorphic and will be able to accept arguments of a single type only.

Usually, a function is not generalized, but marked as weakly polymorphic if it might contain mutable state. In your example this is probably the case, because type system doesn't know if List.fold_left is pure or impure function.

Edit: Why avoiding partial application (eta expansion) allows function (even impure) to be polymorphic?

Let's define a function that have an internal counter that is incremented and printed out every time the function is called. Among this, it takes a function as the argument and applies it after increasing the counter:

let count f =
  let inc = ref 0 in
  (fun x -> inc := !inc + 1; print_int !inc; f x);;

This function is polymorphic: ('a -> 'b) -> 'a -> 'b.

Next, let's define two more functions. A weekly polymorphic:

let max' = count max;;
val max' : '_a -> '_a -> '_a = <fun>

and a polymorphic one:

let max'' x = count max x;;
val max'' : 'a -> 'a -> 'a = <fun>

Now notice what is printed when we execute these functions:

max' 1 2;;  (* prints 1 *)
max' 1 2;;  (* prints 2 *)
max' 1 2;;  (* prints 3 *)
max'' 1 2;; (* prints 1 *)
max'' 1 2;; (* prints 1 *)
max'' 1 2;; (* prints 1 *)

So the function that we designed as weekly polymorphic has a persistent mutable state inside that allows to use the counter as expected, while the polymorphic function is stateless and is reconstructed with every call, although we wanted to have a mutable variable inside.

This is the reason for a compiler to prefer a weakly polymorphic function that can be used with any single type instead of supporting full-fledged polymorphism.

Answer 2

A function with the type '_a list list -> '_a list is weakly polymorphic. What this means is that if you call the second one on an int list list, rev_flatten will no longer by '_a list list -> 'a list but int list list -> int list

You can read more here about the details of why here: http://caml.inria.fr/resources/doc/faq/core.en.html

Cheers,

Scott