Version 2 (modified by diatchki, 7 years ago) (diff)

--

## Natural Numbers

We may define the type of (value level) natural numbers in terms of singleton types. The idea is that a natural number is, basically, an unknown singleton type. This is why we use an existential construct in the definition:

```data Natural = forall n . Natural !(Nat n)

instance Enum Natural
instance Eq Natural
instance Integral Natural
instance Num Natural
instance Ord Natural
instance Real Natural
instance Show Natural
```

The instances make it possible to work with 'Naturals' as with any other numeric type. Note, however, that some of the operations are partial. For example, subtracting a larger number from a smaller one results in the undefined value of type Natural.

We also provide some functions for converting Interger values into their corresponding Natural ones. We do this by using an intermediate representation for integers in terms of naturals, NaturalInteger. This type is intended to be used only for the conversion. While, in principle, we could provide numeric instances for the type, we chose not to, because we would be duplicating functionality provided by the type 'Integer'.

```data NaturalInteger
= Negative Natural
| NonNegative Natural

toNaturalInteger :: Integer -> NaturalInteger

subNatural :: Natural -> Natural -> NaturalInteger
```