-- | 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 -- (_|_) `compare` Z == _|_, but (_|_) >= Z = True -- so for maximum laziness, we need a specialized version of (>=) and (<=) _ >= Z = True Z >= S _ = False S a >= S b = a >= b (<=) = flip (>=) S x `max` S y = S (x `max` y) x `max` y = x + y S x `min` S y = S (x `min` y) _ `min` _ = Z 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 fromEnum = 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