Haskell/惰性

惰性 (解决方案)

Haskell 性能

介绍
逐步示例
图约简
惰性
时间和空间分析
严格性
算法复杂度
数据结构
 并行

编辑本章

“

努力工作会在以后得到回报。懒惰现在就会得到回报！ - 史蒂文·赖特

”

介绍

到目前为止，您已经知道 Haskell 使用惰性求值，也就是说在需要之前不会进行任何求值。但是“在需要之前”到底是什么意思呢？在本章中，我们将了解惰性求值是如何工作的（其中有多少魔法）、它对函数式编程的意义以及如何充分利用它。

首先，让我们考虑一下惰性求值的原因和影响。乍一看，我们可能会认为惰性求值使程序更有效。毕竟，还有什么比什么都不做更有效率的呢？然而，在实践中，惰性往往会带来一些开销，导致程序员去寻找可以使代码更严格的地方。惰性的真正好处在于使正确的事情变得足够有效。惰性求值使我们能够编写比在严格环境中更简单、更优雅的代码。

非严格性与惰性

惰性和非严格性之间存在细微差别。非严格语义是指 Haskell 程序的特定属性，您可以依赖它：在需要之前不会进行任何求值。惰性求值是使用一种称为thunk的机制来实现非严格性的方法，我们将在下一节中解释。但是，这两个概念密切相关，将它们一起解释起来很有帮助。了解 thunk 有助于理解非严格性，而非严格性的语义解释了我们为什么要首先使用惰性求值。因此，我们将同时介绍这些概念，并且不会特别努力地将它们分开（除了要正确使用术语）。

thunk 和弱头范式

您需要理解两个原则才能了解程序在 Haskell 中是如何执行的。首先，我们有非严格性的特性：我们尽可能少地求值，并尽可能推迟求值。其次，Haskell 值具有高度分层；而“求值”一个 Haskell 值可能意味着求值到这些层中的任何一层。让我们使用一个对子来逐步说明几个示例。

let (x, y) = (length [1..5], reverse "olleh") in ...

假设在“in”部分，我们使用 x 和 y，否则我们根本不需要求值 let 绑定！右侧可以是 undefined，如果“in”部分没有提到 x 或 y，它仍然有效。这个假设将适用于本节中的所有示例。

我们对 x 了解什么？我们可以计算出 x 必须是 5，y 是 "hello"，但是请记住第一个原则：我们不会求值对 length 和 reverse 的调用，除非被迫这样做。因此，我们说 x 和 y 都是thunk：也就是说，它们是带有求值方法的未求值值，该方法解释了如何求值它们。例如，对于 x，这个方法说“求值 length [1..5]”。但是，我们实际上正在对左侧进行一些模式匹配。如果我们删除该模式匹配会发生什么？

let z = (length [1..5], reverse "olleh") in ...

虽然我们仍然很明显地知道 z 是一个对子，但编译器看到我们根本没有尝试对“=”符号右侧的值进行解构，因此它并不关心那里是什么。它让 z 本身成为一个 thunk。稍后，当我们尝试使用 z 时，我们可能需要一个或两个组件，因此我们必须求值 z，但现在它可以是一个 thunk。

上面，我们说 Haskell 值是分层的。如果我们对 z 进行模式匹配，我们可以看到这一点

let z     = (length [1..5], reverse "olleh")
   (n, s) = z 
in ...

执行完第一行之后，z 只是一个 thunk。我们对它的值类型一无所知，因为我们还没有被要求去了解。但是，在第二行中，我们使用对子模式对 z 进行模式匹配。编译器认为“我最好确保该模式确实与 z 匹配，为了做到这一点，我需要确保 z 是一个对子。”但是要注意，我们还没有对组件部分（对 length 和 reverse 的调用）做任何事情，因此它们可以保持未求值。换句话说，z（它只是一个 thunk）被求值为类似 (*thunk*, *thunk*) 的东西，n 和 s 成为 thunk，当求值时，它们将是原始 z 的组件部分。

让我们尝试一个稍微复杂的模式匹配

let z     = (length [1..5], reverse "olleh")
   (n, s) = z 
   'h':ss = s
in ...

对 z 的第二个组件进行模式匹配会导致一些求值。编译器希望检查 'h':ss 模式是否与对子的第二个组件匹配。因此，它

