haskell - 使用 rank-N 类型翻转

Question

我有以下 Rank 2 功能:

polyOn :: (f a -> f b -> c) -> (forall k . k -> f k) -> a -> b -> c
polyOn bifunc func x y =
  bifunc (func x) (func y)

我想翻转它

flippedPolyOn :: (forall k . k -> f k) -> (f a -> f b -> c) -> a -> b -> c
flippedPolyOn =
  flip polyOn

但 ghc 提示:

    • Couldn't match type ‘k0 -> f k0’ with ‘forall k. k -> f k’
      Expected type: (f a -> f b -> c) -> (k0 -> f k0) -> a -> b -> c
        Actual type: (f a -> f b -> c)
                     -> (forall k. k -> f k) -> a -> b -> c
    • In the first argument of ‘flip’, namely ‘polyOn’
      In the expression: flip polyOn
      In an equation for ‘flippedPolyOn’: flippedPolyOn = flip polyOn
    • Relevant bindings include
        flippedPolyOn :: (forall k. k -> f k) -> (f a -> f b -> c) -> a -> b -> c
          (bound at XXXXXX:75:1)
   |
76 |   flip polyOn
   |        ^^^^^^

所以看起来 ghc 在某些时候专门化了 forall k. k -> f k到 k 的特定值(它称之为 k0 )。
为什么 ghc 会这样做？这种特化可以避免吗？

Answer 1

GHC < 9
问题是 GHC < 9.x 不支持指示性多态性。本质上，您要做的是实例化

flip :: (a0->b0->c0) -> b0->a0->c0

这样:

a0 ~ (f a -> f b -> c)
b0 ~ (forall k . k -> f k)
c0 ~ a -> b -> c

a0 的类型推断没有问题和 c0 ，但不允许选择 b0以这种方式。
事实上，在不支持隐含多态性的情况下，类型变量如 b0只能用单型(没有 forall 的类型)实例化。
我们需要内联 flip使这项工作

flippedPolyOn x y = polyOn y x

GHC >= 9
默认情况下，在 GHC 9 中，我们仍然会收到类型错误，但有更好的错误消息，指出了不可预测性问题:

  Cannot instantiate unification variable `b0'
  with a type involving polytypes: forall k. k -> f k

我们可以通过打开指示性类型来对您的代码进行类型检查:

{-# LANGUAGE RankNTypes, ImpredicativeTypes #-}