Haskell/图约简

Haskell 性能

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

备注和待办事项

待办事项：将惰性中的惰性求值解释融入到这个框架中。
待办事项：更好的章节名称。
待办事项：思考图的图形表示。
- 没有图形表示，用 let .. in 来做。优点：约简在这种情况下最容易执行。缺点：没有图形。
- ASCII 艺术/线形艺术类似于 Bird&Wadler 中的？优点：只显示相关部分，真正地作为图形，在纸上很容易执行。缺点：难看，不能用它来表示大型图形。
- 带有 @-节点的完整图形？优点：看起来像图形。缺点：没有人需要知道 @-节点才能理解图约简。可以在实现部分解释。
- 没有 @-节点的图形。优点：易于理解。缺点：柯里化怎么办？
！保持本章简短。读者越快学会如何手动评估 Haskell 程序，越好。
前几节紧随 Bird&Wadler

介绍

编程不仅仅是编写由语义学回答的正确程序，还包括编写快速且内存消耗低的程序。为此，我们需要了解它们如何在机器上执行，通常由操作语义给出。本章解释了 Haskell 程序通常如何在真实计算机上执行，因此它为分析 Haskell 程序的时间和空间使用提供了基础。请注意，Haskell 标准故意不提供操作语义，实现可以自由选择自己的语义。但到目前为止，所有 Haskell 实现或多或少都遵循惰性求值的执行模型。

在下文中，我们将详细说明惰性求值，并随后使用此执行模型来解释和举例说明关于 Haskell 程序的时间和内存复杂度的推理。

通过惰性求值评估表达式

约简

执行一个函数式程序，即评估一个表达式，意味着重复应用函数定义，直到所有函数应用都被展开。例如，表达式 pythagoras 3 4 以及定义

      square x = x * x
pythagoras x y = square x + square y

一个可能的约简序列是

pythagoras 3 4
 ⇒ square 3 + square 4   (pythagoras)
 ⇒    (3*3) + square 4   (square)
 ⇒        9 + square 4   (*)
 ⇒        9 + (4*4)      (square)
 ⇒        9 + 16         (*)
 ⇒          25

每次约简都用一个等效的表达式替换一个子表达式，称为可约表达式或简称为redex，要么是通过调用函数定义（例如 square），要么是通过使用内置函数（例如 (+)）来实现。没有 redex 的表达式被称为范式。当然，一旦达到范式，执行就会停止，因此范式是计算的结果。

显然，执行约简的次数越少，程序运行速度就越快。我们不能期望每个约简步骤都花费相同的时间，因为它们在真实硬件上的实现看起来非常不同，但在渐近复杂度方面，这个约简次数是一个准确的度量。

约简策略

有许多可能的约简序列，约简次数可能取决于约简执行的顺序。例如，表达式 fst (square 3, square 4)。一种系统的方法是在应用函数定义之前评估所有函数参数

fst (square 3, square 4)
 ⇒ fst (3*3, square 4)   (square)
 ⇒ fst ( 9 , square 4)   (*)
 ⇒ fst ( 9 , 4*4)        (square)
 ⇒ fst ( 9 , 16 )        (*)
 ⇒ 9                     (fst)

这被称为最内层约简策略，而最内层 redex 是一个 redex，其内部没有其他 redex 作为子表达式。

另一种系统的方法是先应用所有函数定义，然后再评估参数

fst (square 3, square 4)
 ⇒  square 3             (fst)
 ⇒  3*3                  (square)
 ⇒  9                    (*)

这被称为最外层规约，它总是规约最外层重写子，而最外层重写子不在另一个重写子中。这里，最外层规约比最内层规约使用更少的规约步骤。为什么？因为函数fst不需要对的第二个元素，而square 4的规约是多余的。

终止

对于一些表达式，例如

loop = 1 + loop

没有规约序列可以终止，程序执行进入无限循环，这些表达式没有范式。但也有一些表达式，其中一些规约序列终止而另一些则不终止，例如

fst (42, loop)
 ⇒  42                   (fst)