求值 s 的顶层以确保它是一个 cons 单元：s = *thunk* : *thunk*。（如果 s 是一个空列表，我们将在此时遇到模式匹配失败错误。）
求值它刚刚揭示的第一个 thunk 以确保它是 'h':ss = 'h' : *thunk*

列表的其余部分保持未求值，ss 成为一个 thunk，当求值时，它将是此列表的其余部分。

逐步评估表达式 `(4, [1, 2])` 的值。第一步是完全未评估的；所有后续形式都处于 WHNF 状态，最后一个也处于正常形式。

我们可以对（大多数）Haskell 值进行“部分评估”。此外，我们对评估的最小程度有一些认识。例如，如果我们有一个对 thunk，那么最小程度的评估将我们带到具有两个未评估组件的对构造函数：(*thunk*, *thunk*)。如果我们有一个列表，那么最小程度的评估将我们带到一个 cons 单元格 *thunk* : *thunk* 或一个空列表 []。请注意，在空列表情况下，无法对值进行更多评估；据说它处于正常形式。如果我们处于任何中间步骤，以便我们对值执行了至少一些评估，那么它处于弱头部正常形式（WHNF）。（还有一个“头部正常形式”，但它不在 Haskell 中使用。）完全评估 WHNF 中的某个东西会将其简化为正常形式；如果在某个时刻我们需要，例如，将z 打印给用户，我们需要完全评估它，包括对length 和reverse 的调用，以及对(5, "hello") 的调用，它处于正常形式。对值执行任何程度的评估有时被称为强制该值。

请注意，对于某些值，只有一个结果。例如，你无法对整数进行部分评估。它要么是一个 thunk，要么处于正常形式。此外，如果我们有一个具有严格组件的构造函数（用感叹号注释，如 data MaybeS a = NothingS | JustS !a），那么这些组件将在我们评估上一级时立即被评估。也就是说，我们永远不会有 JustS *thunk*——一旦我们达到这一级，JustS 的组件上的严格性注释就会迫使我们评估组件部分。

在本节中，我们探讨了惰性的基础知识。我们已经看到，在需要之前不会对任何东西进行评估（事实上，Haskell 值唯一被评估的地方是在模式匹配中和在某些原始 IO 函数内部）。这一原则甚至适用于评估值——我们对值执行的最小工作量，以便计算出我们的结果。

惰性和严格函数

函数可以在“一个参数中”是惰性或严格的。大多数函数需要对它们的参数做些什么，这将涉及将这些参数评估到不同的级别。例如，length 只需要评估你给它的参数中的 cons 单元格，而不是这些 cons 单元格的内容。length *thunk* 可能会评估为类似于 length (*thunk* : *thunk* : *thunk* : []) 的东西，进而评估为 3。其他函数需要完全评估它们的参数，如 (length . show)。如果你有 length $ show *thunk*，你无法执行任何其他操作，只能将该 thunk 评估为正常形式。

因此，一些函数比其他函数更全面地评估它们的参数。给定两个具有一个参数的函数，f 和 g，如果 f x 将 x 评估为比 g x 更深的级别，那么我们说 f 比 g 更严格。通常，我们只关心 WHNF，因此将参数评估为至少 WHNF 的函数称为严格函数，而没有任何评估的函数称为惰性函数。对于具有多个参数的函数呢？好吧，我们可以说函数在一个参数中是严格的，但在另一个参数中是惰性的。例如，给定如下函数

f x y = length $ show x

显然我们需要对 y 不进行任何评估，但我们需要将 x 完全评估为正常形式，因此 f 在第一个参数中是严格的，但在第二个参数中是惰性的。

练习
为什么我们必须将 x 在 f x y = show x 中完全评估为正常形式？哪一个函数更严格？ f x = length [head x] g x = length (tail x)

在关于折叠的最初讨论中，我们讨论了 foldl 的内存问题，这些问题由严格评估的 foldl' 解决。本质上，foldr (:) [] 和 foldl (flip (:)) [] 都将它们的参数评估为相同的严格性级别，但 foldr 可以立即开始生成值，而 foldl 需要一直评估到结尾的 cons 单元格才能开始生成任何输出。因此，在某些情况下，严格性可能很有价值。

