RWH 就是《Real World Haskell》。这次是我第二次阅读它，因为第一次半途而废。
现在，已经前四章读完，其中前三章讲的是 Haskell 的一些非常基础的语法，例如基本类型、用户自定义类型、函数的定义与应用、条件判断语句、模式匹配等内容，这部分内容结合书中的小示例很容易理解。
第四章，其标题貌似是要概述式的讲述 FP 的思想和方法，实际上内容严重的跑题。我觉得读完这一章，只要能够理解下面这几个知识点就足够了，不必在意能否理解作者提供的那些自以为是的示例。
其中的难点是如何使用尾递归实现迭代以及惰性计算的陷阱，本文对它们略微总结一下。
在 C 语言中，我们会经常写下面这样的代码：
int n = 10;
for (int i = 0; i < n; i++) {
}
且不论 Haskell 如何实现它，先来看 C 语言如何用递归来实现它。我们先用一个比较简单的尾递归函数来实现上述循环结构的外壳，即：
void loop (int i, int n)
{
if (i < n)
loop (i + 1, n);
}
然后调用这个函数：
loop (0, 10);
这样，这个空壳的 for 循环结构便被转化为递归函数形式。建议在编译上述 loop 代码时，使用 gcc 的 -O2 选项，这样会启用尾递归优化。
现在，我们使用 Haskell 来写这个 loop 函数：
loop i n | i < n = loop (i + 1) n
然后应用这个函数：
loop 0 10
就是这么的简单。
下面我们来看怎么利用这个循环结构对一个数组进行求和。
先给出 C 语言的 for 循环代码：
int a[5] = {1, 2, 3, 4, 5}
int sum = 0;
for (int i = 0; i < 5; i++) {
sum += a[i];
}
然后我们再写出 C 语言版本 loop 函数：
int loop (int i, int n, int *a, int sum)
{
if (i < n)
loop (i + 1, n, a, sum + a[i]);
return sum;
}
然后调用这个函数：
int a[5] = {1, 2, 3, 4, 5};
int sum = loop (0, 5, a, 0);
同理，我们也可以写出 Haskell 版本的 loop 函数：
loop i n a sum | i < n = loop (i + 1) n a (sum + a !! i) | otherwise = sum
然后调用它：
loop 0 5 a 0
不过这个 loop 函数的 Haskell 版本不够高效，因为我们使用了 a !! i 这个表达式获取列表元素。虽然 a !! i 在功能上等同于 C 语言的 a[i]，但实际上 !! 这个函数是从列表首元素开始一直遍历到第 i + 1 个元素才停止。效率更高一些的版本应该是：
loop i n x:xs sum | i < n = loop (i + 1) n xs (sum + x) | otherwise = sum
不过，既然我们已经利用了列表构造式以及模式匹配，单纯对于列表元素的求和问题，可以改进的再彻底一些，即：
loop [] sum = sum loop x:xs sum = loop xs (sum + x)
如果你能够毫无障碍的理解以上内容，那么 RWH 第四章的一多半内容理解起来就没啥障碍，只要稍微有点耐心即可。
Haskell 比较有名的一个特性就是惰性求值。用来展示 Haskell 惰性求值威力的一个有名的例子是生成无限长的 Fibonacci 数列：
fib = 1:1:zipWith (+) fib (tail fib)
其中的玄机就是利用一个 Fibonacci 数列 [F(0), F(1), ... , F(n-2)] 与 [F(1), F(2), ..., F(n-1)] 求和，得到 [F(2), F(3), ..., F(n)]，再将 F(0) 与 F(1) 添加到所得结果的首部，这样就得到 [F(0), F(1), ..., F(n)]。由于 n 值可以无限大，所以 fib 函数所得结果就是一个无限长的 Fibonacci 数列。我们可根据自己的需要从这个无线长的数列中取得对应位置的元素。例如要得到 Fibonacci 数列的第 10 个元素，只需 fib !! 10 即可。
但是惰性计算会导致一些递归函数出现栈溢出，即便是尾递归函数。
与命令式语言的递归函数发生栈溢出的情况不同，Haskell 的函数是没有调用栈的，但是在将一个表达式求值至 WHNF 的过程中需要用到内部栈，并且可能会发生栈溢出。
可能你会问，将一个表达式求值至 WHNF，这是什么意思？好吧，我就将我查询到的一点知识现学现卖了。
看下面这个表达式：
[1,2,3]
很简单的一个列表构造式。Haskell 编译器在遇到这个表达式时，会把它当成一个未被求值的表达式，术语称之为“Thunk”，然后不会理睬它。如果这个表达式遇到了诸如 print 这样的函数：
print [1,2,3]
那么 Haskell 编译器就只好对它进行求值，这就是所谓的惰性求值。实际上，Haskell 编译器在求值的过程中依然非常的不积极，它会将这个表达式的求值分成下面的过程：
第 0 步：Thunk 第 1 步：1:Thunk 第 2 步：1:2:Thunk 第 3 步：1:2:3:Thunk 第 4 步：1:2:3:[]
从高处看，这个过程可用人类的语言描述为从一个 Thunk 到 WHNF 再到 NF 的过程，其中第 1、2、3 步的表达式都是 WHNF，第 4 步所得表达式是 NF。
我们可以粗俗的将 Thunk 视为未求值的表达式，WHNF 是表达式部分被求值，而 NF 是表达式完全被求值。
将一个 Thunk 求值至 WHNF 时，如果它会触发许多其它的 Thunk 被求值为 WHNF，那么就可能会导致栈溢出。例如 Haskell 标准库提供的列表左折叠函数 foldl，它在处理较长的列表时，便会生成一个很庞大的 Thunk，将这个 Thunk 求值为 WHNF 表达式时会引发一连串的子 Thunk 要被求值为 WHNF，这时便会出现栈溢出的情况。事实上，右折叠函数 foldr 也可能会出现这种情况。
Haskell Wiki 的栈溢出页面详细的讨论了 foldl、foldr 的陷阱，并总结了以下使用经验：
使用 foldl' 就可以跳过惰性求值的陷阱？当然不尽然啊，遇到更深的陷阱的时候，foldl' 也救不了你，例如下面这个例子：
otherTrap xs = foldl' (\(acc, len) x -> (acc+x, len+1)) (0,0) xs
要认识这个更深的陷阱，我们需要了解一下匿名函数与 seq 函数。
匿名函数就是在一个函数的定义中临时的定义的函数，被作为高阶函数的参数使用。例如，上一节最后给出的 otherTrap 函数，其定义中便存在一个匿名函数：
\(acc, len) x -> (acc+x, len+1)
这个函数接受两个参数，即 (acc, len) 与 x。-> 符号右侧的部分是函数体。
我们将这个匿名函数作为 foldl' 的参数，便有了上面 otherTrap 函数的定义。
我们再来了解一下 seq 函数，它的签名是：
seq :: a -> b -> b
字面上来看，seq 接受两个参数，并且返回第二个参数。它的实际功能是：将第一个参数求值为 WHNF，返回第二个参数。
foldl' 函数的定义便利用了 seq：
foldl' _ zero [] = zero
foldl' step zero (x:xs) =
let new = step zero x
in new `seq` (foldl' step new xs)
主要看最后那行代码：
new `seq` (foldl' step new xs)
seq 会将它接受的第一个表达式 new 求值至 WHNF，实际效果就是对 new 所指代的 step zero x 这个表达式进行求值。这样，在 seq 所返回的第二个表达式 foldl' step new xs 可以坐享 new 表达式的求值结果。
foldl' 就是 seq 实现递归过程中对 Thunk 的逐步缩减，从而维持常量的栈空间，而不是 foldl 的线性栈空间。
理解了上面的知识，我们就可以探索上一节最后所说的那个更深的陷阱：
otherTrap xs = foldl' (\(acc, len) x -> (acc+x, len+1)) (0,0) xs
现在我们对这个陷阱进行初步的探索。按照上面 foldl' 的定义，new 此刻指代的表达式是：
(\(acc, len) x -> (acc+x, len+1)) (0, 0) x
这是匿名函数应用表达式，seq 会对这个表达式进行求值，使之成为 WHNF，求值结果是：
(0+x, 0+1)
可能我们认为求值结果应当是：
(x, 1)
因为 WHNF 的准确定义是：如果一个表达式，其最外层是值构造子或匿名函数定义式，就表示这个表达式已经处于 WHNF 中。
(0+x, 0+1) 这个表达式的最外层是元组构造子，seq 准备对它进一步求值时，发现它已经是 WHNF 了，便停止求值。
对于 otherTrap 函数而言，伴随着 foldl' 的递归，会制造出来下面这样的表达式：
(0+x1+x2+x3+..., 0+1+2+3+...)
对于较长的列表，便可能会出现栈溢出。
如果要跳出这个陷阱，我们就需要在 otherTrap 的定义中对元组的两个成员手动进行 seq，即：
otherTrap xs = foldl' (\(acc, len) x -> acc `seq` len `seq` (acc+x, len+1)) (0,0) xs