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