Haskell/性能介绍
编程不仅仅是编写能工作的程序，还包括编写需要很少内存和时间在计算机上执行的程序。虽然在命令式编程语言或严格的函数式语言（如 LISP 或 ML）中，时间和内存使用相对容易预测，但这里的情况有所不同。在 Haskell 中，表达式按需求值。例如，表达式
head (map (2 *) [1 .. 10])
将按如下方式求值
⇒ head (map (2 *) (1 : [2 .. 10])) ([1 .. 10]) ⇒ head (2 * 1 : map (2 *) [2 .. 10]) (map) ⇒ 2 * 1 (head) ⇒ 2 (*)
head 函数仅要求列表的第一个元素，因此列表的其余部分 map (2 *) [2 .. 10] 从未求值。由于这种策略只执行必要的求值，因此被称为惰性求值。章节图归约 将详细介绍它。
虽然惰性求值是 Haskell 的常用实现技术，但语言标准 仅指定 Haskell 具有非严格的语义，而没有确定特定的执行模型。具有一个参数的函数 f 被认为是严格的，如果它的参数求值永远循环或未定义时，它不会终止或产生错误。用 ⊥ 表示无限循环的“结果”，严格性的定义为
f ⊥ = ⊥ ，则函数 f 被称为严格的。例如，尝试将 1 加到一个永远循环的数字上，仍然会永远循环，所以 ⊥+1 = ⊥，加法函数 (+1) 是严格的。head 函数也是严格的，因为如果整个列表未定义，列表的第一个元素将不可用。但是，第一个元素可能已定义，而其余列表则没有。在这种情况下，我们有
head (x : ⊥) = x
此等式意味着 head 不会求值其余列表，否则它也会循环。因此，这种纯粹的代数严格性属性对于推理执行时间和内存非常有帮助。在像 LISP 或 ML 这样的严格语言中，我们总是会得到 head (x:⊥) = ⊥，而 Haskell 作为“非严格的”意味着我们可以编写非严格的函数，比如 head 的上述属性或最简单的示例 (const 1) ⊥ = 1。借助于来自Prelude 的常量 undefined，我们甚至可以交互地探索严格性
> head (1 : undefined) 1 > head undefined *** Exception: Prelude.undefined
在这些章节中将使用严格性和 ⊥。图归约 提供了更多入门示例，语义 中详细阐述了语义观点。
理解惰性求值的最佳方法是研究一个例子。因此，我们将考虑 foldr 及其变体的典型用例。章节算法复杂度 回顾了研究程序时间和空间复杂度所需的基础知识。
考虑以下 isPrime 函数，该函数检查一个数字是否为素数
isPrime n = not $ any (`divides` n) [2..n-1] d `divides` n = n `mod` d == 0 any p = or . map p or = foldr (||) False
来自 Haskell Prelude 的辅助函数 any 检查列表中是否存在至少一个满足某个属性 p 的元素。对于 isPrime，该属性是“是 n 的除数”。
求值一个表达式所需的时间当然是由归约步骤的数量来衡量的。如果 n 是一个素数，上述算法将检查从 2 到 n-1 的所有数字，因此最坏情况下的运行时间为 归约。但是，如果 n 不是素数，我们不需要遍历所有这些数字，只要找到一个除数就可以停止，并报告 n 是合数。惰性求值的妙处在于这种行为已经内置在逻辑析取 || 中！
isPrime 42 ⇒ not $ any (`divides` 42) [2..41] ⇒ not ( or (map (`divides` 42) [2..41] ) ) ⇒ not ( or ((42 `mod` 2 == 0) : map (`divides` 42) [3..41]) ) ⇒ not ( (42 `mod` 2 == 0) || or (map (`divides` 42) [3..41]) ) ⇒ not ( True || or (map (`divides` 42) [3..41]) ) ⇒ not True ⇒ False
该函数在发现 42 是偶数后返回 False，|| 在第一个参数确定结果为 True 时不会查看它的第二个参数。换句话说，我们有以下严格性属性
True || ⊥ = True
当然，以上算法可以使用自定义循环来实现。但延迟求值的关键在于，我们可以通过重复使用标准的foldr以透明的方式来制定算法，并且仍然可以获得提前退出。换句话说，延迟求值是关于以模块化的方式制定快速算法。一个极端的例子是使用无限数据结构来有效地模块化生成和修剪算法。本章延迟求值将详细介绍这种技术以及许多其他与延迟求值相关的巧妙技巧。
对执行时间进行详细的图约简分析既不可行也不必要。可以使用一些捷径，例如非严格性或延迟求值始终比急切求值需要更少的约简步骤。这些将在图约简中介绍。
空间
[edit | edit source]虽然执行时间由约简步骤的数量来建模，但内存使用量由表达式在求值过程中的大小来建模。不幸的是，很难预测，而且偏离正常的延迟求值过程（通过增加严格性）可以改善这种情况。更多细节请参见图约简。在这里，我们将介绍一个非预期空间行为的典型示例。
天真地对大量整数求和
> foldr (+) 0 [1..1000000] *** Exception: stack overflow
会产生堆栈溢出。发生了什么？求值过程如下
foldr (+) 0 [1..1000000] ⇒ 1+(foldr (+) 0 [2..1000000]) ⇒ 1+(2+(foldr (+) 0 [3..1000000])) ⇒ 1+(2+(3+(foldr (+) 0 [4..1000000]))
等等。我们可以看到表达式越来越大，需要越来越多的内存。在本例中，内存是在堆栈上分配的，用于在递归调用foldr返回后执行待处理的加法运算。在某个时刻，所需的内存超过了最大可能的堆栈大小，从而引发了“堆栈溢出”错误。不要担心是堆栈还是堆，要记住的是，表达式的尺寸对应于使用的内存，我们可以看到，通常情况下，求值foldr (+) 0 [1..n]需要内存。
但是，应该可以在空间内完成，方法是保留到目前为止看到的数字的累积和，利用+是结合律。（一些读者可能会注意到，这意味着使函数尾递归。）这就是foldl的作用
foldl (+) 0 [1..n] ⇒ foldl (+) (0+1) [2..n] ⇒ foldl (+) ((0+1)+2) [3..n] ⇒ foldl (+) (((0+1)+2)+3) [4..n]
但令我们惊恐的是，累积的和将不会被进一步约简！它将在堆上增长，直到列表结束
⇒ ... ⇒ foldl (+) ((((0+1)+2)+3)+...) [] ⇒ ((((0+1)+2)+3)+...)
随后对这个巨大的未求值的和进行约简也会导致堆栈溢出。（因此，仅仅引入一个累积参数并不能使其成为尾递归。）
问题在于，未求值的和对于单个整数来说是一个过大的表示，并且急切地对其进行求值更便宜。这就是foldl'的作用
foldl' f z [] = z foldl' f z (x:xs) = z `seq` foldl' f (f z x) xs
这里，求值a `seq` b将在继续约简b之前，将a约简为弱头范式。这样，求和过程就变成了
foldl' (+) 0 [1..n] ⇒ foldl' (+) (0+1) [2..n] ⇒ foldl' (+) (1+2) [3..n] ⇒ foldl' (+) (3+3) [4..n] ⇒ foldl' (+) (6+4) [5..n] ⇒ ...
在恒定空间内。
有关更多详细信息和示例，请阅读本章图约简。
低级开销
[edit | edit source]与急切求值相比，延迟求值会增加相当大的开销，即使是整数或字符也必须存储为指针，因为它们可能为⊥。一个包含 1 字节字符的数组比长度相同的String = [Char]紧凑得多。使用严格性注解、非盒装类型和自动严格性分析，可以降低开销。Haskell wiki 是一个很好的资源[1]，其中包含这些低级细节，但该维基百科目前不包含这些内容。
算法和数据结构
[edit | edit source]算法
[edit | edit source]虽然本维基百科不是一本关于算法的通用书籍，但其中包含许多在函数式编程中独有的编写高效程序的技术。本章算法复杂性回顾了大 O 符号，并展示了一些来自实践的示例。
在延迟求值中，重点是利用延迟求值以模块化的方式编写高效算法。
程序推导和等式推理的共同主题是从规范中推导出一个高效的程序，方法是应用和证明方程，例如
map f . reverse = reverse . map f filter p . map f = map f . filter (p . f)
这种探索催生了一个宝石，即纯粹的代数方法来进行动态规划，这将在某个有良好名称的章节中介绍。
另一种称为融合或去森林化的等式技术旨在消除函数组合中的中间数据结构。例如，左侧的组合
map f . map g = map (f . g)
构造和解构一个中间列表，而右侧是对列表的单次遍历。这里的一般主题是融合构造器-解构器对，例如
case (Just y) of { Just x -> f x; Nothing -> ...; } = f y
这将在某个有良好名称的章节中详细介绍。
数据结构
[edit | edit source]选择正确的数据结构是成功的关键。虽然列表很常见，而且可以带来意想不到的收获，但它们更像是一种物化的循环，而不是一种具有快速访问和更新功能的经典数据结构。许多语言都为这类数据结构提供了特殊支持，例如 C 语言中的数组、Perl 语言中的哈希表或 LISP 语言中的列表。在 Haskell 中，本质上倾向于任何类型的树。但是，由于参数多态性和类型类，任何抽象类型（如平衡二叉树）都易于使用和重用！本章数据结构详细介绍了针对常见问题的数据结构的自然选择。
因为 Haskell 是纯粹的函数式语言，所以数据结构具有共同的特征，即持久性。这意味着数据结构的旧版本仍然可用，例如在
foo set = (newset, set) where newset = insert "bar" set
相比之下，命令式语言中的默认行为是瞬态的，即数据在原地更新，旧版本被覆盖。例如，数组是瞬态的。这就是为什么它们在 Haskell 中要么是不可变的，要么需要单子来使用。幸运的是，许多瞬态结构（如队列或堆）都有持久性对应物，本章数据结构还将温和地介绍一些设计原则，例如关于摊销。
并行性
[edit | edit source]并行的目标是在多个核心/计算机上并行运行算法，以获得更快的结果。由于 Haskell 由于其纯度而不强制执行执行顺序，因此非常适合制定并行算法。
目前，Haskell 中的并行仍然是一个研究课题，并且正在进行实验。有一些用于控制执行顺序的组合子Control.Parallel.Strategies，但它们粒度相当细。对一个不太雄心勃勃但更实用的替代方案数据并行 Haskell的研究正在进行中。
本章并行尚未编写，但旨在成为对并行算法以及 Haskell 中当前可能性的简要介绍。