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.

```1 data Bit = ZeroBit | OneBit deriving Eq ```

Here is the implementation of natural addition:

```1 2 3 4 5 6 7 natAdd :: Natural -> Natural -> Natural natAdd n Zero = n natAdd Zero n = n natAdd n1@(Nat h1 t1) n2@(Nat h2 t2) | h1 == ZeroBit = createNatural (natAdd t1 t2) h2 | h2 == ZeroBit = createNatural (natAdd t1 t2) h1 | otherwise = createNatural (natAdd one (natAdd t1 t2)) ZeroBit ```

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`:

```1 2 3 4 5 6 7 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:

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 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 -- part three: addition and toString (show in Haskell) -- Also added derived implementation of Eq to Bit above natAdd :: Natural -> Natural -> Natural natAdd n Zero = n natAdd Zero n = n natAdd n1@(Nat h1 t1) n2@(Nat h2 t2) | h1 == ZeroBit = createNatural (natAdd t1 t2) h2 | h2 == ZeroBit = createNatural (natAdd t1 t2) h1 | otherwise = createNatural (natAdd one (natAdd t1 t2)) ZeroBit 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 natInc = natAdd one ```