Quoting John Hughes
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
I am thinking of the beginner. I would hate to explain what the difference between '=' and ':=' is and when to use one or the other. I think that's a wart as ugly as the M-R. As for there being many warnings, we don't really know, do we? I'm only suggesting a warning when there's a potential loss of sharing, not in general. In my experience it's very rare to have the M-R kick in at the top level; it's almost always in local definitions. And for local definitions you can see all uses of a binding and handle it accordingly. Local bindings are very rarely used polymorphically. Nhc didn't use to implement the M-R (maybe it does now). When porting code to nhc this caused a few code changes. Perhaps 10 lines out of 10000 when I tried the Bluespec compiler. So my gut feeling is that the M-R is a rare beast in practise. -- Lennart