Last time I developed a representation of Natural numbers following Eric Lippert’s lead. In this post I’ll continue to follow him and implement addition.

Eric did all the hard work of explaining the recursive algorithm for addition.

First thing I’ll need is an equality operator for Bit. I’ll just derive that by adding “deriving Eq” to the Bit definition.

data Bit = ZeroBit | OneBit deriving Eq


Here is the implementation of natural addition:

natAdd :: Natural -> Natural -> Natural
natAdd n1@(Nat h1 t1) n2@(Nat h2 t2)
| h1 == ZeroBit = createNatural (natAdd t1 t2) h2
| h2 == ZeroBit = createNatural (natAdd t1 t2) h1


Then like Eric I added the ability to convert a Natural to a string. In Haskell this is done by implementing instance of Show. I do this for both Bit and Natural:

instance Show Bit where
show ZeroBit = "0"
show OneBit = "1"

instance Show Natural where
show Zero = "0"
show (Nat h t) = show t ++ show h


Finally I added an increment method and exposed the new functions. The whole implementation now looks like this:

module Natural (Natural, zero, one, natAdd, natInc) where

data Bit = ZeroBit | OneBit deriving Eq

data Natural = Zero | Nat Bit Natural

zero = Zero
one = Nat OneBit Zero

-- Creates a natural number. Keeps the invariant that
-- Naturals always end with Zero and never end with ZeroBit followed by Zero
createNatural :: Natural -> Bit -> Natural
createNatural Zero ZeroBit = Zero
createNatural Zero OneBit = one
createNatural n b = Nat b n

-- Also added derived implementation of Eq to Bit above
natAdd :: Natural -> Natural -> Natural
natAdd n1@(Nat h1 t1) n2@(Nat h2 t2)
| h1 == ZeroBit = createNatural (natAdd t1 t2) h2
| h2 == ZeroBit = createNatural (natAdd t1 t2) h1

instance Show Bit where
show ZeroBit = "0"
show OneBit = "1"

instance Show Natural where
show Zero = "0"
show (Nat h t) = show t ++ show h

-- bug guy meets math from scratch: added increment
natInc :: Natural -> Natural