full laziness
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
Trac metadata
Trac field | Value |
---|---|
Version | 6.4.1 |
Type | Bug |
TypeOfFailure | OtherFailure |
Priority | normal |
Resolution | Unresolved |
Component | Compiler |
Test case | |
Differential revisions | |
BlockedBy | |
Related | |
Blocking | |
CC | |
Operating system | Unknown |
Architecture | Unknown |