Church Numerals in Haskell

church.hs

data N = Z | S N 

-- Naturals are equitable
instance Eq N where
  (==) Z Z = True
  (==) (S a) (S b) = a == b
  (==) (S n) _ = False
  (==) _ (S n) = False

-- Naturals are ordered
instance Ord N where
  (<=) Z Z = True
  (<=) (S a) (S b) = a <= b
  (<=) Z (S b) = True
  (<=) (S a) Z = False

-- Naturals can be displayed
instance Show N where
  show = show . nToInt

-- Wrap a function that operates on Naturals to operating on Ints
intWrapper :: (N -> N -> Maybe N) -> (Int -> Int -> Maybe Int)
intWrapper f = \ia ib ->
  do
    na <- intToN ia
    nb <- intToN ib
    result <- f na nb
    return $ nToInt result

justWrapper :: (N -> N -> N) -> (N -> N -> Maybe N)
justWrapper f = \a b -> Just $ f a b
  

-- Converts an integer to a Natural, if it's >= 0
intToN :: Int -> Maybe N
intToN n
  | n == 0 = Just Z
  | n > 0 = do
      sub <- intToN (n - 1)
      return $ S sub
  | otherwise = Nothing
  

nToInt :: N -> Int
nToInt Z = 0
nToInt (S n) = 1 + (nToInt n)

add :: N -> N -> N
add Z a = a
add a Z = a
add a (S b) = (S (add a b))

minus :: N -> N -> Maybe N
minus Z (S n) = Nothing
minus n Z = Just n
minus (S a) (S b) = minus a b

multiply :: N -> N -> N
multiply Z a = Z
multiply a Z = Z
multiply (S Z) a = a
multiply a (S Z) = a
multiply a (S b) = add a (multiply a b)

-- Simple datatype to hold the two division results
data DivInfo = Info N N deriving (Show)

ratio :: N -> N -> Maybe DivInfo 
ratio n (S Z) = Just $ Info n Z
ratio a b 
  | b == Z = Nothing
  | a > b = do
      sub <- (minus a b)
      term <- (ratio sub b)
      case term of (Info amnt rem) -> return (Info (S amnt) rem)
  | a == b = Just (Info (S Z) Z)
  | a < b = Just (Info Z a)
       
divide :: N -> N -> Maybe N
divide a b = do
  (Info amnt rem) <- (ratio a b)
  return amnt
      
modulo :: N -> N -> Maybe N
modulo a b = do
  (Info amnt rem) <- (ratio a b)
  return rem