# ML functions from polymorphic lists to polymorphic lists

I'm learning programming in ML (OCaml), and earlier I asked about ML functions of type 'a -> 'b. Now I've been experimenting a bit with functions of type 'a list -> 'b list. There are some obvious simple examples:

let rec loop l = loop l
let return_empty l = []
let rec loop_if_not_empty = function [] -> []
| l -> loop_if_not_empty l


What I can't figure out is how to make a function that does something other than return the empty list or loop (without using any library function). Can this be done? Is there a way to return non-empty lists?

Edit: Yes, if I have a function of type 'a -> 'b, then I can make another one, or a function of type 'a list -> 'b list, but what I'm wondering here is how to make the first one.

-
As with the previous question, please target the CS101 student learning programming in your answer, not the type theoretist that your answer might inspire him to later become. – Gilles Mar 14 '12 at 0:12
Notice that if you had a function f with this type returning a non empty list then fun a -> List.hd (f [ a ]) would have type 'a -> 'b without being non-terminating or raising an exception. – gallais Mar 14 '12 at 0:49

Well, something known as parametricity tells us that if we consider the pure subset of ML (that is, no infinite recursion, ref and all that weird stuff), there is no way to define a function with this type other than the one returning the empty list.

1. If we consider programming languages that satisfy certain conditions, we can deduce some cool theorems just by looking at the type signature of a polymorphic function (this is called the Parametricity Theorem).
2. ML (without infinite recursion, ref and all that weird stuff) satisfies those conditions.

From the Parametricity Theorem we know that if we have a function f : 'a list -> 'b list, then for all 'a, 'b, 'c, 'd and for all functions g : 'a -> 'c, h : 'b -> 'd we have:

map h ∘ f = f ∘ map g


(Note, f on the left has type 'a list -> 'b list and f on the right is 'c list -> 'd list.)

We are free to choose whatever g we like, so let 'a = 'c and g = id. Now since map id = id (easy to prove by induction on the definition of map), we have:

map h ∘ f = f


Now let 'b = 'd = bool and h = not. Let's assume for some zs : bool list it happens that f zs ≠ [] : bool list. It is clear that map not ∘ f = f does not hold, because

(map not ∘ f) zs ≠ f zs


If the first element of the list on the right is true, then on the left the first element is false and vice versa!

This means, our assumption is wrong and f zs = []. Are we done? No.

We assumed that 'b is bool. We've shown that when f is invoked with type f : 'a list -> bool list for any 'a, f must always return the empty list. Can it be that when we call f as f : 'a list -> unit list it returns something different? Our intuition tells us that this is nonsense: we just can't write in pure ML a function that always returns the empty list when we want it to give us a list of booleans and might return a non-empty list otherwise! But this is not a proof.

What we want to say is that f is uniform: if it always returns the empty list for bool list, then it has to return the empty list for unit list and, in general, any 'a list. This is exactly what the second point in the bullet list in the beginning of my answer is about.

The paper tells us that in ML f must take related values to related ones. I'm not going into details about relations, it is enough to say that lists are related if and only if they have equal lengths and their elements are pair-wise related (that is, [x_1, x_2, ..., x_m] and [y_1, y_2, ..., y_n] are related if and only if m = n and x_1 is related to y_1 and x_2 is related to y_2 and so on). And the fun part is, in our case, since f is polymorphic, we can define any relation on the elements of lists!

Let's pick any 'a, 'b and look at f : 'a list -> 'b list. Now look at f : 'a list -> bool list; we've already shown that in this case f always returns the empty list. We now postulate that all the elements of 'a are related to themselves (remember, we can choose any relation we want), this implies that any zs : 'a list is related to itself. As we know, f takes related values to related ones, this means that f zs : 'b list is related to f zs : bool list, but the second list has length equal to zero, and since the first one is related to it, it is also empty.

For completeness, I'll mention that there is a section on impact of general recursion (possible non-termination) in the Wadler's original paper, and there is also a paper exploring free theorems in the presence of seq.

-
Now I suspect the proof can be done in one step if instead of weakening the parametricity theorem by considering specific relations induced by functions (g and h in this case) go straight with custom-made general relations… – kirelagin Apr 20 '14 at 23:06
Nitpick, parametricity doesn't start with Wadler's paper (which claims to be a summary of approaches for defining parametricity). The idea dates back to Reynold's paper "Types, Abstraction and Parametric Polymorphism." The idea was also kinda present in Girard's proof of normalization for System F as far as I know. – jozefg May 8 '15 at 17:14

Let's get back to simpler objects: you cannot build an proper object of type 'a because then it would mean this object x can be used wherever 'a would fit. And that means everywhere: as an integer, an array, even a function. For example that would mean you can do things like x+2, x.(1) and (x 5). Types exist exactly to prevent this.

This the same idea that apply with a function of type 'a -> 'b, but there are some cases where this type can exists: when the function never returns an object of type 'b: when looping or raising an exception.

This also apply to functions that return a list. If your function is of type t -> 'b list and that you build an object of type t and apply it to this function, then that means that if you successfully access an element of this list then you will access to an object that have all types. So you can't access any element of the list: the list is either empty or ... there is no list.

However the type 'a list -> 'b list appears in usual exercises but that's only when you already have a function of type 'a -> 'b:

let rec map (f : 'a -> 'b) =
function
| [] -> []
| x :: xs -> f x :: map f xs


But you probably know this one.

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

-
Is the type of map not usually 'a list -> ('a -> 'b) -> 'b list? It seems a more natural order w.r.t. currying. – Raphael Mar 14 '12 at 7:07
Well it is quite standard in OCaml, Haskell, Caml Light, SML, Lisp or even theoretical monads. It seems natural to me: you can define a function like let double_list = List.map (( * ) 2). Do you have an example where currying with the list first is interesting? – jmad Mar 14 '12 at 10:07
('a -> 'b) -> 'a list -> 'b list reflects the fact that map is just the lifting of functions wrt the functor list. – gallais Mar 14 '12 at 10:12
Never mind; I should not write comments before breakfast. Thanks for your explanations. – Raphael Mar 14 '12 at 10:20
The older type theorist is less than thrilled by this answer. Ok, a non-empty type variable context is a way to have a function that's literally of type 'a -> 'b or 'a list -> 'b list, but that's not such an interesting observation. In fact I'm going to edit the question to make it clear this isn't what the younger student learning programming was wondering about. – Gilles Mar 15 '12 at 1:00