Geek asks and answers

Adding a natural number type

I assume that in haskell you can’t just add two natural level level numbers. It's true?

Suppose natural numbers are defined as follows:

class HNat a

data HZero
instance HNat HZero

data HSucc n
instance (HNat n) => HNat (HSucc n)

Is it possible to define HAdd in a way similar to:

class (HNat n1, HNat n2, HNat ne) => HAdd n1 n2 ne | n1 n2 -> ne
instance             HAdd HZero HZero HZero
instance (HNat x) => HAdd HZero x     x
instance (HNat n1 
         ,HNat x) => HAdd (HSucc n1)  x (HAdd n1 (HSucc x) (???))
+5
source share
2 answers

You do not need the case of adding HZeroand HZero. This is already being considered in the second case. Think about how you would add peano to the term level by induction on the first argument:

 data Nat = Zero | Succ Nat

 add :: Nat -> Nat -> Nat
 add Zero     y = y
 add (Succ x) y = Succ (add x y)

Now, if you use functional dependencies, you are writing a logical program. Therefore, instead of making a recursive call on the right side, you add a constraint on the result of the recursive call on the left:

 class (HNat x, HNat y, HNat r) => HAdd x y r | x y -> r
 instance (HNat y)     => HAdd HZero     y y
 instance (HAdd x y r) => HAdd (HSucc x) y (HSucc r)

HNat. .

, - DataKinds TypeFamilies. , :

 data Nat = Zero | Succ Nat

Nat , . :

 type family Add (x :: Nat) (y :: Nat) :: Nat
 type instance Add Zero     y = y
 type instance Add (Succ x) y = Succ (Add x y)

. , "" Nat , HNat.

+19

. type-level-natural-number `type-level-natural-number-operations. , , Plus.

, - ( , ).

instance (HNat n1, HNat x, HAdd n1 x y) => HAdd (HSucc n1) x (HAdd n1 x (HSucc y))

, , HAdd n1 x y .

+3

More articles:


All Articles