ML function of type 'a -> 'b

Question

Our professor asked us to think of a function in OCaml that has the type

'a -> 'b

i.e. a function of one argument that could be anything, and that can return a different anything.

I thought of using raise in a function that ignores its argument:

let f x = raise Exit

But the professor said there was a solution that doesn't require any function in the standard library. I'm confused: how can you make a 'b if you don't have one in the first place?

_{I'm asking here rather than on Stack Overflow because I want to understand what's going on, I don't want to just see a program with no explanation.}

Answer 1

The skeleton is let f x = BODY. In BODY you must use x only in generic ways (for example, don't send it to a function that expects integers), and you must return a value of any other type. But how can the latter part be true? The only way to satisfy the statement "for all types 'b, the returned value is a value of type 'b" is to make sure the function does not return. There are exactly two possibilities: either BODY faults or it doesn't terminate. The function raise faults, the following doesn't terminate:

let rec f x = f x

Answer 2

First, some remarks. Using only the core typed lambda calculus it's not possible to obtain 'a -> 'b because the typing system is in correspondence (via the Curry Howard isomorphism) to intuitionistic logics, and the corresponding formula A → B is not a tautology.

Other extensions such as tuples and matchings/conditionals still preserve some logic consistency adding product types * which correspond to the logical connective and, and sum types | which correspond to the or. Again, don't expect them to produce that 'a -> 'b type, as it would allow one to prove some formula which is not a tautology.

So your only chances are using other constructions which escape from the logics like raise (but you're not allowed to in this case)… or let rec! Recursion allows to build programs which never terminate, and their results can be given an arbitrary return type as they will never be produced. Now if you think about the most trivial non terminating function (the one which directly calls itself to return a result):

let rec f x = f x

You'll notice that its type is exactly 'a -> 'b: whatever is the provided argument, the result (which will never be computed) can be assumed to have any type.

Of course this f is not an interesting function, but that's the point. In OCaml, any function whose type does not look like a valid formula is a suspicious function.

Answer 3

Using a compiler primitive you can write this:

external magic: 'a -> 'b = "%identity"

(and indeed the compiler distribution provides this, though isn't part of the language). This is an unsafe identity cast.

Your professor almost certainly doesn't want this. However, this is also the only useful function with type 'a -> 'b that I am aware of, and indeed it is used in the OCaml distribution itself.