Integers from scratch in Haskell Inspired by this article about natural numbers from first principles in swift I implemented integers from scratch in Haskell.

Besides obviously being extremely inefficient, is this code idiomatic Haskell?

import Data.List
import GHC.Real


data ℤ = Pred ℤ | Zero | Succ ℤ

toNat = toEnum :: Int -&gt; ℤ
fromNat = fromEnum :: ℤ -&gt; Int  

toInteger' :: ℤ -&gt; Integer
toInteger' Zero = 0
toInteger' (Succ n) = toInteger' n + 1
toInteger' (Pred n) = toInteger' n - 1

instance Show ℤ where

  show = ((++) "Nat: ") . show . toInteger'


data SimpleNat = MinusOne | One deriving (Eq, Ord, Show)

toList :: ℤ -&gt; [SimpleNat]
toList Zero = []
toList (Succ n) = One : toList n
toList (Pred n) = MinusOne : toList n

fromList :: [SimpleNat] -&gt; ℤ
fromList [] = Zero
fromList (One:xs) = Succ (fromList xs)
fromList (MinusOne:xs) = Pred (fromList xs)

normaliseList :: [SimpleNat] -&gt; [SimpleNat]
normaliseList xs = normaliseSorted $ sort xs
                   where normaliseSorted xs = map fst filtered
                         filtered = filter (uncurry (==)) $ zip xs (reverse xs)

normalise :: ℤ -&gt; ℤ
normalise = fromList . normaliseList . toList


instance Enum ℤ where

  succ (Pred n) = n
  succ n = Succ n

  pred (Succ n) = n
  pred n = Pred n

  toEnum n | n &lt; 0 = Pred $ toEnum (n+1)
           | n &gt; 0 = Succ $ toEnum (n-1)
           | otherwise = Zero

  fromEnum Zero = 0
  fromEnum (Succ n) = fromEnum n + 1
  fromEnum (Pred n) = fromEnum n - 1


instance Num ℤ where

  Zero + n = n
  n + Zero = n
  (Succ n) + m = Succ (n + m)
  (Pred n) + m = Pred (n + m)

  abs n = abs' $ normalise n
          where abs' (Pred n) = Succ (abs' n)
                abs' n = n

  signum n = signum' $ normalise n
             where signum' Zero = Zero
                   signum' (Succ n) = Succ Zero
                   signum' (Pred n) = Pred Zero

  negate n = negate' $ normalise n
             where negate' Zero = Zero
                   negate' (Succ n) = Pred (negate' n)
                   negate' (Pred n) = Succ (negate' n)

  fromInteger n | n &lt; 0 = Pred $ fromInteger (n+1)
                | n &gt; 0 = Succ $ fromInteger (n-1)
                | otherwise = Zero


  Zero * _ = Zero
  _ * Zero = Zero
  (Succ n) * m = n*m + m
  (Pred n) * m = n*m - m


instance Eq ℤ where

  n == m = normalise n `eq` normalise m
           where Zero `eq` Zero = True
                 (Succ n) `eq` (Succ m) = n `eq` m
                 (Pred n) `eq` (Pred m) = n `eq` m
                 _ `eq` _ = False


instance Ord ℤ where

  a `compare` b = normalise a `comp` normalise b
                  where Zero `comp` Zero = EQ
                        Zero `comp` (Succ _) = LT
                        Zero `comp` (Pred _) = GT
                        (Succ _) `comp` Zero = GT
                        (Succ _) `comp` (Pred _) = GT
                        (Pred _) `comp` Zero = LT
                        (Pred _) `comp` (Succ _) = LT
                        (Succ n) `comp` (Succ m) = n `comp` m
                        (Pred n) `comp` (Pred m) = n `comp` m


instance Real ℤ where

  toRational n = toInteger' n % 1


instance Integral ℤ where

  toInteger = toInteger'

  quotRem _ Zero = error "divide by zero"
  quotRem Zero _ = (Zero, Zero)
  quotRem n d | n == d = (Succ Zero,0)
              | n &lt; d = (Zero, n)
              | otherwise = (Succ (fst foo), snd foo)
                          where foo = (n-d) `quotRem` d
This is some good looking code, there are just a few things that throw me. The first is that you're defining the integers but occasionally referring to them as "Nat"s. The natural numbers are non-negative integers, don't confuse the two.

toNat = toEnum :: Int -&gt; ℤ
fromNat = fromEnum :: ℤ -&gt; Int


This is a strange construction, give the type signature before the definition of the function and GHC will figure out which version of toEnum and fromEnum to use. Anything else is unusual and unnecessary.

Your Show instance should really just punt to the instance for Integers. Again, naturals numbers aren't integers so your "Nat: " tag is incorrect, it doesn't really add anything, and it makes writing a Read instance more difficult. Also there's no need to section infix functions by writing them prefix style. Thus:

instance Show ℤ where
    show = show . toInteger

instance Read ℤ where
    read = fromInteger . read


Your normalization function is more complex than it needs to be, but consider what having to normalize says about the representation you picked. Here's one version that doesn't change anything about your data types.

normalise = fromList . uncurry tailOfLonger . partition isOne . toList
    where 
          isOne :: SimpleNat -&gt; Bool
          isOne One = True
          isOne _   = False

          tailOfLonger :: [a] -&gt; [a] -&gt; [a]
          tailOfLonger    []     ys  = ys
          tailOfLonger    xs     []  = xs
          tailOfLonger (_:xs) (_:ys) = tailOfLonger xs ys


You have some unnecessary pattern match cases, such as n + Zero = n in the Num instance declaration. There's nothing wrong operationally with that case of course, but it's superfluous and the beauty of the inductive construction of the integers encourages me at least to be ruthless with flensing redundant code.



Here is an alternate construction that could obviate the need for all of the expensive normalization your version incurs. Writing the Num instance is pretty fun.

data Nat = Zero | Succ Nat

data Z = Negative Nat | NonNegative Nat