fst (42, loop)
 ⇒  fst (42,1+loop)      (loop)
 ⇒  fst (42,1+(1+loop))  (loop)
 ⇒  ...

第一个规约序列是最外层规约，第二个是最内层规约，它徒劳地试图评估loop，即使它被fst忽略。在终止方面，能够仅在需要时评估函数参数是使最外层规约成为最佳选择的原因。

定理（Church-Rosser II）: 如果存在一个终止规约，那么最外层规约也将终止。

图规约（规约 + 共享）

尽管能够丢弃参数，但最外层规约并不总是比最内层规约需要更少的规约步骤。

square (1+2)
 ⇒  (1+2)*(1+2)          (square)
 ⇒  (1+2)*3              (+)
 ⇒      3*3              (+)
 ⇒       9               (*)

这里，参数(1+2)被复制，随后被规约两次。但是，因为它是一个参数，所以解决方案是与该参数的所有其他化身共享规约(1+2) ⇒ 3。这可以通过将表达式表示为图来实现。例如，

 __________
|   |     ↓
◊ * ◊     (1+2)

表示表达式(1+2)*(1+2)。现在，square (1+2)的最外层图规约按如下方式进行：

square (1+2)
 ⇒  __________           (square)
    |   |     ↓
    ◊ * ◊     (1+2)
 ⇒  __________           (+)
    |   |     ↓
    ◊ * ◊      3

 ⇒ 9                     (*)

并且工作已经共享。换句话说，最外层图规约现在最多只规约每个参数一次。因此，它总是比最内层规约需要更少的规约步骤，当我们推理时间时将证明这一点。

表达式共享也通过let和where构造引入。例如，考虑海伦公式，用于计算边长为a、b和c的三角形的面积。

area a b c = let s = (a+b+c)/2 in
     sqrt (s*(s-a)*(s-b)*(s-c))

将其实例化为等边三角形将规约为

area 1 1 1
 ⇒        _____________________             (area)
          |  |    |     |      ↓
    sqrt (◊*(◊-a)*(◊-b)*(◊-c))  ((1+1+1)/2)
 ⇒        _____________________             (+),(+),(/)
          |  |    |     |      ↓
    sqrt (◊*(◊-a)*(◊-b)*(◊-c))  1.5
 ⇒
    ...
 ⇒
    0.433012702

即 ${\sqrt {3}}/4$ 。换句话说，let绑定只是为图中的节点命名。事实上，人们可以完全放弃图形符号，而仅仅依靠let来标记共享并表达图结构。^[1]

Haskell 的任何实现都以某种形式基于最外层图规约，因此它为推理时间和内存分配的渐近复杂度提供了一个良好的模型。达到范式的规约步骤数量对应于执行时间，图中项的大小对应于使用的内存。

练习

使用最内层和最外层图规约将square (square 3)规约为范式。
考虑快速求幂算法
```
power x 0 = 1
power x n = x' * x' * (if n `mod` 2 == 0 then 1 else x)
  where x' = power x (n `div` 2)
```
它将x提高到n次方。使用最内层和最外层图规约规约power 2 5。执行了多少次规约？一般power 2 n的渐近时间复杂度是多少？如果我们使用“无图”最外层规约，算法会发生什么？

模式匹配

到目前为止，我们对最外层图规约的描述在模式匹配和数据构造函数方面仍然不足。解释这些要点将使读者能够跟踪大多数规约策略的情况，该策略通常是实现非严格函数式语言（如 Haskell）的基础。它被称为按需调用或惰性求值，暗示它“惰性地”将函数参数的规约推迟到最后一刻。当然，其余细节将在后续章节中介绍。

要了解模式匹配需要规范，例如，考虑布尔析取

 or True  y = True
 or False y = y

和表达式

 or (1==1) loop

其中有一个非终止loop = not loop。以下规约序列

or (1==1) loop
 ⇒ or (1==1) (not loop)        (loop)
 ⇒ or (1==1) (not (not loop))  (loop)
 ⇒ ...

只规约最外层重写子，因此是最外层规约。但是

