Haskell 简明教程
Haskell 简明教程
学一门新语言，先弄清它组织代码的基本思路，比先记语法更省力。Haskell 的思路可以用三句话概括：
程序由值和函数构成，函数接收值、返回新的值。
Haskell 是静态强类型语言，每个函数都写明了它能处理什么类型的值。
为了让一个函数能处理“一类”类型，Haskell 提供了类型类，关键字是 class，但它相当于 Rust 的 trait、Java 的 interface、Python 的 typing.Protocol。
后面的章节，从列表、字符串到 Monoid、Functor、Monad，再到 JSON 和 HTTP 库，都是这三点的展开。本章先把整体图景讲清楚，细节留给后续章节。
Haskell 是纯函数式语言。在 C、Python、Java 里，程序是一串修改状态的语句；在 Haskell 里，程序是一组表达式，运行程序就是对表达式求值：
值不可变。x = 10 是定义，不是赋值，之后不能再改。要“修改”一个列表，就是用函数生成一个新列表。
函数是纯的。相同的输入必定得到相同的输出，函数不会暗中改全局变量、写文件或修改入参。
副作用也是值。读文件、打印这类操作由 IO 类型的值描述，交给运行时执行，见 IO 一章。
函数本身也是值，可以作为参数传递、作为结果返回、存进列表。不需要名字的函数用反斜杠写成匿名函数（Lambda）：
ghci> map (\x -> x * 2) [1, 2, 3]
[2,4,6]
\x -> x * 2 读作“接收 x，返回 x * 2 的函数”，反斜杠是希腊字母 λ 的简写。Haskell 的理论基础叫 Lambda 演算，它只有“定义函数”和“应用函数”两种操作。写 Haskell 不需要掌握这套理论，只需要记住它留下的一个重要特征，也就是下一节的柯里化。
在 Haskell 中，每个函数都只接受一个参数。多参数函数其实是“接收第一个参数，返回一个接收剩余参数的函数”。下面两种写法完全等价：
add :: Int -> Int -> Int
add x y = x + y
add' :: Int -> Int -> Int
add' = \x -> \y -> x + y
类型签名里的箭头是右结合的，Int -> Int -> Int 就是 Int -> (Int -> Int)：接收一个 Int，返回一个 Int -> Int 的函数。调用 add 1 2 的过程是先把 1 代进去，再把 2 代进去：
add 1 2
= (\x -> \y -> x + y) 1 2
= (\y -> 1 + y) 2
= 1 + 2
= 3
这种机制叫柯里化（Currying），得名于逻辑学家 Haskell Curry，这门语言的名字也来自他。它最直接的好处是部分应用：只传一部分参数，就得到一个新函数：
ghci> :t add 1
add 1 :: Int -> Int
ghci> map (add 1) [1, 2, 3]
[2,3,4]
add 1 不需要额外的语法就能当作单参数函数传给 map。这也解释了 Haskell 标准库的参数顺序习惯：配置类参数放前面，被处理的数据放最后，例如 map f xs、filter p xs、take n xs，方便先固定前面的参数得到一个专用函数。
同样的道理，如果一个函数定义的两边最后都是同一个参数，就可以把它消掉：
addOne x = add 1 x
-- 两边同时去掉 x，含义不变：
addOne = add 1
这种不写出参数的写法叫无点风格（Pointfree Style），在函数组合一节会经常看到。
Haskell 在编译期检查每个函数调用的类型是否匹配，而且没有隐式转换。not 只接受 Bool，传一个数字进去不能编译：
ghci> :t not
not :: Bool -> Bool
ghci> not 3
error: • No instance for ‘Num Bool’ arising from the literal ‘3’
大部分类型签名可以省略，编译器会自动推断。但习惯上顶层函数都写签名，签名本身就是最准确的文档。
有些函数不关心元素是什么类型，签名里用小写字母表示“任意类型”，这叫参数多态：
length :: [a] -> Int -- 任意类型的列表都能求长度
reverse :: [a] -> [a]
参数多态的代价是函数对 a 一无所知。length 能数元素个数，但不能比较两个元素是否相等，也不能把元素打印出来，因为不是所有类型都支持这些操作。
于是出现了两个极端：not 只能处理 Bool，太窄；length 能处理任意类型，但什么都不能做。实际需要的往往是中间状态：“任何能比较相等的类型”“任何能排序的类型”“任何能转成字符串的类型”。这正是类型类要解决的问题。
看 elem 的签名（这里把它简化为只作用于列表）：
elem :: Eq a => a -> [a] -> Bool
=> 左边的 Eq a 是约束，意思是“a 可以是任何类型，只要它是 Eq 的实例”。Eq 就是一个类型类，它描述“能比较相等”这种能力。Int、Char、String 都是 Eq 的实例，所以 elem 能用在它们身上；函数类型不是 Eq 的实例，所以不能在函数列表里查找某个函数。
定义类型类的关键字是 class，这个名字很容易误导。它和 Java、Python 的 class 没有关系，没有字段，没有对象，也不能实例化出值。Haskell 里定义数据的是 data，定义能力的是 class，把两者连起来的是 instance。
小技巧
如果你熟悉其他语言：
Rust：class 几乎就是 trait，instance Eq Color 就是 impl PartialEq for Color。Rust 的 trait 本来就是参考 Haskell 类型类设计的，默认方法、超 trait（trait Ord: Eq）、为别人的类型实现自己的 trait，这些概念一一对应。
Java：class 相当于 interface，比如 Ord 对应 Comparable<T>。接口里的 default 方法对应类型类的默认实现，interface B extends A 对应类型类的继承。最大的区别是 Java 必须在定义类时写 implements，无法让 String 这类已有的类型事后实现你的接口，Haskell 的 instance 可以单独写在任何地方。
Python：class 相当于 typing.Protocol，比如 Eq 对应“定义了 __eq__ 的类型”。Protocol 是结构化匹配的，方法对上就算实现；Haskell 必须显式写 instance，而且在编译期检查，不会运行到一半才发现某个方法不存在。
标准库中 Eq 的定义是这样的：
class Eq a where
(==), (/=) :: a -> a -> Bool
x == y = not (x /= y)
x /= y = not (x == y)
{-# MINIMAL (==) | (/=) #-}
两个方法都有默认实现，各自定义为另一个的取反。MINIMAL 标注说明实例只需要实现 == 或 /= 中的一个，另一个自动得到。为一个颜色类型实现 Eq：
data Color = Red | Green | Blue
instance Eq Color where
Red == Red = True
Green == Green = True
Blue == Blue = True
_ == _ = False
只写了 ==，但 /= 已经可以用了。更重要的是，标准库里所有以 Eq a => 为约束的函数也都可以用了：
ghci> import Data.List (nub, sort)
ghci> Red /= Green
True
ghci> elem Blue [Red, Blue]
True
ghci> nub [Red, Red, Green] == [Red, Green]
True
这是 Haskell 类型类的典型收益：实现一两个核心方法，换来类内的其余方法，再换来整个标准库里基于这个类型类写好的函数。Eq 换来的有 elem、lookup、nub、group；后面会看到，Monoid 换来 mconcat 和 foldMap，Foldable 换来 sum、length、maximum 等一大批函数，Monad 换来 do 记号和 mapM、forM。
实际上像 Color 这样的简单类型，连 == 都不用手写，加一行 deriving (Eq) 让编译器生成即可。手写实例一般只在需要特殊语义时出现。
其他语言的接口通常只要求方法签名对得上。Haskell 的类型类还约定了方法的行为，这些约定叫法则（Laws）。Eq 的法则就是数学上“相等”的性质：x == x 总成立；x == y 和 y == x 结果相同；x == y 且 y == z 时 x == z。
编译器不检查法则，但标准库的函数都假设法则成立。违反了，代码能编译，结果却会出错。下面这个“近似相等”看起来很合理，却破坏了传递性：
newtype Approx = Approx Double deriving Show
instance Eq Approx where
Approx a == Approx b = abs (a - b) < 0.1
0 等于 0.08，0.08 等于 0.16，但 0 不等于 0.16。于是去重的结果取决于元素的排列顺序：
ghci> Approx 0 == Approx 0.08
True
ghci> nub [Approx 0, Approx 0.08, Approx 0.16]
[Approx 0.0,Approx 0.16]
ghci> nub [Approx 0.08, Approx 0, Approx 0.16]
[Approx 8.0e-2]
标准库自己也有一个著名的反例，浮点数的 NaN 不等于自身，所以 elem nan [nan] 返回 False。这也是为什么在 Haskell 里说“某类型是某类型类的实例”时，意思不只是“实现了这几个函数”，而是“满足这组行为”。后面每介绍一个类型类，都会同时给出它的法则。
类型类可以要求它的实例先是另一个类型类的实例。Ord（能排序）的定义开头是：
class Eq a => Ord a where
compare :: a -> a -> Ordering
-- (<)、(<=)、max、min 等都有默认实现
{-# MINIMAL compare | (<=) #-}
Eq a => 表示“要成为 Ord，先得是 Eq”。这和 Rust 的 trait Ord: Eq、Java 的 interface B extends A、Python 中一个 Protocol 继承另一个 Protocol 是同一个意思。实现 Ord 同样只需要 compare，然后 <、max、sort、maximum 都能用，还可以作为 Map 的键：
data Version = Version Int Int
instance Eq Version where
Version a b == Version c d = a == c && b == d
instance Ord Version where
compare (Version a b) (Version c d) = compare (a, b) (c, d)
instance Show Version where
show (Version a b) = show a ++ "." ++ show b
ghci> sort [Version 1 10, Version 1 2, Version 0 9]
[0.9,1.2,1.10]
ghci> Version 1 2 < Version 1 10
True
按版本号的数字排序，1.10 排在 1.2 后面，而按字符串排序会得到相反的结果。
标准库里的主要类型类形成几条继承链，本书的大部分章节就是沿着它们展开的：
graph LR
Eq --> Ord
Semigroup --> Monoid
Functor --> Applicative --> Monad
Foldable --> Traversable
Functor --> Traversable
完整的层级图和各类型的实例表在类型类一章。
有了上面的框架，后面的内容大多可以归到同一个模式里：
读签名先看约束。sort :: Ord a => [a] -> [a] 说明排序只需要元素能比较；mapM :: (Traversable t, Monad m) => ... 说明它对任何可遍历的容器、任何单子都适用。约束告诉你函数体里能对值做什么。
每个抽象都是一个类型类。Monoid、Functor、Applicative、Monad、Foldable、Traversable 这些名字听起来抽象，但每一个都可以按同样的四个问题来学：要实现哪几个方法，哪些方法有默认实现，要遵守什么法则，实现之后能用哪些现成的函数。
很多运算符是类型类的方法。==、<、+、<>、<$>、<*>、>>= 都属于某个类型类，同一个运算符在不同类型上的具体行为由实例决定。在 GHCi 里用 :i 可以查到一个运算符属于哪个类型类，以及有哪些实例。
第三方库也用同一套机制。aeson 定义了 ToJSON、FromJSON，你的类型实现了它们，所有接受 JSON 的函数就都能用。
Haskell 程序由不可变的值和纯函数构成，函数本身也是值，匿名函数写作 \x -> ...。
每个函数只接受一个参数，多参数函数是柯里化的结果，因此可以随时部分应用。
强类型让每个函数写明它处理的类型；参数多态处理任意类型，但对值一无所知。
类型类介于两者之间，描述“一类类型共有的能力”。class 应理解为 Rust 的 trait、Java 的 interface、Python 的 Protocol，instance 是具体类型对它的实现。
类型类通常只需实现最少的几个方法，其余有默认实现，还能换来大量以它为约束的库函数。
实例除了签名正确，还必须遵守法则，库函数都以法则成立为前提。
类型类之间有继承关系，如 Ord 要求先是 Eq，Monad 要求先是 Applicative。