where 子句中的类型推断

Question

如果我写

foo :: [Int]
foo = iterate (\x -> _) 0

GHC 高兴地告诉我 x 是一个 Int 而这个洞应该是另一个 Int。但是，如果我将其重写为

foo' :: [Int]
foo' = iterate next 0
  where next x = _

它不知道 x 的类型，也不知道洞是什么。如果我使用 let.

也会发生同样的情况

除了手动添加类型签名之外，还有什么方法可以恢复 where 绑定中的类型推断吗？

Answer 1

不是真的。此行为是设计使然，继承自形成 Haskell 类型系统最初灵感的理论 Hindley-Milner 类型系统。（该行为称为“let-polymoprhism”，可以说是 H-M 系统最关键的功能。）

粗略地说，lambda 的类型是“top-down”：当 type-checking 包含表达式（具体来说，当 type-checking iterate 的参数），然后使用此类型推断 x :: Int 和洞 _ :: Int.

的类型

相比之下，let 和 where 绑定变量的类型为“bottom-up”。 next x = _ 的类型首先被推断出来，与它在主表达式中的使用无关，一旦确定了该类型，就会根据它在表达式 iterate next 0 中的使用进行检查。在这种情况下，表达式 next x = _ 被推断为具有相当无用的类型 p -> t。然后，检查该类型在表达式 iterate next 0 中的使用，表达式 iterate next 0 将其特化为 Int -> Int（通过采用 p ~ Int 和 t ~ Int）并成功 type-checks.

在 languages/type-systems 中，如果没有这种区别（并忽略递归绑定），where 子句只是 lambda 绑定和应用的语法糖：

foo = expr1 where baz = bazdefn   ==>   foo = (\baz -> expr1) bazdefn

所以你可以做的一件事是将 where 子句“脱糖”到“等效”lambda 绑定：

foo' :: [Int]
foo' = (\next -> iterate next 0) (\x -> _)

当然，这种语法在身体上令人厌恶，但它确实有效。由于 lambda 的 top-down 类型，x 和空洞都被类型化为 Int.

where 子句中的类型推断

Type inference in where clauses

haskell

type-inference

ghc