Lennart Augustsson wrote:
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.
True. I don't remember my original example.
I still think removing the M-R and issuing a warning when there's a potential loss of sharing would be acceptable.
Wouldn't there be quite a lot of warnings? I really think we have to remember beginners' problems here. I know noone reading this discussion is one, but without beginners, there will be no growth in the Haskell community. If we did as you suggest, then beginners would be confronted by yet another kind of incomprehensible message--and I fear it would be hard to report that x=e risks evaluating e many times, in a way that would be viewed as positive by someone still trying to understand how Haskell works at all. John