or (1==1) loop
 ⇒ or True   loop              (or)
 ⇒ True

更有意义。当然，我们只想应用or的定义，并且只规约参数以决定选择哪个等式。这种意图可以通过以下 Haskell 模式匹配规则来捕获。

从上到下匹配左手边
当匹配左手边时，从左到右匹配参数
仅在需要时评估参数以确定它们是否匹配。

因此，对于我们的示例or (1==1) loop，我们必须将第一个参数规约为True或False，然后评估第二个参数以匹配变量y模式，然后展开匹配的函数定义。由于与变量的匹配总是成功的，因此第二个参数根本不会被规约。它是上面的第二个规约部分，再现了这种行为。

有了这些准备，读者现在应该能够评估大多数 Haskell 表达式。以下是一些随机遇到的测试这种能力的问题。

练习

使用惰性求值将以下表达式规约为范式。假设来自 Prelude 的标准函数定义。

```
length [42,42+1,42-1]
```
```
head (map (2*) [1,2,3])
```

head $ [1,2,3] ++ (let loop = tail loop in loop)

```
zip [1..3] (iterate (+1) 0)
```

head $ concatMap (\x -> [x,x+1]) [1,2,3]

take (42-6*7) $ map square [2718..3146]

高阶函数

要澄清的最后一点是高阶函数和柯里化的规约。例如，考虑以下定义

 id x = x
 a = id (+1) 41

 twice f = f . f
 b = twice (+1) (13*3)

其中id和twice都只用一个参数定义。解决方案是将多个参数视为对一个参数的后续应用，这被称为柯里化

 a = (id    (+1)) 41
 b = (twice (+1)) (13*3)

为了规约任意应用expression₁ expression₂，按需调用首先规约expression₁，直到它成为一个函数，其定义可以用参数expression₂展开。因此，规约序列为

a
 ⇒ (id (+1)) 41          (a)
 ⇒ (+1) 41               (id)
 ⇒ 42                    (+)

b
 ⇒ (twice (+1)) (13*3)   (b)
 ⇒ ((+1).(+1) ) (13*3)   (twice)
 ⇒ (+1) ((+1) (13*3))    (.)
 ⇒ (+1) ((+1)  39)       (*)
 ⇒ (+1) 40               (+)
 ⇒ 41                    (+)

诚然，这个描述有点模糊，下一节将详细说明一种清晰地表达它的方法。

虽然看起来模式匹配是时间密集型计算的“主力”，而高阶函数只是为了捕捉算法的本质，但事实上，函数确实可以作为数据结构很有用。一个例子是差分列表（[a] -> [a]），它允许在 $O(1)$ 时间内连接，另一个是通过折叠表示流。事实上，在纯 lambda 演算（所有函数式编程语言的根源）中，所有数据结构都表示为函数。

练习！还是不？差分列表最好用foldl (++)完成，但这需要了解折叠的例子。哦，我们到底在哪里介绍了 foldl VS. foldr 的例子？嗯，Bird & Wadler 在“控制规约顺序和空间需求”的最后偷偷加了一个额外的部分“再次遇到折叠”来处理 (++) 的例子 :-/ (++) 的复杂度在论证reverse时得到解释。

弱头范式

为了精确地表达惰性求值如何选择它的规约序列，最好放弃等式函数定义，并用一种以表达式为导向的方法来代替。换句话说，我们的目标是将像f (x:xs) = ...这样的函数定义转换为f = expression的形式。这可以通过两个原语来完成，即 case 表达式和 lambda 抽象。

在它们的原始形式中，case 表达式只允许区分最外层构造函数。例如，列表的原始 case 表达式具有以下形式

case expression of
  []   -> ...
  x:xs -> ...

lambda 抽象是一个参数的函数，因此以下两个定义是等效的

f x = expression
f   = \x -> expression

以下是zip定义的翻译

 zip :: [a] -> [a] -> [(a,a)]
 zip []      ys      = []
 zip xs      []      = []
 zip (x:xs') (y:ys') = (x,y):zip xs' ys'

