John Hughes wrote:
An example where loss of sharing leads to exponential time:
fib n = fst (fib' n)
fib' :: (Num a, Num b) => Integer -> (a,b) fib' 0 = (0,1) fib' n = (snd p,fst p+snd p) where p :: (Num a, Num b) => (a,b) p = fib' (n-1)
It would be undesirable for adding a type signature to a function (such as fib' above) to risk making its performance exponentially worse, because of consequential loss of sharing in a binding somewhere else. Wouldn't it?
I don't agree in this case. You are asking for something rather strange when you put that type signature on fib'. I also noticed that to give a "convincing" example you picked something with polyporphic recursion. P-R wasn't in Haskell at the time the M-R was added (if memory serves me). So there must be other examples. I still think removing the M-R and issuing a warning when there's a potential loss of sharing would be acceptable. -- Lennart