Haskell/惰性

惰性 (解决方案)

Haskell 性能

介绍
循序渐进的例子
图归约
惰性
时间和空间分析
严格性
算法复杂度
数据结构
 并行

编辑本章

“

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

”

介绍

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

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

非严格性与惰性

惰性和非严格性之间存在细微的差别。非严格语义指的是 Haskell 程序具有的一个你可以依赖的属性：在需要之前不会对任何东西进行求值。惰性求值是使用一种叫做thunk的机制来实现非严格性的方式，我们将在下一节中解释。然而，这两个概念是如此密切相关，以至于将它们一起解释会有所帮助。了解 thunk 有助于理解非严格性，而非严格性的语义解释了我们为什么首先在 Haskell 中使用惰性求值。因此，我们将同时介绍这些概念，并且不会特别努力地防止它们交织在一起（除了将术语弄清楚）。

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 进行求值，以确保它是一个 cons 单元：'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 比 g x 更深入地评估 x，则我们说 f 比 g 更严格。通常，我们只关心 WHNF，因此将参数评估为至少 WHNF 的函数被称为严格的，而执行任何评估的函数被称为惰性的。具有多个参数的函数呢？好吧，我们可以谈论函数在一个参数中是严格的，而在另一个参数中是惰性的。例如，给定一个类似于以下的函数

f x y = length $ show x

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

练习
为什么我们必须在 `f x y = show x` 中完全将 `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 传递给它不会打印错误，我们可以像往常一样继续。例如，以下 none 产生错误

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 单元。由于我们使用的是第一个方程式的不可反驳模式，它将匹配，并且函数将始终返回未定义。

练习
为什么将方程式的顺序更改为`head'`在这里不起作用？如果将第一个方程式更改为使用普通的可反驳模式，`head'`的行为是否仍与`head`不同？如果是，怎样？

非严格语义的优点

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

无需时间损失的关注点分离

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

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

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中完成的递归，以便它再次提前停止。您可以更好地重用标准库代码。惰性不仅仅是恒定因子速度问题，它对代码的编写方式产生了质的影响。事实上，定义无限结构并只使用需要的部分很常见，而不必将构造数据结构的逻辑与确定是否需要任何部分的代码混合起来。代码模块化性得到提高，因为惰性为您提供了更多方法将代码分解成小块，每个小块都执行一项生成、过滤或以其他方式操作数据的简单任务。

为什么函数式编程很重要主要集中在惰性至关重要的示例上，并为惰性求值为默认值提供了强有力的论据。

无限数据结构

示例

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”结构替换，相互引用。这就是我们想要的。

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