Natural.hs

-- | 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
    fromEnum = fromIntegral

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