# [Haskell-cafe] lazy evaluation is not complete

Iavor Diatchki iavor.diatchki at gmail.com
Tue Feb 10 01:50:42 EST 2009

Hi,
Just for fun, here is the code that does this:

newtype Int' = I Int deriving Eq

instance Show Int' where
show (I x) = show x

instance Num Int' where
I x + I y     = I (x + y)

I 0 * _       = I 0
I x * I y     = I (x * y)

I x - I y     = I (x - y)

abs (I x)     = I (abs x)

signum (I x)  = I (signum x)

negate (I x)  = I (negate x)

fromInteger n = I (fromInteger n)

foo x = if x == 0 then 0 else foo (x - 1) * foo (x + 1)

*Main> foo 5 :: Int'
0

-Iavor

On Mon, Feb 9, 2009 at 7:19 AM, Jochem Berndsen <jochem at functor.nl> wrote:
>> A simplied version of Example 5-16 in Manna's classical book
>> "Mathematical Theory of Computation":
>>
>> foo x = if x == 0 then 0 else foo (x-1)*foo (x+1)
>>
>> If run with ghci, foo 5 does not terminate, i.e., Haskell does not look
>> for all outermost redices in parallel. Why? For efficiency reasons?
>>
>> It's a pity because a parallel-outermost strategy would be complete.
>
> (*) is strict in both arguments for Int. If you want to avoid this, you
> could do
> newtype X = X Int
> and write your own implementation of (*) that is nonstrict.
>
> --
> Jochem Berndsen | jochem at functor.nl
> GPG: 0xE6FABFAB
> _______________________________________________