Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
2  
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 13 '12 at 11:22
    
It would help if you explained how you figured out that raise would work, so we know how best to explain why the solution your prof is looking for (which will work for the same reasons that raise works) works. –  sepp2k Mar 13 '12 at 11:29
    
@sepp2k raise : exn -> 'a so I can get the return value, I just ignore the argument. –  Gilles Mar 13 '12 at 12:00
1  
2  
See also Why will the Hindley-Milner algorithm never yield a type like t1 -> t2? discussing a more theoretical setting. –  Gilles Jan 1 at 4:33

2 Answers 2

up vote 15 down vote accepted

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
share|improve this answer

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.

share|improve this answer
    
The asker didn't understand a word of your first two paragraphs, but I like your sentence “their results can be given a arbitrary return type as they will never be produced”. –  Gilles Mar 13 '12 at 12:04
    
@J.D. Oh, I know. But this question is from the perspective of a student learning programming. –  Gilles Mar 13 '12 at 16:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.