```-- | 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

import Data.Maybe

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

maybeSubtract :: Natural -> Natural -> Maybe Natural
a   `maybeSubtract` Z   = Just a
S a `maybeSubtract` S b = a `maybeSubtract` b
_   `maybeSubtract` _   = Nothing

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

x   - y  = fromMaybe (error "Natural: (-)") (x `maybeSubtract` 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
succ = S
pred Z = error "Natural: pred 0"
pred (S a) = a
toEnum = fromIntegral
enumFromThenTo from thn to | from <= thn = go from (to `maybeSubtract` from) where
go from Nothing      = []
go from (Just count) = from:go (step + from) (count `maybeSubtract` step)
step = thn - from
enumFromThenTo from thn to | otherwise = go (from + step) where
go from | from >= to + step = let next = from - step in next:go next
| otherwise         = []
step = from - thn
enumFrom a       = enumFromThenTo a (S a) infinity
enumFromThen a b = enumFromThenTo a b infinity
enumFromTo a c   = enumFromThenTo a (S a) c

-- | The infinite natural number.
infinity :: Natural
infinity = S infinity
```