到 case 表达式和 lambda 抽象

 zip = \xs -> \ys ->
    case xs of
       []    -> []
       x:xs' ->
          case ys of
             []    -> []
             y:ys' -> (x,y):zip xs' ys'

假设所有定义都已翻译为这些原语，那么每个重写子现在都具有以下形式之一：

一个函数应用 (\variable->expression₁) expression₂
或一个 case 表达式case expression of { ... }

惰性求值.

弱头范式: 一个表达式处于弱头范式，当且仅当它为以下之一：

一个构造函数（可能应用于参数），例如True、Just (square 42)或(:) 1
一个应用于过少参数（可能没有参数）的内置函数，例如(+) 2或sqrt。
或一个 lambda 抽象\x -> expression。

函数类型无法进行模式匹配，但是狡猾的 seq 仍然可以将它们评估为 WHNF。“弱” = 在 lambda 下不规约。“头” = 首先是函数应用，然后是参数。

严格函数和非严格函数

非严格函数不需要它的参数。严格函数需要它的参数处于 WHNF，只要我们不区分非终止的不同形式（例如，f x = loop 不需要它的参数）。

控制空间

"空间"在这里可以更好地理解为图的遍历。可以是数据结构，也可以是诱导的依赖图。例如：Fibonacci(N) 依赖于：如果 N = 0 或 N = 1，则没有依赖；否则依赖于 Fibonacci(N-1) 和 Fibonacci(N-2)。由于 Fibonacci(N-1) 依赖于 Fibonacci(N-2)，因此诱导的图不是树。因此，实现技术和数据结构遍历之间存在对应关系。

对应的实现技术	数据结构遍历
记忆化	深度优先搜索（将所有中间结果保存在内存中）
并行评估	广度优先搜索（将所有中间结果保存在内存中）
共享	有向无环图遍历（只在内存中维护一个“前沿”）
常规递归	树遍历（填充堆栈）
尾递归	列表遍历 / 贪心搜索（常数空间）

经典的

fibo 0 = 1
fibo 1 = 1
fibo n = fibo (n-1) + fibo (n-2)

是将树遍历应用于有向无环图，在最坏情况下。优化后的版本

fibo n = 
  let f a b m =
     if m = 0 then a
     if m = 1 then b
     f b (a+b) (m-1)
  in f 1 1 n

使用 DAG 遍历。幸运的是，前沿大小是常数，因此它是一个尾递归算法。

注意：本章Haskell/Strictness旨在详细阐述这里的內容。

注意：在这一节之前要介绍严格函数的概念。

现在是介绍占用大量空间的 fold 示例的时候了

foldl (+) 0 [1..10]

介绍 seq 和 $!，它们可以强制表达式变为 WHNF。=> foldl'。

棘手的空间泄漏示例

(\xs -> head xs + last xs) [1..n]

(\xs -> last xs + head xs) [1..n]

由于 Haskell 中的评估顺序仅由数据依赖关系定义，而 head xs 不依赖于 last xs，反之亦然，因此两者都可以先执行。这意味着，根据编译器，一个版本在 O(1) 空间内运行，而另一个在 O(n) 空间内运行（一个足够聪明的编译器可能会将两个版本都优化到 O(1)，但 GHC 9.8.2 在我的机器上没有这样做 - 只有第二个版本在 O(1) 空间内运行）。

共享和 CSE

注意：与关于时间的部分有重叠。嗯，添加一个额外的记忆化部分吗？

如何共享

foo x y =
  where s = expensive x -- s is not shared
foo x = \y -> s + y
  where s = expensive x -- s is shared

"Lambda 提炼"，"完全惰性"。编译器不应该执行完全惰性。

一个经典且重要的空间和时间权衡示例

sublists []      = [[]]
sublists (x:xs)  = sublists xs ++ map (x:) (sublists xs)
sublists' (x:xs) = let ys = sublists' xs in ys ++ map (x:) ys

这就是编译器不应该将公共子表达式消除作为优化的原因。（GHC 会这样做吗？）

尾递归

注意：这是否属于空间部分？我认为是的，它与堆栈空间有关。

