The dreaded M-R

[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