证明自然数类型级加法的交换性
Proving commutativity of type level addition of natural numbers
我正在研究 haskell 为依赖类型编程提供的工具。我已经将一个代表自然数的GADT提升到种类级别,并制作了一个用于添加自然数的类型族。我还制作了标准 "baby's first dependently typed datatype" 向量,对其长度和包含的类型进行了参数化。代码如下:
data Nat where
Z :: Nat
S :: Nat -> Nat
type family (a :: Nat) + (b :: Nat) :: Nat where
Z + n = n
S m + n = S (m + n)
data Vector (n :: Nat) a where
Nil :: Vector Z a
Cons :: a -> Vector n a -> Vector (S n) a
此外,我制作了一个 append
函数,它接受一个 m 向量、一个 n 向量和 return 一个 (m+n) 向量。这和人们希望的一样有效。然而,只是为了它,我试着把它翻转过来,所以它 return 是一个 (n+m) 向量。但这会产生编译器错误,因为 GHC 无法证明我的加法是可交换的。我对类型族还是比较陌生,所以我不确定自己如何写这个证明,或者你是否可以在 haskell.
中做这件事
我最初的想法是以某种方式利用类型相等约束,但我不确定如何前进。
所以说清楚:我想写这个函数
append :: Vector m a -> Vector n a -> Vector (n + m) a
append Nil xs = xs
append (Cons x xs) ys = x `Cons` append xs ys
但无法通过
编译
* Could not deduce: (n + 'Z) ~ n
from the context: m ~ 'Z
bound by a pattern with constructor: Nil :: forall a. Vector 'Z a,
in an equation for `append'
这是一个完整的解决方案。警告:包括一些 hasochism。
我们从原始代码开始。
{-# LANGUAGE TypeFamilies, DataKinds, TypeOperators, GADTs, PolyKinds #-}
{-# OPTIONS -Wall -O2 #-}
module CommutativeSum where
data Nat where
Z :: Nat
S :: Nat -> Nat
type family (a :: Nat) + (b :: Nat) :: Nat where
'Z + n = n
'S m + n = 'S (m + n)
data Vector (n :: Nat) a where
Nil :: Vector 'Z a
Cons :: a -> Vector n a -> Vector ('S n) a
立即检查类型的旧追加。
append :: Vector m a -> Vector n a -> Vector (m + n) a
append Nil xs = xs
append (Cons x xs) ys = x `Cons` append xs ys
另外一个append,我们需要证明加法是可交换的。
我们首先在类型级别定义相等性,利用 GADT。
-- type equality, also works on Nat because of PolyKinds
data a :~: b where
Refl :: a :~: a
我们引入了单例类型,这样我们就可以传递 Nat
s 并对其进行模式匹配。
-- Nat singleton, to reify type level parameters
data NatI (n :: Nat) where
ZI :: NatI 'Z
SI :: NatI n -> NatI ('S n)
我们可以将每个向量的长度关联为单个向量 NatI
。
-- length of a vector as a NatI
vecLengthI :: Vector n a -> NatI n
vecLengthI Nil = ZI
vecLengthI (Cons _ xs) = SI (vecLengthI xs)
现在是核心部分。我们需要通过归纳来证明n + m = m + n
。这需要一些算术定律的引理。
-- inductive proof of: n + Z = n
sumZeroRight :: NatI n -> (n + 'Z) :~: n
sumZeroRight ZI = Refl
sumZeroRight (SI n') = case sumZeroRight n' of
Refl -> Refl
-- inductive proof of: n + S m = S (n + m)
sumSuccRight :: NatI n -> NatI m -> (n + 'S m) :~: 'S (n + m)
sumSuccRight ZI _m = Refl
sumSuccRight (SI n') m = case sumSuccRight n' m of
Refl -> Refl
-- inductive proof of commutativity: n + m = m + n
sumComm :: NatI n -> NatI m -> (n + m) :~: (m + n)
sumComm ZI m = case sumZeroRight m of Refl -> Refl
sumComm (SI n') m = case (sumComm n' m, sumSuccRight m n') of
(Refl, Refl) -> Refl
最后,我们可以利用上面的证明说服 GHC 按我们的意愿输入 append
。请注意,我们可以重用旧类型的实现,然后说服 GHC 它也可以使用新类型。
-- append, with the wanted type
append2 :: Vector m a -> Vector n a -> Vector (n + m) a
append2 xs ys = case sumComm (vecLengthI xs) (vecLengthI ys) of
Refl -> append xs ys
最后的评论。与完全依赖类型的语言(比如 Coq)相比,我们不得不引入单例并花费更多的精力让它们工作(Hasochism 的 "pain" 部分)。在 return 中,我们可以简单地使用 Refl
进行模式匹配,让 GHC 弄清楚如何使用推导出的方程,而不会弄乱依赖匹配("pleasure" 部分)。
总的来说,我认为使用完全依赖类型仍然更容易一些。 If/when GHC 获得非擦除类型量词(pi n. ...
超出 forall n. ...
),可能 Haskell 会变得更方便。
我正在研究 haskell 为依赖类型编程提供的工具。我已经将一个代表自然数的GADT提升到种类级别,并制作了一个用于添加自然数的类型族。我还制作了标准 "baby's first dependently typed datatype" 向量,对其长度和包含的类型进行了参数化。代码如下:
data Nat where
Z :: Nat
S :: Nat -> Nat
type family (a :: Nat) + (b :: Nat) :: Nat where
Z + n = n
S m + n = S (m + n)
data Vector (n :: Nat) a where
Nil :: Vector Z a
Cons :: a -> Vector n a -> Vector (S n) a
此外,我制作了一个 append
函数,它接受一个 m 向量、一个 n 向量和 return 一个 (m+n) 向量。这和人们希望的一样有效。然而,只是为了它,我试着把它翻转过来,所以它 return 是一个 (n+m) 向量。但这会产生编译器错误,因为 GHC 无法证明我的加法是可交换的。我对类型族还是比较陌生,所以我不确定自己如何写这个证明,或者你是否可以在 haskell.
我最初的想法是以某种方式利用类型相等约束,但我不确定如何前进。
所以说清楚:我想写这个函数
append :: Vector m a -> Vector n a -> Vector (n + m) a
append Nil xs = xs
append (Cons x xs) ys = x `Cons` append xs ys
但无法通过
编译 * Could not deduce: (n + 'Z) ~ n
from the context: m ~ 'Z
bound by a pattern with constructor: Nil :: forall a. Vector 'Z a,
in an equation for `append'
这是一个完整的解决方案。警告:包括一些 hasochism。
我们从原始代码开始。
{-# LANGUAGE TypeFamilies, DataKinds, TypeOperators, GADTs, PolyKinds #-}
{-# OPTIONS -Wall -O2 #-}
module CommutativeSum where
data Nat where
Z :: Nat
S :: Nat -> Nat
type family (a :: Nat) + (b :: Nat) :: Nat where
'Z + n = n
'S m + n = 'S (m + n)
data Vector (n :: Nat) a where
Nil :: Vector 'Z a
Cons :: a -> Vector n a -> Vector ('S n) a
立即检查类型的旧追加。
append :: Vector m a -> Vector n a -> Vector (m + n) a
append Nil xs = xs
append (Cons x xs) ys = x `Cons` append xs ys
另外一个append,我们需要证明加法是可交换的。 我们首先在类型级别定义相等性,利用 GADT。
-- type equality, also works on Nat because of PolyKinds
data a :~: b where
Refl :: a :~: a
我们引入了单例类型,这样我们就可以传递 Nat
s 并对其进行模式匹配。
-- Nat singleton, to reify type level parameters
data NatI (n :: Nat) where
ZI :: NatI 'Z
SI :: NatI n -> NatI ('S n)
我们可以将每个向量的长度关联为单个向量 NatI
。
-- length of a vector as a NatI
vecLengthI :: Vector n a -> NatI n
vecLengthI Nil = ZI
vecLengthI (Cons _ xs) = SI (vecLengthI xs)
现在是核心部分。我们需要通过归纳来证明n + m = m + n
。这需要一些算术定律的引理。
-- inductive proof of: n + Z = n
sumZeroRight :: NatI n -> (n + 'Z) :~: n
sumZeroRight ZI = Refl
sumZeroRight (SI n') = case sumZeroRight n' of
Refl -> Refl
-- inductive proof of: n + S m = S (n + m)
sumSuccRight :: NatI n -> NatI m -> (n + 'S m) :~: 'S (n + m)
sumSuccRight ZI _m = Refl
sumSuccRight (SI n') m = case sumSuccRight n' m of
Refl -> Refl
-- inductive proof of commutativity: n + m = m + n
sumComm :: NatI n -> NatI m -> (n + m) :~: (m + n)
sumComm ZI m = case sumZeroRight m of Refl -> Refl
sumComm (SI n') m = case (sumComm n' m, sumSuccRight m n') of
(Refl, Refl) -> Refl
最后,我们可以利用上面的证明说服 GHC 按我们的意愿输入 append
。请注意,我们可以重用旧类型的实现,然后说服 GHC 它也可以使用新类型。
-- append, with the wanted type
append2 :: Vector m a -> Vector n a -> Vector (n + m) a
append2 xs ys = case sumComm (vecLengthI xs) (vecLengthI ys) of
Refl -> append xs ys
最后的评论。与完全依赖类型的语言(比如 Coq)相比,我们不得不引入单例并花费更多的精力让它们工作(Hasochism 的 "pain" 部分)。在 return 中,我们可以简单地使用 Refl
进行模式匹配,让 GHC 弄清楚如何使用推导出的方程,而不会弄乱依赖匹配("pleasure" 部分)。
总的来说,我认为使用完全依赖类型仍然更容易一些。 If/when GHC 获得非擦除类型量词(pi n. ...
超出 forall n. ...
),可能 Haskell 会变得更方便。