[GHC] #741: full laziness

[GHC]

#741: full laziness
-------------------------+--------------------------------------------------
    Reporter:  guest     |        Owner:         
        Type:  bug       |       Status:  new    
    Priority:  normal    |    Milestone:         
   Component:  Compiler  |      Version:  6.4.1  
    Severity:  normal    |     Keywords:         
          Os:  Unknown   |   Difficulty:  Unknown
Architecture:  Unknown   |  
-------------------------+--------------------------------------------------
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
 }}}

-- 
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/741>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler