-- | 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 = (+1)
    pred = (subtract 1)
    toEnum = fromIntegral
    fromEnum = fromIntegral
    enumFromThenTo from thn to = go from (to `maybeSubtract` from) where
      go from Nothing      = []
      go from (Just count) = from:go (thn + from) (count `maybeSubtract` thn)
    enumFrom a       = enumFromThenTo a 1 infinity
    enumFromThen a b = enumFromThenTo a b infinity
    enumFromTo a c   = enumFromThenTo a 1 c

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