```-- | Lazy natural numbers.
-- Addition and multiplication recurses over the first argument, i.e.,
-- @1 + n@ is the way to write the constant time successor function.
--
-- Note that (+) and (*) are not commutative for lazy natural numbers
-- when considering bottom.
module Data.Number.Natural(Natural, infinity) where

data Natural = Z | S Natural

instance Show Natural where
showsPrec p n = showsPrec p (toInteger n)

instance Eq Natural where
x == y  =  x `compare` y == EQ

instance Ord Natural where
Z   `compare` Z    =  EQ
Z   `compare` S _  =  LT
S _ `compare` Z    =  GT
S x `compare` S y  =  x `compare` y

instance Num Natural where
Z   + y  =  y
S x + y  =  S (x + y)

x   - Z    =  x
Z   - S _  =  error "Natural: (-)"
S x - S y  =  x - y

Z   * y  =  Z
S x * y  =  y + x * y

abs x = x
signum Z = Z
signum (S _) = S Z

fromInteger x | x < 0 = error "Natural: fromInteger"
fromInteger 0 = Z
fromInteger x = S (fromInteger (x-1))

instance Integral Natural where
-- Not the most efficient version, but efficiency isn't the point of this module. :)
quotRem x y =
if x < y then
(0, x)
else
let (q, r) = quotRem (x-y) y
in  (1+q, r)
div = quot
mod = rem
toInteger Z = 0
toInteger (S x) = 1 + toInteger x

instance Real Natural where
toRational = toRational . toInteger

instance Enum Natural where
toEnum = fromIntegral