I’ve been following a set of posts written by where he is implementing arbitrary size naturals and the corresponding arithmetic in C#. As I follow along I’m writing an implementation in Haskell (one that I hope is idiomatic to Haskell).

In part one and part two of the series he develops a representation of naturals and exposes two public members: `Zero`

and `One`

. Read those two posts to understand his implementation.

Here is my implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

module Natural (Natural, zero, one) where
data Bit = ZeroBit | OneBit
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
-- a ZeroBit followed by Zero
createNatural :: Natural -> Bit -> Natural
createNatural Zero ZeroBit = Zero
createNatural Zero OneBit = one
createNatural n b = Nat b n

On line 1 we expose the new type and two public values: `zero`

and `one`

.

I define two new types: `Bit`

and `Natural`

. The definition of `Bit`

is straightforward. I simply define two constructors: `ZeroBit`

and `OneBit`

. Likewise the definition of `Natural`

follows directly from the recursive definition given by Eric. I can construct a `Natural`

by using the `Zero`

constructor or by using the `Nat`

constructor (which adds a new least significant bit onto an existing `Natural`

).

Like Eric’s implementation I use a helper function to maintain the invariant he mentions that a `Natural`

never ends in a `ZeroBit`

followed by a `Zero`

.

The definitions of `zero`

and `one`

are straightforward as well. That’s it.

I’ll continue to add posts that follow Eric’s posts. The next post will show how to implement addition.