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