Natural.hs: For fun wrote up a definition for natural numbers using recursive types.

Natural.hs

module Natural where

data Natural = Zero | Inc Natural

instance Eq Natural where
  (==) Zero Zero = True
  (==) (Inc a) (Inc b) = a == b
  (==) a b = False

instance Ord Natural where
  compare Zero Zero = EQ
  compare (Inc _) Zero = GT
  compare Zero (Inc _) = LT
  compare (Inc a) (Inc b) = compare a b

instance Enum Natural where
  toEnum n
    | n == 0 = Zero
    | n > 0  = Inc $ toEnum $ n - 1
    | otherwise = error "underflow"

  fromEnum Zero = 0
  fromEnum (Inc n) = 1 + fromEnum n

  succ = Inc 
  pred Zero = error "underflow"
  pred (Inc n) = n

  enumFrom n = n:(enumFrom (succ n))
  enumFromTo a b
    | a <= b    = a:(enumFromTo (succ a) b)
    | otherwise = []

instance Num Natural where
  fromInteger = toEnum . fromInteger

  abs n = n

  signum Zero = Zero
  signum (Inc n) = Inc Zero

  (+) n Zero = n
  (+) Zero n = n
  (+) a (Inc b) = succ a + b

  (-) n Zero = n
  (-) Zero n = error "underflow"
  (-) (Inc a) (Inc b) = a - b

  (*) Zero _ = Zero
  (*) _ Zero = Zero
  (*) a@(Inc _) (Inc b) = a + a * b

instance Integral Natural where
  toInteger = toInteger . fromEnum

  quotRem _ Zero = error "divide by zero"
  quotRem a@(Inc _) b@(Inc _)
    | a >= b = inc $ quotRem (a - b) b
    | otherwise = (Zero, a)
    where inc (q,r) = (succ q, r)

instance Real Natural where
  toRational = toRational . toInteger

instance Show Natural where
  show = ("nat " ++) . show . fromEnum

nat :: Int -> Natural
nat = toEnum