|Version 3 (modified by diatchki, 14 months ago)|
We use a family of singleton types to relate type-level naturals to runtime values.
In our design, we chose to provide as primitive an overloaded "smart" constructor and a polymorphic elimination construct:
newtypeT Nat (n :: Nat) = Nat Integer class NatI n where tNat :: TNat n instance NatI 0 where tNat = TNat 0 instance NatI 1 where tNat = TNat 1 ... tNatInteger :: TNat n -> Integer tNatInteger (TNat n) = n
It is also possible to make the dual choice, where we provide a polymorphic constructor and an overloaded elimination construct:
data TNat (n :: Nat) = TNat class NatE n where tNatInteger :: TNat n -> Integer instance NatE 0 where tNatInteger TNat = 0 instance NatE 1 where tNatInteger TNat = 1 ...
We made this choice, at least in part, because it made the implementation simpler: the evidence for class NatI is just an integer. Note that our choice does not loose any generality because we can define the alternative design in terms of it:
data TNat1 (n :: Nat) = TNat1 tNat1Integer :: NatI n => TNat1 n -> Integer tNat1Integer = tNatInteger . cast where cast :: NatI n => TNat1 n -> TNat n cast TNat1 = tNat