黑盒严格性分析

如果 `f` 在传递 undefined 时返回错误，那么它一定是严格的。否则，它就是惰性的。

假设我们得到了一个函数 f，它接受一个参数。我们不允许查看它的源代码，但我们想知道 f 是否严格。我们该怎么做呢？可能最简单的方法是使用标准 Prelude 值 undefined。将 undefined 强制为任何评估级别都会停止我们的程序并打印错误，因此所有这些都会打印错误

let (x, y) = undefined in x
length undefined
head undefined
JustS undefined -- Using MaybeS as defined in the last section

因此，如果一个函数是严格的，将 undefined 传递给它将导致错误。如果该函数是惰性的，将 undefined 传递给它将不会打印任何错误，我们可以照常进行。例如，以下内容都不会产生错误

let (x, y) = (4, undefined) in x
length [undefined, undefined, undefined]
head (4 : undefined)
Just undefined

因此，我们可以说 f 是一个严格函数，当且仅当 f undefined 导致打印错误并停止我们的程序。

在非严格语义的上下文中

我们到目前为止提出的内容在你开始思考 id 这样的函数时是合理的。id 是严格的吗？我们的本能反应可能是“不！它不评估它的参数，因此它是惰性的”。但是，让我们将上一节中的黑盒严格性分析应用于 id。显然，id undefined 将会打印错误并停止我们的程序，所以我们不应该说 id 是严格的吗？这种混淆的原因是 Haskell 的非严格语义使整个问题变得更加模糊。

根据非严格性，如果不需要评估任何东西，则不会评估它。在以下代码中，length undefined 会被评估吗？

[4, 10, length undefined, 12]

如果你在 GHCi 中输入此代码，它看起来是严格的——你会得到一个错误。但是，我们的问题有点技巧。在对这个值做一些事情之前，说一个值是否被评估是没有意义的。想想看：如果我们在 GHCi 中输入 head [1, 2, 3]，我们进行任何评估的唯一原因是因为 GHCi 必须将结果打印给我们。输入 [4, 10, length undefined, 12] 再次需要 GHCi 将该列表打印回给我们，因此它必须将其评估为正常形式。在你的普通 Haskell 程序中，直到我们执行 main 中的 IO 之前，什么都不会被评估。因此，除非我们知道它被传递给了什么（向上一个级别），否则说某件事是否被评估是没有意义的。这里的一个教训是：不要盲目信任 GHCi，因为GHCi 中的一切都被过滤到 IO 中！

因此，当我们说“f x 是否强制 x？”时，我们的真正意思是“鉴于我们正在强制 f x，x 是否因此被强制？”。现在我们可以将注意力回到 id。如果我们将 id x 强制为正常形式，那么 x 将被强制为正常形式，因此我们得出结论，id 是严格的。id 本身不评估它的参数，它只是将其传递给将要评估它的调用者。以下代码可以说明这一点

-- We evaluate the right-hand of the let-binding to WHNF by pattern-matching
-- against it.
let (x, y) = undefined in x -- Error, because we force undefined.
let (x, y) = id undefined in x -- Error, because we force undefined.

id 不“停止”强制，因此它是严格的。将其与一个明显的惰性函数 const (3, 4) 相比

let (x, y) = undefined in x -- Error, because we force undefined.
let (x, y) = const (3, 4) undefined -- No error, because const (3, 4) is lazy.

关于事物的语义学观点

如果你熟悉语义学（也许你已经阅读过维基教科书章节？），那么函数的严格性可以非常简洁地总结

f ⊥ = ⊥ ⇔ f 是严格的

假设这一点，我们可以说所有类型为 forall a. a 的东西，包括 undefined、error "any string"、throw 等等，都具有符号 ⊥。

惰性模式匹配

你可能在 Haskell 源代码中看到过类似以下的模式匹配。

-- From Control.Arrow
(***) f g ~(x, y) = (f x, g y)

问题是：在上面的模式匹配中，波浪号 (~) 代表什么？~ 创建一个 *惰性模式* 或 *不可反驳模式*。通常，如果你使用构造函数作为模式的一部分进行模式匹配，你需要评估传递给该函数的任何参数，以确保它与模式匹配。例如，如果你有一个像上面的函数，当调用该函数时，第三个参数将被评估，以确保该值与模式匹配。（注意，第一个和第二个参数不会被评估，因为模式 f 和 g 匹配任何东西。另外值得注意的是，元组的 *组件* 不会被评估：只有 '顶层'。尝试 let f (Just x) = 1 in f (Just undefined) 来查看这一点。）

