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@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@functor.nl GPG: 0xE6FABFAB _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe