The dreaded M-R

[Lennart Augustsson]

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