On Sun, Dec 11, 2011 at 8:09 PM, Graham Gill
Excellent, thanks Daniel and Felipe.
We don't even need to invoke infinite or undecidable problems, since it's easy to construct equal functions for which determining equality would be prohibitively expensive. If then you can only check equality for some functions, because you want compilation to finish, say, within the programmer's lifetime, you lose referential transparency.
Note that the time isn't spent on compilation time, but on run time! Which is actually worse ;-). Also note that it is possible to imagine something like obviouslyEqual :: a -> a -> Bool where 'obviouslyEqual x y' is 'True' when it's easy to see that they are equal or 'False' if you can't decide. Actually, with GHC you may say {-# LANGUAGE MagicHash #-} import GHC.Exts obviouslyEqual :: a -> a -> Bool obviouslyEqual a b = case I# (reallyUnsafePtrEquality# a b) of 0 -> False _ -> True However, this functions is *not* referentially transparent (exercise: show an example of how obviouslyEqual breaks referential transparency). reallyUnsafePtrEquality# is really unsafe for a reason =). Cheers, -- Felipe.