然而，在模式前面加上波浪号会延迟值的评估，直到组件部分实际使用。但你会有一个风险，即该值可能与模式不匹配——你是在告诉编译器“相信我，我知道它会成功”。（如果事实证明它与模式不匹配，你会得到一个运行时错误。）为了说明区别

Prelude> let f (x,y) = 1
Prelude> f undefined
*** Exception: Prelude.undefined

Prelude> let f ~(x,y) = 1
Prelude> f undefined
1

在第一个例子中，值被评估，因为它必须与元组模式匹配。你评估 undefined 并得到 undefined，这会停止执行。在第二个例子中，你不会在需要之前评估参数，结果证明永远不会需要，所以你传递了 undefined 并不重要。为了让讨论回到 (***)

Prelude> (const 1 *** const 2) undefined
(1,2)

如果模式不是不可反驳的，这个例子就会失败。

什么时候使用惰性模式有意义？

本质上，当你只有类型的一个构造函数时，例如元组，就使用惰性模式。多个等式与不可反驳模式的配合并不好。为了说明这一点，让我们看看如果我们让 head 有一个不可反驳的模式会发生什么

head' :: [a] -> a
head' ~[]     = undefined
head' ~(x:xs) = x

我们肯定使用其中一个模式，并且我们不必在绝对必要之前评估参数的顶层，所以我们不知道它是一个空列表还是一个 cons 单元。因为我们对第一个等式使用了一个 *不可反驳* 模式，它会匹配，函数将始终返回 undefined。

练习
为什么将等式的顺序更改为 `head'` 这里没有帮助？如果将第一个等式更改为使用普通的可反驳模式，`head'` 的行为是否仍然不同于 `head`？如果是，怎么样？

非严格语义的好处

为什么首先要使 Haskell 成为非严格语言？有哪些优势？

没有时间惩罚的关注点分离

惰性求值鼓励在编码时采用一种“所见即所得”的心态。例如，假设你想在一个很长的列表中找到最小的三个数字。在 Haskell 中，这可以通过极其自然的方式实现：take 3 (sort xs)。然而，在严格语言中对该代码进行天真的转换将是一个非常糟糕的主意！它将涉及计算整个排序列表，然后只保留前三个元素。但是，使用惰性求值，我们一旦对列表排序到第三个元素，就停止了，因此这个自然的定义证明是有效的（取决于排序的实现）。

再举一个例子，函数 isInfixOf 来自 Data.List，它允许你查看一个字符串是否是另一个字符串的子字符串。它很容易定义为

isInfixOf :: Eq a => [a] -> [a] -> Bool
isInfixOf x y = any (isPrefixOf x) (tails y)

同样，这在严格语言中是自杀行为，因为计算列表的所有尾部将非常耗时。但是，这里我们只评估每个尾部中足够多的元素，以确定它是否具有前缀 x，并且一旦找到一个具有前缀 x 的元素，就停止并返回 True。

还有很多类似的例子。^[1] 所以我们可以编写看起来和感觉都很自然的代码，而且不会带来任何时间上的损失。

然而，正如计算机科学（以及生活中）中始终存在的那样，存在着权衡（特别是空间-时间权衡）。对一个简单的计算（比如 2+2）使用 thunk 而不是一个简单的 Int 可能是浪费的。有关更多示例，请参阅有关 Haskell/Strictness 的页面。

改进的代码重用

代码重用通常是可取的。

例如，我们再次（但更详细地）使用 Data.List 中的 isInfixOf。让我们看看完整的定义

-- From the Prelude
or = foldr (||) False
any p = or . map p 
 
-- From Data.List
isPrefixOf []     _      = True
isPrefixOf _      []     = False
isPrefixOf (x:xs) (y:ys) = x == y && isPrefixOf xs ys 

tails []         = [[]]
tails xss@(_:xs) = xss : tails xs

-- Our function
isInfixOf :: Eq a => [a] -> [a] -> Bool
isInfixOf x y = any (isPrefixOf x) (tails y)

