Quoting John Hughes <[EMAIL PROTECTED]>:
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
_______________________________________________
Haskell-prime mailing list
[email protected]
http://haskell.org/mailman/listinfo/haskell-prime
