编写涉及 rank-n 类型的重写规则

Question

下面是我面临的一个非常相似的问题的简化版本。

考虑以下类型，函数f1:

{-# LANGUAGE RankNTypes #-}

newtype D t = D t deriving Functor
newtype T t = T { getT :: t }

f1 :: (forall t'. t' -> D t') -> T t -> D (T t)

注意 f1 实际上可以是 id，因为如果我们得到适用于所有 t 的传递函数，我们当然可以像这样专门化它：

f1 = id

现在让我们考虑 "inverse" 函数，f2:

f2 :: (T t -> D (T t)) -> t -> D t

这个"unspecialises"函数，可以实现如下：

f2 f x = getT <$> (f (T x))

我们可以组合f2和f1如下，这基本上是一个恒等函数：

g :: (forall t'. t' -> D t') -> t -> D t
g x = f2 (f1 x)

事实上，g 几乎等同于 id 函数，实际上我们可以定义 g 如下：

g = id

所以我们建立了f2 . f1 == id。

但是当我们写 f2 . f1 时，我怀疑 GHC 可能不会将其编译成 id，因为 f2 至少做了一些重要的工作。

我想为 f2 . f1 编写一个重写规则，这是我的尝试：

{-# RULES
"f2f1" forall x. f2 (f1 x) = g x
#-}

因为 g 可以定义为 id 我认为这可能不错。

但不幸的是，这无法编译。我怀疑这是由于 f1.

中排名较高的类型

我意识到如果我改变 f1 的类型签名如下：

f1 :: (t -> D t) -> T t -> D (T t)
f1 f x = T <$> f (getT x)

我可以写一个重写规则如下：

{-# RULES
"f2f1" forall x. f2 (f1 x) = x
#-}

但现在每当我使用 f1 时，它不仅仅是 id，而是更复杂一些。

有没有一种方法可以编写像 f2 . f1 == id 这样的重写规则，而不给 f1 一个非 id 风格的实现？

更多信息：

请注意，在我的实际问题中，D和T都不是新类型。

D 是任何 Functor f，而 T 实际上是 Coyoneda, following on from .

Answer 1

RULES 中的多态自由变量必须具有类型签名。只需使用

{-# RULES
"f2/f1" forall (x :: forall t. t -> D t). f2 (f1 x) = x
  #-}

Answer 2

HTNW 比我写得更快。但让我解决您的潜在问题。如果我定义

g :: (forall t'. t' -> D t') -> t -> D t
g x = f2 (f1 x)

并用-O2 -ddump-simpl -dsuppress-coercions -dsuppress-idinfo编译，我得到

Clinton.g1
  :: forall t_aGp.
     (forall t'_aqH. t'_aqH -> D t'_aqH) -> t_aGp -> D (T t_aGp)
Clinton.g1 =
  \ (@ t_aGp)
    (x_aqY :: forall t'_aqH. t'_aqH -> D t'_aqH)
    (x1_Xrz :: t_aGp) ->
    x_aqY @ (T t_aGp) (x1_Xrz `cast` ...)

-- RHS size: {terms: 1, types: 0, coercions: 16}
g :: forall t_aqG.
     (forall t'_aqH. t'_aqH -> D t'_aqH) -> t_aqG -> D t_aqG
g = Clinton.g1 `cast` ...

忽略代码生成中消失的类型参数和强制转换，这基本上是说

g f y = f y

这真是太好了。根据您的重写规则，我们得到

g :: forall t_aqG.
     (forall t'_aqH. t'_aqH -> D t'_aqH) -> t_aqG -> D t_aqG
g =
  \ (@ t_aGr) (x_aqY :: forall t'_aqH. t'_aqH -> D t'_aqH) ->
    x_aqY @ t_aGr

这基本上是

g f = f

更好？好吧，有点。它们实际上略有不同。没有重写规则，

g undefined `seq` () = ()

有了规则，

g undefined `seq` () = undefined

就个人而言，我根本不喜欢使用更改语义的重写规则，尤其是那些会降低定义性的规则，所以我永远不会写那个。

编写涉及 rank-n 类型的重写规则

Writing a rewrite rule involving rank-n types

haskell

ghc