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