读懂类型签名:多态与推断

签名的语法,五分钟

双冒号读作「的类型是」。从具体到抽象排一队:

answer  :: Int                  -- 一个整数
name    :: String               -- 字符串,其实是 [Char] 的别名
flags   :: [Bool]               -- 布尔列表
pair    :: (Int, String)        -- 二元组,两格类型可以不同
inc     :: Int -> Int           -- 函数:吃 Int 吐 Int
add     :: Int -> Int -> Int    -- 上一章讲过:Int -> (Int -> Int)
apply   :: (Int -> Int) -> Int -> Int   -- 第一个参数本身是函数

只有一条规则需要死记:-> 右结合,函数应用左结合。a -> b -> c 读 a -> (b -> c);想表达「参数是函数」必须自己加括号,像上面的 apply。

小写字母:无从作弊的多态

现在看真正有意思的。GHCi 里问几个标准库函数:

λ> :t head
head :: [a] -> a
λ> :t reverse
reverse :: [a] -> [a]
λ> :t map
map :: (a -> b) -> [a] -> [b]

小写的 a、b 是类型变量:调用方想代入什么类型都行,而且——关键——函数体不允许知道它是什么。这叫参数化多态(parametric polymorphism),对应你熟悉的泛型,但纪律更严:Java 里你可以 instanceof 偷看再分派,Kotlin 里可以 is 判断;Haskell 的类型变量没有任何此类后门。

没有后门,意味着签名会「泄露」实现。考一考:类型为 a -> a 的函数,有几种可能的实现?

答案:一种。它拿到一个完全未知类型的值,不能检查、不能构造新的(不知道怎么构造)、不能变换(没有可用的函数)——唯一合法的动作是原样奉还。所以 a -> a 必然是 id。同理推理一遍:a -> b -> a 只能返回第一个参数(它是 const);[a] -> [a] 不能碰元素本身,只能重排、复制、丢弃——所以看见这个签名,你不用读实现就知道它「顶多是 reverse/take/shuffle 这一类」。这个「从签名免费推出性质」的思路有个漂亮的名字:free theorems。

推断:你不写,编译器算

Java 写泛型要处处标注;Kotlin/TS 能推断局部变量,但函数参数必须写类型。Haskell 更进一步:整个程序一个类型都不写,编译器也能推出全部类型,而且推出的是最通用的那个。这套算法叫 Hindley-Milner(HM),1969/1978 年两次被独立发现,是 ML 语系(含 Haskell、OCaml、F#、Rust 的核心部分)的共同基石。

它的直觉出乎意料地朴素:把类型当未知数,把代码当方程组,解方程。手推一遍 compose f g x = f (g x):

-- 设 f :: t1, g :: t2, x :: t3,整体结果 :: t4
-- ① g x 要成立     ⇒ t2 必须是函数:t3 -> t5
-- ② f (g x) 要成立 ⇒ t1 必须是函数:t5 -> t6
-- ③ 结果就是 f (g x) ⇒ t4 = t6
-- 消元完毕,没有任何额外约束剩下:
compose :: (t5 -> t6) -> (t3 -> t5) -> t3 -> t6
-- 换上好看的字母,就是 (.) 的签名:(b -> c) -> (a -> b) -> a -> c

「要求两个类型相等」这一步叫合一(unification),整套推断的骨架叫 Algorithm W。下面这台推断台就是照着 Algorithm W 一行行实现的(不是查表,是真的在解方程),把上面的推导喂给它验证:

几个值得逐个试的输入:\f x -> f (f x)(为什么两个箭头里的类型被迫相同?);flip;map head;let id = \x -> x in (id 1, id True)——最后这个展示 let 多态:let 绑定的 id 被「泛化」成 a -> a,之后每次使用各自实例化,所以能同时用于 Int 和 Bool。把同样的逻辑写成 (\id -> (id 1, id True)) (\x -> x) 喂进去,它反而报错——lambda 参数是单态的,这是 HM 的著名边界,叫 let 与 lambda 的多态不对称。

实战读谱:三个真实签名

拿标准库的真实签名练手,按「先认变量,再找相同,最后猜行为」三步走:

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
-- ① 三个类型变量,互不约束
-- ② 函数参数吃 a 和 b、吐 c;两条列表恰好是 [a] [b];结果是 [c]
-- ③ 猜:按位置配对两条列表,用函数合并 ⇒ 对,就是它

takeWhile :: (a -> Bool) -> [a] -> [a]
-- 判断函数 + 列表进,列表出且元素类型不变
-- ⇒ 只能是「按条件筛选或截断」;名字告诉你是截断

maybe :: b -> (a -> b) -> Maybe a -> b
-- 一个「备用的 b」、一个「a 变 b 的办法」、一个「可能没有的 a」
-- ⇒ 有就转换,没有就用备用值。第 8 章的主力工具

三步走熟练后会产生一个副作用:你开始先想签名再写实现。「这个函数吃什么吐什么」想清楚的瞬间,实现常常只剩一种合理写法——这就是本章开头那句社区玩笑话的由来。

让编译器帮你写:类型洞

签名先行的工作流,GHC 给了官方外挂:类型洞(typed holes)。实现写不出来的部分,填一个下划线,编译器会告诉你「这个洞需要什么类型的东西」,还附赠候选清单:

λ> foldr _ 0 [1,2,3::Int]
<interactive>: error:
    • Found hole: _ :: Int -> Int -> Int
    • Valid hole fits include:
        (+) :: forall a. Num a => a -> a -> a
        (*) :: forall a. Num a => a -> a -> a
        subtract :: forall a. Num a => a -> a -> a ...

这是真实的日常工作方式:把函数骨架搭好,洞留着,按编译器的提示逐个填——类型系统从「检查官」变成「结对程序员」。Idris、Agda 把这条路走到了头(类型足够精确时,编辑器能自动填洞),而它的平民版你已经用过:IDE 里 .let/.also 后缀补全能猜你要什么,靠的同样是类型信息。

occurs check:防止类型吞掉自己

推断台里试 \x -> x x,你会得到一条著名的报错。手推就明白:设 x :: t1,「x 应用于 x」要求 t1 = t1 -> t2——一个类型等于「自己加个箭头」,展开就是 ((… -> t2) -> t2) -> t2,无穷无尽。合一算法里专门有一步检查「未知数是否出现在它要绑定的类型里」,叫 occurs check,发现了就报「无限类型」。GHC 的原版报错长这样:

λ> \x -> x x
<interactive>:1:7: error:
    • Occurs check: cannot construct the infinite type: t ~ t -> t1

既然能推断,为什么还手写签名?

打开任何真实 Haskell 项目,顶层函数几乎都有签名。不矛盾——推断是能力,签名是纪律:

文档:签名是最不会说谎的注释。边界:你想暴露的接口可能比推出来的更窄(推出 [a] -> Int,但你只想承诺 [User] -> Int)。报错质量:有签名时,类型错误在函数边界被拦下,信息精准;没签名时,错误会顺着推断传播到十万八千里外才爆炸。感受一下差别——同一个 bug(把年龄传成了字符串),有签名时:

λ> price "sixty"
<interactive>: error:
    • Couldn't match type ‘[Char]’ with ‘Int’
      Expected: Int   Actual: String
    • In the first argument of ‘price’

三行,指名道姓。没签名时,推断会「顺从」你的错误继续往下推,直到几层调用之外两个不相容的推断迎头相撞,报错里全是你没写过的类型变量。实践口径由此而来:顶层必写,局部随意——签名是防错误扩散的水密舱。