lazy-evaluation - (++) 运算符和 (:) operator and lazy evaluation

Question

真实世界Haskell的第8章

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 来说是必不可少的，但是

我们怎么能理解呢？

底层发生了什么？

“x:(xs ++ ys) 将在恒定空间中进行评估”，如何？听起来尾递归是做什么的!

Answer 1

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

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

当客户端代码使用链表时，它会将其分解回头部和尾部(例如 x:xs )，对头部执行某些操作(如果需要)，然后递归尾部。

当您的代码正在构建链表时，由于延迟评估，它需要做的就是返回一个 thunk 或 promise 它会在被要求时返回一个链表。当头部被取消引用时，它是按需提供的，而尾部则作为对列表其余部分的 promise 。

应该很容易看出，只要列表没有被复制或以其他方式存储，每个 thunk 将被使用一次然后被丢弃，因此整体存储空间是恒定的。

许多严格的语言公开了一种机制(通常称为生成器)来完成相同类型的惰性列表生成，但是对于惰性求值，这些功能作为语言的一部分“免费”提供——本质上，所有 Haskell 列表都是生成器!