The dreaded M-R
rjmh at cs.chalmers.se
Mon Jan 30 07:58:21 EST 2006
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)
p :: (Num a, Num b) => (a,b)
p = fib' (n-1)
Here you need BOTH type signatures, since otherwise the one stated for p
is too general (needs polymorphic recursion).
Maybe it's obvious from the two type variables that sharing will be lost--
but the example below only has one, and is still exponential time under Hugs
(GHC optimises it to linear).
fib2 n = fst (fib2' n)
fib2' :: Num a => Integer -> (a,a)
fib2' 0 = (0,1)
fib2' n = (snd p,fst p+snd p)
p :: Num a => (a,a)
p = fib2' (n-1)
In this case, provided you write the type signature on fib2' (thus
polymorphic recursion), then the type signature I wrote on p is the one that
would be inferred, were it not for the M-R--and thus this program risks
running in exponential time. Same applies to fib' above: if you write the
type signature on fib', then but for the M-R, the type signature on p is the
one that would be inferred, and you get exponential time behaviour.
It would be undesirable for adding a type signature to a function (such
above) to risk making its performance exponentially worse, because of
consequential loss of sharing in a binding somewhere else. Wouldn't it?
More information about the Haskell-prime