用自己的证明丰富约束求解器

Question

我有以下类型系列：

{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE DataKinds #-}

data Nat = Z | S Nat
type family WrapMaybes (n :: Nat) (a :: *) :: *
type instance WrapMaybes Z a = a
type instance WrapMaybes (S n) a = Maybe (WrapMaybes n a)

这基本上按预期工作，例如 WrapMaybes (S (S Z)) Int ~ Maybe (Maybe Int)。

现在，显然（好吧，除了可能出于终止原因？！）以下通勤身份成立：WrapMaybes n (Maybe a) ~ Maybe (WrapMaybes n a)

GHC 本身无法推断属性，因此我正在寻找添加该公理的方法，最好是通过一些补充证明。到目前为止我想出的最好的是 coincident overlap in type families。但是建议的语法似乎不再起作用（type instance where 触发语法错误），所以我只用了这个：

type instance WrapMaybes n (Maybe a) = Maybe (WrapMaybes n a)

但这让 GHC 再次抱怨：

Conflicting family instance declarations:
  WrapMaybes 'Z a = a
  WrapMaybes n (Maybe a) = Maybe (WrapMaybes n a)

Conflicting family instance declarations:
  WrapMaybes ('S n) a = Maybe (WrapMaybes n a)
  WrapMaybes n (Maybe a) = Maybe (WrapMaybes n a)

所以：

有没有办法让提议的机制发挥作用？例如。如何消除语法错误？
重合重叠在 GHC Haskell 中仍然存在吗？
还有什么其他机制可以教 GHC 必要的公理？

Answer 1

重合类型家族重叠确实仍然存在于 GHC Haskell 中，如记录 here 所示。 GHC 8.4.3 仍然接受文档中的示例以及您链接到的博客 post。

但是，我认为重合重叠不会对您有所帮助，因为根据 GHC 使用的句法相等性检查，RHS 不（不能）相等。基本上，对于重合重叠类型家庭的想法是可行的，GHC 已经必须知道你想要 "prove".

的属性

要真正证明这一点，您需要在需要使用此事实时将您想要的类型相等性引入类型环境。一种方法是使用 :~: from Data.Type.Equality:

data a :~: b where  -- See Note [The equality types story] in TysPrim
  Refl :: a :~: a

这里的基本思想是，当您使用 Refl 构造函数创建 a :~: b 类型的值时，GHC 必须知道 a ~ b。当您稍后在此 Refl 构造函数上进行模式匹配时，您正在将这种相等性重新引入 GHC 的输入环境。您可以使用它来建立归纳证明。

但是，为了能够构建归纳证明，您将需要能够对 Nat 的值进行分支，而当它完全处于类型时您无法做到这一点等级。为了解决这个问题，我们可以引入一个 "singleton" GADT:

data SNat (n :: Nat) where
  SZ :: SNat 'Z
  SS :: SNat n -> SNat ('S n)

当您对类型 SNat 的值进行模式匹配时，由于 [=25= 的 GADT 结构，您将在类型环境中引入有关类型级自然值的信息]类型变量。

这意味着我们可以编写一个类型如下的函数：

wrapMaybeComm' :: forall n a. SNat n
               -> WrapMaybes n (Maybe a) :~: Maybe (WrapMaybes n a)

这里的想法是，如果你给它一个（价值级别的见证）一个类型级别的自然 n，它将 return 一个事实的见证 WrapMaybes n (Maybe a) 与 Maybe (WrapMaybes n a) 相同。当您对该见证进行模式匹配时，GHC 将确信事实是真实的，并能够使用它。

我们现在可以为 wrapMaybeComm' 写一个定义，它看起来非常像必要事实的归纳证明。基本情况是 0:

wrapMaybeComm' SZ = Refl

当 n = 0 时，GHC 立即能够看到 Maybe a ~ Maybe a。

在归纳的情况下，我们需要调用 wrapMaybeComm':

wrapMaybeComm' (SS m) = case wrapMaybeComm' @_ @a m of Refl -> Refl

Refl 上的模式匹配告诉 GHC WrapMaybes m (Maybe a) ~ Maybe (WrapMaybes m a)，其中 n ~ 'S m。有了这个，GHC 可以看到

  WrapMaybes n (Maybe a)
~ WrapMaybes ('S m) (Maybe a)            {- defn. of m -}
~ Maybe (WrapMaybes m (Maybe a))         {- defn. of WrapMaybes -}
~ Maybe (Maybe (WrapMaybes m (Maybe a))) {- IH -}
~ Maybe (WrapMaybes ('S m) (Maybe a))    {- defn. of WrapMaybes -}
~ Maybe (WrapMaybes n (Maybe a))         {- defn of m -}

所以知道右侧的 Refl 类型检查。

如果您不想到处携带 SNats，您可以通过定义 KnownNat class 像这样：

class KnownNat (n :: Nat) where
  getSNat :: SNat n
instance KnownNat 'Z where
  getSNat = SZ
instance KnownNat n => KnownNat ('S n) where
  getSNat = SS getSNat
wrapMaybeComm :: forall n a. (KnownNat n)
              => WrapMaybes n (Maybe a) :~: Maybe (WrapMaybes n a)
wrapMaybeComm = wrapMaybeComm' @n @a getSNat

要实际使用这个定理，只要你有一个 GHC 拒绝类型检查的表达式 e，因为它不知道与 n 和 a 的期望相等性，你可以改写 case wrapMaybeComm @n @a of Refl -> e 它应该可以工作。

这种方法可用于向 GHC 传授各种有趣的归纳事实。在一般情况下，GHC 当然不能知道所有相等的类型，因为这需要它能够决定一个非常强大的逻辑系统的任意定理，这是不可能的。然而，许多有趣的归纳定理的证明可以很容易地转换成这种风格，这种风格的一种变体（没有额外的单例工作）在依赖类型的语言中很常见。

旁注：要使用上述内容，您将需要一些额外的 GHC Haskell 扩展。

-XGADTs：SNat 单例必须是 GADT，以确保每个 SNat n 都有一个值（具体来说，带有 n SSs 应用于 SZ).
-XScopedTypeVariables：这是确保以正确的类型调用证明函数所必需的。
-XTypeOperators：给定的代码使用 Data.Type.Equality 中的 :~:，这是一个类型运算符。但是，可以使用不是类型运算符的等效定义（例如 Equal a b 而不是 a :~: b）。
-XAllowAmbiguousTypes：给定的定义具有 GHC 所称的模糊类型（需要额外类型签名的函数 and/or 可见类型应用程序来消除某些 tyvar 的歧义） .这可以通过使用更多 Proxy 参数来解决。
-XTypeApplications：这（@tyvar 语法）用于方便指定类型变量。但是，它应该可以替换为（更多annoying/verbose）显式类型注释。

用自己的证明丰富约束求解器

Enrich constraint solver with own proofs

haskell

ghc

type-families