Math from scratch in Haskell: addition

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

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


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

About Michael

I am a software developer and part-time professor. I enjoy studying and discussing mathematics, computer science and software development.
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply