Haskell 中类型级别 Nats 的一致性

Question

我正在尝试在 Haskell 中实现 Braun Tree 的一个版本，这需要我证明关于 Nats

的事实

If n :~: m, then n + 1 :~: m + 1

但是，我无法填写下面的 undefined。我试过 Refl，但类型系统报错。

import GHC.TypeLits
import Data.Type.Equality

sucCong :: ((p :: Nat) :~: (q :: Nat)) -> (p + 1 :: Nat) :~: (q + 1 :: Nat)
sucCong proof = undefined

我如何证明这一点？

Answer 1

proof 上的模式匹配，使其语句可用于约束求解器。然后类型 (:~:) 只有一个构造函数，所以无论如何在定义的其余部分没有太多选择。

sucCong :: (p :~: q) -> (p+1) :~: (q+1)
sucCong Refl = Refl

Congruence of Type Level Nats in Haskell