[Haskell-cafe] lazy evaluation is not complete

[Iavor Diatchki]

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:
> Peter Padawitz 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
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>