[JadeNB]

> it's a matter of how much you put into the type system:

It's also a matter of how much polymorphism you have. There are lots of functions `Integer -> Integer`; there is only one total function `a -> a`. (This is the parametricity theorem mentioned by sanxiyn in http://news.ycombinator.com/item?id=4215055 .)

[cwzwarich]

There are lots of different functions `a -> a`. One could take a few cycles to complete, whereas others could take a day or week to complete. One could use a few bytes of space, whereas others could use megabytes or gigabytes.

[JadeNB]

I think that this is a different meaning of 'different' from the one usually recognised in computer science; it's my understanding that what usually matters is extensional equality (are the same outputs (eventually) produced for the same inputs?) rather than intensional equality (are those outputs produced in the same way?). Otherwise, all compiler transformations would be illegal.

(You could argue that a (correct) transformation that sends space usage way up may actually change even extension equality, in the sense that it could result in the transformed algorithm failing on a given piece of hardware when the original algorithm would have succeeded. However, my understanding is that the state of 'realistic' computer science, where hardware limitations are part of the reasoning, is in a much more primitive state than 'idealised' computer science.)