haskell奇怪的类型错误时,使用无点表示法与(.)运算符

jv4diomz  于 9个月前  发布在  其他
关注(0)|答案(1)|浏览(60)

有人能解释一下为什么这个代码不工作吗?

import GHC.Exts (build)
data List a = Nil | Cons a (List a)

toLambdaList :: List t0 -> (t0 -> t1 -> t1) -> t1 -> t1
toLambdaList Nil cons nil = nil
toLambdaList (x `Cons` xs) cons nil = x `cons` (toLambdaList xs cons nil)
fromList :: List a -> [a]
fromList = build . toLambdaList

我得到的错误是这样的:

Couldn't match type: forall b. (a -> b -> b) -> b -> b
               with: (t1 -> t20 -> t20) -> t20 -> t20

(GHCi版本9.0.2)
令人惊讶的是,如果我只是用\a -> build $ toLambdaList a替换build . toLambdaList,新代码突然就可以工作了:

import GHC.Exts (build)
data List a = Nil | Cons a (List a)

toLambdaList :: List t0 -> (t0 -> t1 -> t1) -> t1 -> t1
toLambdaList Nil cons nil = nil
toLambdaList (x `Cons` xs) cons nil = x `cons` (toLambdaList xs cons nil)
fromList :: List a -> [a]
fromList a = build $ toLambdaList a

我试过删除类型声明,但这没有帮助。

m528fe3b

m528fe3b1#

这不起作用的原因(自GHC 9以来)是forall现在在类型中被更字面地处理。在你的情况下,
在你的例子中,编译器会抱怨它不能匹配这些类型:

Expected: ((a -> t1 -> t1) -> t1 -> t1) -> [a]
     Actual: (forall b. (a -> b -> b) -> b -> b) -> [a]

它们看起来确实不同,但您可能认为GHC只是将实际类型中的forall b示例化为t1。然后类型会匹配。这就是GHC在版本9之前所做的,现在可以在GHC 9.2和更高版本中使用名为DeepSubsumption的新扩展重新启用。
在某些情况下,GHC仍然示例化forall 'd变量,但当它位于函数箭头的左侧下方时(如在您的情况下),则不会示例化。
做出这一改变的主要原因是:

  • 它简化了类型检查器。
  • 它可以正确地支持非 predicate 类型。
  • 这些示例化会悄悄地影响运行时行为。

有关更多详细信息,请参阅Simplify Subsumption proposal
解决这个问题的一种方法是使用ImpredicativeTypes(在某些情况下可以替代深度包容)并稍微更改toLambdaList的类型:

{-# LANGUAGE ImpredicativeTypes #-}

import GHC.Exts (build)
data List a = Nil | Cons a (List a)

toLambdaList :: List t0 -> forall t1. (t0 -> t1 -> t1) -> t1 -> t1
toLambdaList Nil cons nil = nil
toLambdaList (x `Cons` xs) cons nil = x `cons` (toLambdaList xs cons nil)
fromList :: List a -> [a]
fromList = build . toLambdaList

要理解为什么这样做,我们需要看看(.)的类型:

(.) :: forall a b c. (b -> c) -> (a -> b) -> a -> c

使用ImpredicativeTypes,我们可以将b示例化为forall t1. (t0 -> t1 -> t1) -> t1 -> t1ab像往常一样分别示例化为List a[a](.)的特殊类型则变为:

(.) :: forall a t0.
  ((forall t1. (t0 -> t1 -> t1) -> t1 -> t1) -> [a]) ->
  (List a -> forall t1. (t0 -> t1 -> t1) -> t1 -> t1) ->
  List a -> [a]

现在第一个参数的类型匹配build的类型,第二个参数的类型匹配toLambdaList的类型。

相关问题