绕过预测多态性的方法

Question

我不熟悉 Haskell 中一些更复杂的类型构造，并且一直在胡思乱想。我目前一直在尝试获得一个我认为应该用于类型检查的功能。

以如下代码为例：

{-# LANGUAGE RankNTypes   #-}
{-# LANGUAGE TypeFamilies #-}

class X a where
  data Y a
  z :: Y a -> Int

data D1 = D1
instance X D1 where
  data Y D1 = YD1
  z _ = 1

data D2 = D2
instance X D2 where
  data Y D2 = YD2
  z _ = 2

sumZ :: X a => [Y a] -> Int
sumZ = foldl' sumFn 0
  where sumFn = flip ((+) . z)

我希望a = sumZ [YD1, YD2] 进行类型检查。这（显然）不起作用，因为 a 类型变量被第一个 YD1.

固定

我知道我应该在这里使用更高等级的类型，所以我尝试了这个：

sumZ' :: [(forall a. X a => Y a)] -> Int
sumZ' = foldl' sumFn 0
  where sumFn = flip ((+) . z)

但是，当我尝试编译它时，我运行变成了 "impredicative polymorphism":

     • Illegal polymorphic type: forall a. X a => Y a
       GHC doesn't yet support impredicative polymorphism
     • In the type signature: sumZ' :: [(forall a. X a => Y a)] -> Int
    |
 48 | sumZ' :: [(forall a. X a => Y a)] -> Int
    |          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

读了一些书后，我发现传统的解决方案是将值包装在 newtype 中以绕过谓词多态性。

newtype Wrap = Wrap { unWrap :: forall a. X a => Y a }

sumZ'' :: [Wrap] -> Int
sumZ'' = foldl' sumFn 0
  where
    sumFn acc (Wrap v) = acc + (z v)

不幸的是，这似乎也不起作用。编译失败并显示此消息：

     • Ambiguous type variable ‘a0’ arising from a use of ‘z’
       prevents the constraint ‘(X a0)’ from being solved.
       Probable fix: use a type annotation to specify what ‘a0’ should be.
       These potential instances exist:
         instance X D1
           -- Defined at ...
         instance X D2
           -- Defined at ...
     • In the second argument of ‘(+)’, namely ‘(z v)’
       In the expression: acc + (z v)
       In an equation for ‘sumFn’: sumFn acc (Wrap v) = acc + (z v)
    |
 64 |     sumFn acc (Wrap v) = acc + (z v)
    |                                 ^^^

最后，我的问题：

为什么标准 "wrapping" 技术在这种情况下不起作用？在检查 v 的类型时，我发现它的类型是 forall a. X a => Y a，对我来说这似乎应该有效。
如何让 a = sumZ [YD1, YD2] 工作？我做错了吗？

Answer 1

事实 v :: forall a. X a => Y a 正是应用 z 不起作用的原因。

里面的forall就是说v可以是任意类型，你选哪个。为了说明这一点，请与此进行比较：

empty :: forall a. [a]
empty = []

有值empty可以是任何类型，消费者选择哪种类型。这就是 forall 在这里的意思。我希望这是显而易见的。

您的值也是如此 v：它可以是任何类型，您可以选择。但是在您的代码中您没有选择类型：您正在应用 z，它本身可以与任何类型一起使用，因此 v 的类型仍然未被选择。这正是编译器在抱怨 "ambiguous type variable a0".

时告诉您的内容

要完成这项工作，您应该将 forall 放在 Wrap 的另一边：

data Wrap = forall a. X a => Wrap (Y a)

（您需要启用 GADTs 扩展才能允许这样做）

这样，谁构造一个Wrap就必须选择具体的类型a。另一方面，当你进行模式匹配时，你会得到构造值的人选择的类型 a。

绕过预测多态性的方法

Ways around impredictive polymorphism

polymorphism

haskell

impredicativetypes