module Main where

main = print (fib' 100)
        -- This will time out unless memoing works properly

data Nat = Z | S Nat
           deriving (Show, Eq)

memo f = g
  where
    fz = f Z
    fs = memo (f . S)
    g  Z    = fz
    g (S n) = fs n
        -- It is a BAD BUG to inline 'fs' inside g
        -- and that happened in 6.4.1, resulting in exponential behaviour

-- memo f = g (f Z) (memo (f . S))
--        = g (f Z) (g (f (S Z)) (memo (f . S . S)))
--        = g (f Z) (g (f (S Z)) (g (f (S (S Z))) (memo (f . S . S . S))))

fib' :: Nat -> Integer
fib'             =  memo fib
  where
  fib Z          =  0
  fib (S Z)      =  1
  fib (S (S n))  =  fib' (S n) + fib' n

instance Num Nat where
  fromInteger 0        =  Z
  fromInteger n        =  S (fromInteger (n - 1))
  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