Haskell 中的尾递归看起来有所不同。

关于时间推理

注意：在介绍上界之前介绍严格性可以简化解释过程？

惰性评估 < 积极评估

在推断执行时间时，通过手动执行图归约来了解发生了什么，通常是不可行的。事实上，惰性评估所采取的评估顺序很难让人预测，追踪积极评估的路径要容易得多，因为参数会在传递给函数之前被归约到范式。但要知道，惰性评估总是执行的归约步骤少于积极评估（给出证明！），我们可以很容易地通过假装我们的函数是积极评估的来得到归约次数的上界。

示例

or = foldr (||) False
isPrime n = not $ or $ map (\k -> n `mod` k == 0) [2..n-1]

=> 积极评估总是需要 n 步，惰性评估不会超过这个值。但实际上会更少。

丢弃参数

对于无论如何都会将参数检查到范式的函数，时间边界是精确的。函数需要其参数的属性可以用语义学简洁地表达

f ⊥ = ⊥

不过，参数仅在 WHNF 中。从操作的角度看：非终止 -> 非终止。（但这只是一个近似值，因为 f anything = ⊥ “不需要”其参数）。非严格函数不需要其参数，积极评估的时间边界并不精确。但函数是否严格的信息已经可以很好地用于分析。

isPrime n = not $ or $ (n `mod` 2 == 0) : (n `mod` 3 == 0) : ...

知道 or True ⊥ = True 就足够了。

其他示例

foldr (:) [] 与 foldl (flip (:)) [] 结合 ⊥ 使用。
只用 ⊥ 就可以分析 head . mergesort 吗？无论如何，这个例子太复杂了，应该属于 Haskell/Laziness。

持久化 & 均摊

注意：最好将这一节放到数据结构章节中，因为上面的子节涵盖了大多数程序员（不关注数据结构/均摊）会遇到的情况。

持久化 = 不进行就地更新，旧版本仍然存在。均摊 = 将不均匀的运行时间分配到一系列操作中。在严格环境中，两者无法很好地协同工作。惰性评估可以协调两者。借贷不变式。示例：以二进制表示形式递增数字。

图归约的实现

简要介绍 G-机器等。主要定义

闭包 = thunk = 堆上的代码/数据对。它们的作用是什么？考虑 $(\lambda x.\lambda y.x+y)2$ 。这是一个返回函数的函数，在本例中是 $\lambda y.2+y$ 。但当你想要编译代码时，实际地在内存中执行替换并将所有出现的 $x$ 替换为 2 是不可行的。因此，你返回一个闭包，它包含函数代码 $\lambda y.x+y$ 和一个环境 $\{x=2\}$ ，它将值分配给其中出现的自由变量。

GHC（？，大多数 Haskell 实现？）完全避免了自由变量，并使用了超组合子。换句话说，它们被提供为额外的参数，并且观察到参数过少的 lambda 表达式不需要被归约，因为它们的 WHNF 并没有什么不同。

请注意，这些术语是实现方面的专业术语，惰性评估可以在没有它们的情况下很好地运行。不要在上面的任何部分使用它们。

注释

↑ Maraist, John; Odersky, Martin; Wadler, Philip (1998年5月). "The call-by-need lambda calculus". Journal of Functional Programming. 8 (3): 257–317.

参考文献

Bird, Richard (1998). Introduction to Functional Programming using Haskell. Prentice Hall. ISBN 0-13-484346-0.
Peyton-Jones, Simon (1987). The Implementation of Functional Programming Languages. Prentice Hall.

图约简

练习解答

Haskell 性能

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

编辑本章

Haskell

Haskell 基础 >> 基础 Haskell >> 进阶 Haskell >> 单子
 高级 Haskell >> 类型玩转 >> 扩展理论 >> Haskell 性能

库参考 >> 通用实践 >> 专业任务

编辑书籍结构

[1] Maraist, John; Odersky, Martin; Wadler, Philip (1998年5月). "The call-by-need lambda calculus". Journal of Functional Programming. 8 (3): 257–317.