其中 any、isPrefixOf 和 tails 是从 Data.List 库中获取的函数。这个函数判断它的第一个参数 x 是否作为它的第二个参数 y 的子序列出现；当应用于 String（即 [Char]）时，它会检查 x 是否是 y 的子字符串。以严格的方式读取，它会形成 y 所有尾部的列表，然后检查它们，看是否有任何一个具有 x 作为前缀。在严格语言中，以这种方式编写这个函数（依赖于已经写好的程序 any、isPrefixOf 和 tails）将是愚蠢的，因为它会比实际需要慢得多。你最终会再次进行直接递归，或者在命令式语言中，进行几个嵌套循环。你可能能够从 isPrefixOf 中获得一些使用，但你肯定不会使用 tails。你可能能够编写一个可用的快捷 any，但这将需要更多工作，因为你不会希望使用 foldr 来完成它。

现在，在惰性语言中，所有的快捷方式都是为你完成的。你不会最终重写 foldr 来在找到解决方案时进行快捷方式，也不会重写 tails 中完成的递归，使其再次尽早停止。你可以更好地重用标准库代码。惰性求值不仅仅是一个恒定因子的速度问题，它对代码的编写方式产生了质的影响。事实上，定义无限结构并只使用所需的部分，而不是将构建数据结构的逻辑与确定是否需要任何部分的代码混合在一起，这很常见。代码模块化得到增强，因为惰性求值为你提供了更多方法将代码分解成小块，每块都完成一个简单的数据生成、过滤或其他操作任务。

Why Functional Programming Matters 主要关注惰性求值至关重要的例子，并为惰性求值成为默认选择提供了强有力的论据。

无限数据结构

例子

fibs = 1:1:zipWith (+) fibs (tail fibs)
"rock-scissors-paper" example from Bird&Wadler
prune . generate

无限数据结构通常也会打结，但对它的科幻解释最好留到下一节。可以将下一节放到本节之前，但我认为无限数据结构比打一般的结更简单

常见的非严格习惯用法

打结

更多实际例子？

repMin

科幻解释：“你可以从未来借东西，只要你不试图改变它们”。高级：“蓝图”技术。例子：haskellwiki 上的例子，邮件列表上的例子。

起初，纯函数式语言似乎在循环数据结构方面存在问题。假设我有一个像这样的数据类型

data Foo a = Foo {value :: a, next :: Foo a}

如果我想创建两个对象“x”和“y”，其中“x”包含对“y”的引用，“y”包含对“x”的引用，那么在传统的语言中，这是直接的：创建对象，然后将相关字段设置为指向彼此

 -- Not Haskell code
 x := new Foo;
 y := new Foo;
 x.value := 1;
 x.next := y;
 y.value := 2
 y.next := x;

在 Haskell 中，这种修改是不允许的。因此，我们依赖于惰性求值

circularFoo :: Foo Int 
circularFoo = x
   where
      x = Foo 1 y
      y = Foo 2 x

这取决于“Foo”构造函数是一个函数，而且像大多数函数一样，它是惰性求值的。只有当需要某个字段时，才会对它进行求值。

了解这里幕后发生的事情可能会有所帮助。当创建惰性值时（例如，通过调用“Foo”），编译器会生成一个称为“thunk”的内部数据结构，其中包含函数调用和参数。当需要函数的值时，会调用函数（如你预期的那样）。但随后会用返回值替换 thunk 数据结构。因此，任何其他引用该值的项都会立即获取到它，而无需调用函数。

（注意，Haskell 语言标准没有提到 thunk：它们是实现机制。从数学角度来看，这是一个关于相互递归的简单例子。）

因此，当我们调用“circularFoo”时，结果“x”实际上是一个 thunk。其中一个参数是对表示“y”的第二个 thunk 的引用。它反过来又引用了表示“x”的 thunk。如果我们然后使用值“next x”，这会强制“x” thunk 进行评估，并返回对“y” thunk 的引用。如果我使用值“next $ next x”，那么我会强制对这两个 thunk 进行评估。因此，现在两个 thunk 都被替换为实际的“Foo”结构，相互引用。这就是我们想要的。

这最常应用于构造函数，但并不限于构造函数。你可以同样容易地编写