id,summary,reporter,owner,description,type,status,priority,milestone,component,version,resolution,keywords,cc,os,architecture,failure,testcase,blockedby,blocking,related,differential
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,,,,,,