|Version 3 (modified by 6 years ago) (diff),|
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 Read 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