id summary reporter owner description type status priority milestone component version resolution keywords cc os architecture failure testcase blockedby blocking related differential wikipage
741 full laziness guest "GHC 6.4.1 isn't fully lazy as the following code snippet demonstrates.
{{{
> module Test where
> data Nat = Z | S Nat
> deriving (Show, Eq)
>
> memo f = \ n -> case n of Z -> f_Z
> S n -> f_S n
> where f_Z = f Z
> f_S = memo (\ y -> f (S y))
>
> fib :: Nat -> Integer
> fib Z = 0
> fib (S Z) = 1
> fib (S (S n)) = fib (S n) + fib n
>
> fib' :: Nat -> Integer
> fib' = memo fib
> where
> fib Z = 0
> fib (S Z) = 1
> fib (S (S n)) = fib' (S n) + fib' n
}}}
Hugs calculates the memoized version of fib much faster.
Test> :set +s
Test> map fib [0 .. 30]
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040]
(21162936 reductions, 29882544 cells, 30 garbage collections)
Test> map fib' [0 .. 30]
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040]
(18924 reductions, 25176 cells)
By contrast, GHCi gives:
*Test> :set +s
*Test> map fib [0 .. 30]
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040]
(5.71 secs, 423333160 bytes)
*Test> map fib' [0 .. 30]
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040]
(19.75 secs, 2430652680 bytes)
The memoized version is actually slower. The flags
-no-full-laziness and -ffull-laziness seem to have no influence on the performance.
{{{
> instance Num Nat where
> fromInteger 0 = Z
> fromInteger (n + 1) = S (fromInteger n)
> Z + n = n
> S m + n = S (m + n)
> Z * n = Z
> S m * n = (m * n) + n
> Z - n = Z
> S m - Z = S m
> S m - S n = m - n
>
> instance Enum Nat where
> succ = S
> pred Z = Z
> pred (S n) = n
> toEnum = fromInteger . toInteger
> fromEnum Z = 0
> fromEnum (S n) = fromEnum n + 1
}}}" bug closed normal Compiler 6.4.1 fixed Unknown/Multiple Unknown/Multiple