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