(++)运算符、(:)运算符和惰性求值

Question

《RealWorldHaskell》第八章

globToRegex' (c:cs) = escape c ++ globToRegex' cs

这个函数不是尾递归的，它表明答案依赖于Haskell的非严格（懒惰）求值策略。 (++)运算符的简单定义如下所示，并且它不是尾递归的。

(++) :: [a] -> [a] -> [a]

(x:xs) ++ ys = x : (xs ++ ys)
[]     ++ ys = ys

In a strict language, if we evaluate "foo" ++ "bar", the entire list is constructed, then returned. Non-strict evaluation defers much of the work until it is needed.

If we demand an element of the expression "foo" ++ "bar", the first pattern of the function's definition matches, and we return the expression x : (xs ++ ys). Because the (:) constructor is non-strict, the evaluation of xs ++ ys can be deferred: we generate more elements of the result at whatever rate they are demanded. When we generate more of the result, we will no longer be using x, so the garbage collector can reclaim it. Since we generate elements of the result on demand, and do not hold onto parts that we are done with, the compiler can evaluate our code in constant space.

（强调添加。）

上面加粗的解释对于Haskell非常重要，但是：

1. 我们如何理解它？
2. 底层发生了什么？
3. "x:(xs ++ ys)将在常数空间中评估"，为什么？听起来像尾递归做的事情！

- ylzhang

---

听起来对我来说，_常量空间_来自于在按需生成下一个 xs 时丢弃 x。 - sarnold

Answer 1

请记住，"foo"只是'f':'o':'o':[]的语法糖。

也就是说，String只是[Char]的别名，而[Char]只是一个字符链表。

当客户端代码使用这个链表时，它将其分解为头和尾（例如x:xs），对头部进行操作（如果需要的话），然后对尾部进行递归。

当您的代码构造这个链接列表时，由于惰性求值，它所需要做的就是返回一个thunk或者承诺，当被要求时会返回一个链接列表。当头部被解引用时，它会按需提供，并且尾部则作为列表的其余部分的承诺留下。

很容易看出，只要不复制或存储列表，每个thunk都会被使用一次，然后丢弃，因此总体存储空间是恒定的。

许多严格的编程语言公开了一种机制（通常称为generator）来实现相同类型的惰性列表生成，但是在惰性求值中，这些特性作为语言的一部分“免费”使用 - 实际上，所有Haskell列表都是生成器！

- Daniel Pryden

Answer 2

相比其他函数式编程语言，Haskell 倾向于使用惰性求值而非尾递归。这两种机制在限制内存使用方面发挥着相关的作用，但具体采用哪一种机制取决于所生成的数据。

如果你的输出可以被逐步消耗，则应该优先利用惰性求值，因为只有在需要时才会生成输出，从而限制堆消耗。如果你急切地构造输出，则必须使用堆，但可以通过尾递归来节省栈空间。

如果你的输出无法被逐步消耗——也许你正在计算一个 Int ——那么惰性求值可能会留下一堆不必要的 thunk，其求值将导致栈溢出。在这种情况下，需要使用严格的累加器和尾递归。

因此，如果你急切地构造输出，你可能会浪费堆空间来“构建”一个大型数据结构。如果你懒惰，你可能会将“简化”（例如将 1 + 1 简化为 2）推迟到堆上，最终在付出代价时玷污了你的栈。

要同时探索这两个方面，请考虑 foldl' 和 foldr。

- Anthony

Answer 3

尾递归可以保持栈的恒定，但在严格语言中，当计算 x：（xs ++ ys） 时堆会增长。在 Haskell 中，因为它是非严格的，x 在下一个值被计算之前会被释放（除非调用者不必要地持有对 x 的引用），因此堆也将保持恒定。

- geekosaur