ML function of type 'a -> 'b

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.

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.

StackExchange Computer Science Q#302, answer score: 19