Haskell使用无点式(.)运算符时遭遇异常类型错误

报错代码示例 #

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）

可运行的代码修改 #

将fromList改为显式lambda定义后，代码正常运行：

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

原因解析 #

核心问题出在函数组合符.的类型推断逻辑与build的多态类型特性不兼容：

1. build的类型为forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]，它要求参数是一个Rank-2类型的函数——也就是包含内层forall、对任意类型b都能适配的多态函数。
2. toLambdaList的类型是List t0 -> (t0 -> t1 -> t1) -> t1 -> t1，当它接收List a时，返回的(a -> t1 -> t1) -> t1 -> t1在默认推断中会被绑定为单态类型（GHC会尝试固定t1为某个具体类型），这和build需要的“对任意b都多态”的要求不匹配。
3. 函数组合符.的类型推断会优先给toLambdaList的返回值绑定单态类型，导致无法匹配build的Rank-2参数要求。
4. 而显式lambda写法\a -> build $ toLambdaList a会让GHC先保留toLambdaList a的多态性（即保留forall b的量化），再传递给build，完美满足了build的参数类型要求。

简单来说，.的类型推断无法自动处理需要保留内层多态性的场景，显式lambda则能引导GHC正确识别toLambdaList a的多态特性。

内容的提问来源于stack exchange，提问作者eugene