haskell 缺少绑定时缺少多态推断

Question

类型是否通用化取决于是否存在绑定。这可能会导致意外失败。

这是正常行为吗，有什么原因吗？

{-# LANGUAGE RankNTypes #-}


data IFix0 f a   = IFix0 ( f (IFix0 f) a   ) | In0 a 


msfcata0_OK :: (forall r. (a -> r a) -> (r a -> a) -> f r a -> a) -> (forall z. IFix0 f z) -> a 
msfcata0_OK f = go where go (IFix0 x) = f In0 go x
                         go (In0 v)   = v


msfcata0_KO :: (forall r. (a -> r a) -> (r a -> a) -> f r a -> a) -> (forall z. IFix0 f z) -> a 
msfcata0_KO f  (IFix0 x) = f In0 (msfcata0_KO f) x  -- Couldn't match type ‘IFix0 f a’ with ‘forall z. IFix0 f z’
msfcata0_KO f   (In0 v)  = v

Answer 1

这里有一个非常小的重写，以更好地展示发生了什么。

{-# Language ScopedTypeVariables, RankNTypes #-}

data IFix0 f a = IFix0 (f (IFix0 f) a) | In0 a


msfcata0_OK
    :: forall f a.
       (forall r. (a -> r a) -> (r a -> a) -> f r a -> a)
    -> (forall z. IFix0 f z) -> a
msfcata0_OK f = go
  where
    go :: IFix0 f a -> a
    go (IFix0 x) = f In0 go x
    go (In0 v)   = v


msfcata0_KO
    :: forall f a.
       (forall r. (a -> r a) -> (r a -> a) -> f r a -> a)
    -> (forall z. IFix0 f z) -> a
msfcata0_KO f (IFix0 x) = f In0 (msfcata0_KO f) x -- line 21
msfcata0_KO f (In0 v)   = v

然后报错：

    • Couldn't match type ‘IFix0 f a’ with ‘forall z. IFix0 f z’
      Expected type: IFix0 f a -> a
        Actual type: (forall z. IFix0 f z) -> a
    • In the second argument of ‘f’, namely ‘(msfcata0_KO f)’
      In the expression: f In0 (msfcata0_KO f) x
      In an equation for ‘msfcata0_KO’:
          msfcata0_KO f (IFix0 x) = f In0 (msfcata0_KO f) x
    • Relevant bindings include
        x :: f (IFix0 f) a (bound at free.hs:21:22)
        f :: forall (r :: * -> *). (a -> r a) -> (r a -> a) -> f r a -> a
          (bound at free.hs:21:13)
        msfcata0_KO :: (forall (r :: * -> *).
                        (a -> r a) -> (r a -> a) -> f r a -> a)
                       -> (forall z. IFix0 f z) -> a
          (bound at free.hs:21:1)
   |
21 | msfcata0_KO f (IFix0 x) = f In0 (msfcata0_KO f) x -- line 21
   |                                  ^^^^^^^^^^^^^

那么让我们从查看错误消息开始。它说 (msfcata0_KO f) 的类型是 (forall z. IFix0 f z) -> a 但 f 的第二个参数需要是 IFix0 f a -> a。后一种类型是 r ~ IFix0 f 的特化，它将 In0 作为第一个参数传递给 f.

而且应该清楚的是，这些类型不匹配。 f 不能像使用 IFix0 f a -> a 类型的参数那样使用 (forall z. IFix0 f z) -> a 类型的参数。要对前者做任何事情，它需要传递给它一个多态值。要使用后者，它可以利用 a 在 f 的上下文中固定的事实，并传入一个与 a.[=55 的特定选择一起使用的值=]

那么 msfcata0_OK 有什么不同？好吧，当您创建本地绑定而不为其提供类型时，该类型是本地推断的。我在重写该函数时使用 ScopedTypeVariables 指定推断类型。（请注意，这意味着 f 和 a 类型绑定在顶级类型签名中。）此类型与兼容f，因此将 go 传递给 f 不是错误。

虽然这提出了一个明显的问题：如果 GHC 不能在 msfcata0_KO 中统一 (forall z. IFix0 f z) -> a 和 IFix0 f a -> a，为什么它可以在 msfcata0_OK 中统一？不同之处在于子类型化方向。在 msfcata0_OK 中，类型 IFix0 f a -> a 的表达式被生成为类型 (forall z. IFix0 f z) -> a 的值，这很好。在 msfcata0_KO 中，类型 (forall z. IFix0 f z) -> a 的表达式正在被需要类型 IFix0 f a -> a 的值的内容消耗，而这不起作用。多态值的子类型化方向取决于类型是正位还是负位。

从正面来说，具体类型是多态类型的子类型。您可以使用 (forall a. a) 类型的值，就好像它是 Int 或 Bool 类型的值一样，因此 (forall a. a) 是 Int 的超类型，Bool，以及任何其他具体类型。但在消极的立场上，这是相反的。 Int -> Bool类型的函数可以接受(forall a. a)类型的参数，但是(forall a. a) -> Bool类型的函数不能接受Int类型的参数，所以在负数位置(forall a. a) 是 Int.

的子类型

因此，回到高层次的原始问题 - 通过允许 GHC 从头开始为 go 推断类型，您改变了它统一更多多态和更少多态类型的位置。这导致子类型化关系朝着正确的方向工作，因此成功进行了类型检查。

haskell 缺少绑定时缺少多态推断

Lack of polymorphic inference in haskell when a binding is absent

polymorphism

haskell