应该如何理解 "lemma" 函数的一般类型？
How should the general type of a "lemma" function be understood?
也许这是一个愚蠢的问题。这是来自 the Hasochism paper 的引述：
One approach to resolving this issue is to encode lemmas, given by
parameterised equations, as Haskell functions. In general, such lemmas
may be encoded as functions of type:
∀ x1 ... xn. Natty x1 → ... → Natty xn → ((l ~ r) ⇒ t) → t
我以为我理解了RankNTypes，但是我无法理解这个命题的最后一部分。我以 "given a term which requires l ~ r, return that term" 的形式非正式地阅读它。我确定这种解释是错误的，因为它似乎会导致循环：在证明本身得出结论之前我们不知道 l ~ r，所以我怎么能期望提供作为证明的假设 a哪个词需要那个？
我原以为等式证明的类型更像这样：
Natty x1 → ... → Natty xn → l :~: r
非正式地，"given a bunch of Nattys, return a proof of the proposition that l and r are equal"（使用 GHC 的 Data.Type.Equality）。这对我来说更有意义，并且似乎与您在其他依赖类型系统中所说的一致。我猜它等同于论文中的版本，但我正在努力将这两个版本放在一起。
简而言之，我很困惑。我觉得我缺少一个关键的见解。我应该如何阅读类型 ((l ~ r) => t) -> t?
I'm reading it as "given a term which requires l ~ r, return that
term"
是"given a term whose type contains l, return that term with all ls being substituted by rs in the type"（或者反方向r -> l）。这是一个非常巧妙的技巧，它允许您将所有 cong、trans、subst 和类似的东西委托给 GHC。
这是一个例子：
{-# LANGUAGE GADTs, DataKinds, PolyKinds, TypeFamilies, TypeOperators, RankNTypes #-}
data Nat = Z | S Nat
data Natty n where
Zy :: Natty Z
Sy :: Natty n -> Natty (S n)
data Vec a n where
Nil :: Vec a Z
Cons :: a -> Vec a n -> Vec a (S n)
type family (n :: Nat) :+ (m :: Nat) :: Nat where
Z :+ m = m
(S n) :+ m = S (n :+ m)
assoc :: Natty n -> Natty m -> Natty p -> (((n :+ m) :+ p) ~ (n :+ (m :+ p)) => t) -> t
assoc Zy my py t = t
assoc (Sy ny) my py t = assoc ny my py t
coerce :: Natty n -> Natty m -> Natty p -> Vec a ((n :+ m) :+ p) -> Vec a (n :+ (m :+ p))
coerce ny my py xs = assoc ny my py xs
更新
专业化很有指导意义assoc:
assoc' :: Natty n -> Natty m -> Natty p ->
(((n :+ m) :+ p) ~ (n :+ (m :+ p)) => Vec a (n :+ (m :+ p)))
-> Vec a (n :+ (m :+ p))
assoc' Zy my py t = t
assoc' (Sy ny) my py t = assoc ny my py t
coerce' :: Natty n -> Natty m -> Natty p -> Vec a ((n :+ m) :+ p) -> Vec a (n :+ (m :+ p))
coerce' ny my py xs = assoc' ny my py xs
Daniel Wagner 在评论中解释了发生的事情：
Or, to say it another way, you can read ((l ~ r) => t) -> t as, "given
a term that is well typed assuming that l ~ r, return that same term
from a context where we have proven l ~ r and discharged that
assumption".
让我们详细说明证明部分。
在 assoc' Zy my py t = t 的情况下 n 等于 Zy 因此我们有
((Zy :+ m) :+ p) ~ (Zy :+ (m :+ p))
减少到
(m :+ p) ~ (m :+ p)
这显然是同一性，因此我们可以解除该假设并且 return t。
在每个递归步骤中，我们维护
((n :+ m) :+ p) ~ (n :+ (m :+ p))
等式。所以当 assoc' (Sy ny) my py t = assoc ny my py t 方程变为
((Sy n :+ m) :+ p) ~ (Sy n :+ (m :+ p))
减少到
Sy ((n :+ m) :+ p) ~ Sy (n :+ (m :+ p))
由于 (:+) 的定义。而且由于构造函数是单射的
constructors_are_injective :: S n ~ S m => Vec a n -> Vec a m
constructors_are_injective xs = xs
等式变为
((n :+ m) :+ p) ~ (n :+ (m :+ p))
我们可以递归调用assoc'。
终于在coerce'的调用中统一了这两个词：
1. ((n :+ m) :+ p) ~ (n :+ (m :+ p)) => Vec a (n :+ (m :+ p))
2. Vec a ((n :+ m) :+ p)
显然 Vec a ((n :+ m) :+ p) 是 Vec a (n :+ (m :+ p)) 假设 ((n :+ m) :+ p) ~ (n :+ (m :+ p)).
I would have expected an equality proof to have a type more like this:
Natty x1 → ... → Natty xn → l :~: r
这是一个合理的选择。事实上，它在逻辑上等同于 Hasochism 论文中的那个：
{-# LANGUAGE GADTs, RankNTypes, TypeOperators, ScopedTypeVariables #-}
module Hasochism where
data l :~: r where
Refl :: l :~: l
type Hasoc l r = forall t. (l ~ r => t) -> t
lemma1 :: forall l r. Hasoc l r -> l :~: r
lemma1 h = h Refl
lemma2 :: forall l r. l :~: r -> Hasoc l r
lemma2 Refl t = t
在某种意义上，Hasoc l r是约束l ~ r.
的一种非谓语编码
Hasochistic 变体比 :~: 变体稍微容易使用，因为一旦您拥有
type family A a
-- ...
proof1 :: Proxy a -> Hasoc a (A a)
proof1 _ = -- ...
您可以像
一样简单地使用它
use1 :: forall a. [a] -> [A a]
use1 t = proof1 (Proxy :: Proxy a) t
相反，
proof2 :: Proxy a -> a :~: A a
proof2 _ = -- ...
你需要
use2 :: forall a. [a] -> [A a]
use2 t = case proof2 (Proxy :: Proxy a) of Refl -> t
我们有一些很好的答案，但作为肇事者，我想我会发表一些评论。
是的，这些引理有多个等效的表示。我使用的演示文稿就是其中之一，选择主要是务实的。这些天（在最近的代码库中），我甚至定义
-- Holds :: Constraint -> *
type Holds c = forall t . (c => t) -> t
这是一个消除器类型的例子：它抽象了它提供的内容（消除的动机）并且它需要你构建零个或多个方法（这里是一个）在更具体的情况下实现动机。阅读方式是向后。它说
If you have a problem (to inhabit any motive type t), and nobody else can help, maybe you can make progress by assuming constraint c in your method.
鉴于约束语言允许合取（又名元组），我们获得了编写形式为
的引理的方法
lemma :: forall x1 .. xn. (p1[x1 .. xn],.. pm[x1 .. xn]) -- premises
=> t1[x1 .. xn] -> .. tl[x1 .. xn] -- targets
-> Holds (c1[x1 .. xn],.. ck[x1 .. xn]) -- conclusions
甚至可能是某些约束、前提 p 或结论 c 具有等式形式
l[x1 .. xn] ~ r[x1 .. cn]
现在部署这么一个lemma，考虑填坑的问题
_ :: Problem
通过消除 lemma 来优化此 _，指定 目标 。 动机 来自眼前的问题。 方法（在Holds的情况下为单数）保持开放。
lemma target1 .. targetl $ _
并且方法孔不会改变类型
_ :: Problem
但是 GHC 会知道更多的东西，因此更有可能相信你的解决方案。
有时，对于什么是（约束）前提和什么是（数据）目标，需要做出约束与数据的选择。我倾向于选择这些以避免歧义（Simon 喜欢猜测 x1 .. xn，但有时需要提示）并促进 通过归纳 证明，这在目标上更容易（通常是类型级别数据的单例）而不是本地。
部署，对于方程式，当然可以转成数据类型展示，打个案例分析
case dataLemma target1 .. targetl of Refl -> method
事实上，如果你用 Dict 存在主义
装备自己
data Dict (c :: Constraint) :: * where
Dict :: c => Dict c
你可以一次做一堆
case multiLemma blah blah blah of (Refl, Dict, Dict, Refl) -> method
但是当最多只有一种方法时，消除器形式更加紧凑和可读。事实上，我们可以链接多个引理而无需向右滑动
lemma1 .. $
...
lemmaj .. $
method
如果您有这样一个包含两个或多个案例的消除器，我认为通常最好将其包装为一个 GADT，这样使用站点就可以用构造函数标签帮助标记每个案例。
无论如何，是的，关键是选择最紧凑的事实呈现方式，使我们能够扩展 GHC 的约束解决机制的范围，以便更多的东西只是类型检查。如果您与 Simon 发生争执，向隔壁的 Dimitrios 解释一下自己通常是一个很好的策略。
也许这是一个愚蠢的问题。这是来自 the Hasochism paper 的引述：
One approach to resolving this issue is to encode lemmas, given by parameterised equations, as Haskell functions. In general, such lemmas may be encoded as functions of type:
∀ x1 ... xn. Natty x1 → ... → Natty xn → ((l ~ r) ⇒ t) → t
我以为我理解了RankNTypes，但是我无法理解这个命题的最后一部分。我以 "given a term which requires l ~ r, return that term" 的形式非正式地阅读它。我确定这种解释是错误的，因为它似乎会导致循环：在证明本身得出结论之前我们不知道 l ~ r，所以我怎么能期望提供作为证明的假设 a哪个词需要那个？
我原以为等式证明的类型更像这样：
Natty x1 → ... → Natty xn → l :~: r
非正式地，"given a bunch of Nattys, return a proof of the proposition that l and r are equal"（使用 GHC 的 Data.Type.Equality）。这对我来说更有意义，并且似乎与您在其他依赖类型系统中所说的一致。我猜它等同于论文中的版本，但我正在努力将这两个版本放在一起。
简而言之，我很困惑。我觉得我缺少一个关键的见解。我应该如何阅读类型 ((l ~ r) => t) -> t?
I'm reading it as "given a term which requires
l ~ r, return that term"
是"given a term whose type contains l, return that term with all ls being substituted by rs in the type"（或者反方向r -> l）。这是一个非常巧妙的技巧，它允许您将所有 cong、trans、subst 和类似的东西委托给 GHC。
这是一个例子：
{-# LANGUAGE GADTs, DataKinds, PolyKinds, TypeFamilies, TypeOperators, RankNTypes #-}
data Nat = Z | S Nat
data Natty n where
Zy :: Natty Z
Sy :: Natty n -> Natty (S n)
data Vec a n where
Nil :: Vec a Z
Cons :: a -> Vec a n -> Vec a (S n)
type family (n :: Nat) :+ (m :: Nat) :: Nat where
Z :+ m = m
(S n) :+ m = S (n :+ m)
assoc :: Natty n -> Natty m -> Natty p -> (((n :+ m) :+ p) ~ (n :+ (m :+ p)) => t) -> t
assoc Zy my py t = t
assoc (Sy ny) my py t = assoc ny my py t
coerce :: Natty n -> Natty m -> Natty p -> Vec a ((n :+ m) :+ p) -> Vec a (n :+ (m :+ p))
coerce ny my py xs = assoc ny my py xs
更新
专业化很有指导意义assoc:
assoc' :: Natty n -> Natty m -> Natty p ->
(((n :+ m) :+ p) ~ (n :+ (m :+ p)) => Vec a (n :+ (m :+ p)))
-> Vec a (n :+ (m :+ p))
assoc' Zy my py t = t
assoc' (Sy ny) my py t = assoc ny my py t
coerce' :: Natty n -> Natty m -> Natty p -> Vec a ((n :+ m) :+ p) -> Vec a (n :+ (m :+ p))
coerce' ny my py xs = assoc' ny my py xs
Daniel Wagner 在评论中解释了发生的事情：
Or, to say it another way, you can read ((l ~ r) => t) -> t as, "given a term that is well typed assuming that l ~ r, return that same term from a context where we have proven l ~ r and discharged that assumption".
让我们详细说明证明部分。
在 assoc' Zy my py t = t 的情况下 n 等于 Zy 因此我们有
((Zy :+ m) :+ p) ~ (Zy :+ (m :+ p))
减少到
(m :+ p) ~ (m :+ p)
这显然是同一性，因此我们可以解除该假设并且 return t。
在每个递归步骤中，我们维护
((n :+ m) :+ p) ~ (n :+ (m :+ p))
等式。所以当 assoc' (Sy ny) my py t = assoc ny my py t 方程变为
((Sy n :+ m) :+ p) ~ (Sy n :+ (m :+ p))
减少到
Sy ((n :+ m) :+ p) ~ Sy (n :+ (m :+ p))
由于 (:+) 的定义。而且由于构造函数是单射的
constructors_are_injective :: S n ~ S m => Vec a n -> Vec a m
constructors_are_injective xs = xs
等式变为
((n :+ m) :+ p) ~ (n :+ (m :+ p))
我们可以递归调用assoc'。
终于在coerce'的调用中统一了这两个词：
1. ((n :+ m) :+ p) ~ (n :+ (m :+ p)) => Vec a (n :+ (m :+ p))
2. Vec a ((n :+ m) :+ p)
显然 Vec a ((n :+ m) :+ p) 是 Vec a (n :+ (m :+ p)) 假设 ((n :+ m) :+ p) ~ (n :+ (m :+ p)).
I would have expected an equality proof to have a type more like this:
Natty x1 → ... → Natty xn → l :~: r
这是一个合理的选择。事实上，它在逻辑上等同于 Hasochism 论文中的那个：
{-# LANGUAGE GADTs, RankNTypes, TypeOperators, ScopedTypeVariables #-}
module Hasochism where
data l :~: r where
Refl :: l :~: l
type Hasoc l r = forall t. (l ~ r => t) -> t
lemma1 :: forall l r. Hasoc l r -> l :~: r
lemma1 h = h Refl
lemma2 :: forall l r. l :~: r -> Hasoc l r
lemma2 Refl t = t
在某种意义上，Hasoc l r是约束l ~ r.
Hasochistic 变体比 :~: 变体稍微容易使用，因为一旦您拥有
type family A a
-- ...
proof1 :: Proxy a -> Hasoc a (A a)
proof1 _ = -- ...
您可以像
一样简单地使用它use1 :: forall a. [a] -> [A a]
use1 t = proof1 (Proxy :: Proxy a) t
相反，
proof2 :: Proxy a -> a :~: A a
proof2 _ = -- ...
你需要
use2 :: forall a. [a] -> [A a]
use2 t = case proof2 (Proxy :: Proxy a) of Refl -> t
我们有一些很好的答案，但作为肇事者，我想我会发表一些评论。
是的，这些引理有多个等效的表示。我使用的演示文稿就是其中之一，选择主要是务实的。这些天（在最近的代码库中），我甚至定义
-- Holds :: Constraint -> *
type Holds c = forall t . (c => t) -> t
这是一个消除器类型的例子：它抽象了它提供的内容（消除的动机）并且它需要你构建零个或多个方法（这里是一个）在更具体的情况下实现动机。阅读方式是向后。它说
If you have a problem (to inhabit any motive type
t), and nobody else can help, maybe you can make progress by assuming constraintcin your method.
鉴于约束语言允许合取（又名元组），我们获得了编写形式为
的引理的方法lemma :: forall x1 .. xn. (p1[x1 .. xn],.. pm[x1 .. xn]) -- premises
=> t1[x1 .. xn] -> .. tl[x1 .. xn] -- targets
-> Holds (c1[x1 .. xn],.. ck[x1 .. xn]) -- conclusions
甚至可能是某些约束、前提 p 或结论 c 具有等式形式
l[x1 .. xn] ~ r[x1 .. cn]
现在部署这么一个lemma，考虑填坑的问题
_ :: Problem
通过消除 lemma 来优化此 _，指定 目标 。 动机 来自眼前的问题。 方法（在Holds的情况下为单数）保持开放。
lemma target1 .. targetl $ _
并且方法孔不会改变类型
_ :: Problem
但是 GHC 会知道更多的东西，因此更有可能相信你的解决方案。
有时，对于什么是（约束）前提和什么是（数据）目标，需要做出约束与数据的选择。我倾向于选择这些以避免歧义（Simon 喜欢猜测 x1 .. xn，但有时需要提示）并促进 通过归纳 证明，这在目标上更容易（通常是类型级别数据的单例）而不是本地。
部署，对于方程式，当然可以转成数据类型展示，打个案例分析
case dataLemma target1 .. targetl of Refl -> method
事实上，如果你用 Dict 存在主义
data Dict (c :: Constraint) :: * where
Dict :: c => Dict c
你可以一次做一堆
case multiLemma blah blah blah of (Refl, Dict, Dict, Refl) -> method
但是当最多只有一种方法时，消除器形式更加紧凑和可读。事实上，我们可以链接多个引理而无需向右滑动
lemma1 .. $
...
lemmaj .. $
method
如果您有这样一个包含两个或多个案例的消除器，我认为通常最好将其包装为一个 GADT，这样使用站点就可以用构造函数标签帮助标记每个案例。
无论如何，是的，关键是选择最紧凑的事实呈现方式，使我们能够扩展 GHC 的约束解决机制的范围，以便更多的东西只是类型检查。如果您与 Simon 发生争执，向隔壁的 Dimitrios 解释一下自己通常是一个很好的策略。