Haskell中函数和数据递归的性能差异

Question

在思考另一个问题时，我意识到以下功能smoothSeq和smoothSeq'

smoothSeq :: (Integer, Integer, Integer) -> [Integer]
smoothSeq (a, b, c) = result
  where
    result = 1 : union timesA (union timesB timesC)
    timesA = map (* a) $ result
    timesB = map (* b) $ result
    timesC = map (* c) $ result

smoothSeq' :: (Integer, Integer, Integer) -> [Integer]
smoothSeq' (a, b, c) = 1 : union timesA (union timesB timesC)
  where
    timesA = map (* a) $ smoothSeq' (a, b, c)
    timesB = map (* b) $ smoothSeq' (a, b, c)
    timesC = map (* c) $ smoothSeq' (a, b, c)

-- | Merge two sorted sequences discarding duplicates.
union :: (Ord a) => [a] -> [a] -> [a]
union [] ys = ys
union xs [] = xs
union (x : xs) (y : ys)
  | x < y = x : union xs (y : ys)
  | x > y = y : union (x : xs) ys
  | otherwise = x : union xs ys

具有截然不同的性能特征：

ghci> smoothSeq (2,3,5) !! 500
944784
(0.01 secs, 311,048 bytes)
ghci> smoothSeq' (2,3,5) !! 500
944784
(11.53 secs, 3,745,885,224 bytes)

我的印象是，它smoothSeq在内存和时间上是线性的（就像以前那样regularSeq），因为result在递归定义中共享，而它smoothSeq' 是超线性的，因为递归函数定义产生了一棵计算树，它独立地重新计算序列的前一项的多次（有不共享/记忆前面的术语；类似于朴素的斐波那契）。

在四处寻找详细解释时，我遇到了这些示例（以及其他示例）

fix f = x where x = f x
fix' f = f (fix f)

cycle xs = res where res = xs ++ res
cycle' xs = xs ++ cycle' xs

同样，非启动版本（没有'后缀）显然更有效，因为它重用了以前的计算。

据我所知，这两个版本的区别在于递归是否涉及函数或数据（更准确地说，是函数绑定还是模式绑定）。这足以解释行为的差异吗？决定某件事是否被记忆的背后原理是什么？我在 Haskell 2010 语言报告或其他地方找不到明确且全面的答案。

---

编辑：这是我能想到的另一个简单的例子：

arithSeq start step = result
  where
    result = start : map (+ step) result
arithSeq' start step = start : map (+ step) (arithSeq' start step)

ghci> arithSeq 10 100 !! 10000
1000010
(0.01 secs, 1,443,520 bytes)
ghci> arithSeq' 10 100 !! 10000
1000010
(1.30 secs, 5,900,741,048 bytes)

朴素的递归定义比递归“发生在数据上”arithSeq'更糟糕。arithSeq

Answer 1

在使用 GHC 且不进行优化的情况下，每次调用smoothSeq都会创建一个results列表并在所有计算中使用同一列表。相反，调用smoothSeq'将创建一个列表，然后递归调用自身三次，从而创建另外三个列表，每个列表创建自己的三个列表，依此类推。这解释了内存使用和性能的巨大差异。

在这两个极端之间有一种实现，即：

smoothSeq'' :: (Integer, Integer, Integer) -> [Integer]
smoothSeq'' (a, b, c) = 1 : union timesA (union timesB timesC)
  where
    result = smoothSeq'' (a, b, c)
    timesA = map (* a) result
    timesB = map (* b) result
    timesC = map (* c) result

请注意，smoothSeq'如果您使用-O. 不幸的是，GHC 不够聪明，无法将其一直优化到smoothSeq.

Answer 2

根据经验，当您将某些内容绑定到名称时，同一范围内对该名称的所有引用都引用内存中的单个对象。然而，当您有多个相同的表达式（比对单个名称的引用更复杂）时，它们是内存中碰巧具有相同值的不同对象。¹

那么让我们看看这个一般原则如何应用于您的代码：

smoothSeq :: (Integer, Integer, Integer) -> [Integer]
smoothSeq (a, b, c) = result
  where
    result = 1 : union timesA (union timesB timesC)
    timesA = map (* a) $ result
    timesB = map (* b) $ result
    timesC = map (* c) $ result

result在这里，您已经为值指定了名称1 : union timesA (union timesB timesC)。使用的所有其他地方result都在同一范围内（ 的应用程序内的本地范围smoothSeq），因此引用单个共享值。这意味着当timesA进行更多评估并触发更多评估时result，然后timesB将timesC随后看到内部已评估的工作结果result。

在这一篇中：

smoothSeq' :: (Integer, Integer, Integer) -> [Integer]
smoothSeq' (a, b, c) = 1 : union timesA (union timesB timesC)
  where
    timesA = map (* a) $ smoothSeq' (a, b, c)
    timesB = map (* b) $ smoothSeq' (a, b, c)
    timesC = map (* c) $ smoothSeq' (a, b, c)

在这里，表达式没有单一名称smoothSeq' (a, b, c)，您只是多次编写了该表达式。这些表达式中的每一个都是独立的调用，因此它们将由内存中的单独对象表示，并且评估其中一个不会对其他表达式产生影响。

timesA此外，timesB、 和的定义范围是, 在收到其参数后的应用程序内部的timesC范围。这意味着 的每个应用程序都有其自己的、和值范围，包括定义、和 的调用。因此，与仅输入一次的版本不同，每次调用都会再分叉 3 次调用。这确实是超线性的。smoothSeq'smoothSeq'timesAtimesBtimesCtimesAtimesBtimesCresultsmoothSeq

我认为也值得将其与其他问题中类似结构的代码进行比较：

regularSeq :: [Integer]
regularSeq = 1 : union timesTwo (union timesThree timesFive)
  where
    timesTwo   = map (* 2) regularSeq
    timesThree = map (* 3) regularSeq
    timesFive  = map (* 5) regularSeq

这很像smoothSeq，因为 3 个内部定义都使用单个名称regularSeq，因此引用单个对象。但这里该名称/对象的范围完全不同。smoothSeq共享变量是在应用程序内部result定义的。因此每次调用都有一个单独的，但它在所有内部定义、和之间共享。在 中，共享名称是全局范围内的名称；因此，它将在程序的整个生命周期内共享。smoothSeqresultsmoothSeqtimesAtimesBtimesCregularSeq

希望这说明了在尝试预测共享内容时要考虑的关键问题是变量及其范围。

¹从技术上讲，编译器可能会将名称的定义内联到其使用位置，从而即使您使用相同的名称也会创建不同的对象。它还可能应用公共子表达式消除，以便多个相同的表达式最终引用相同的值。它甚至可以注意到局部作用域中的表达式不依赖于它内部出现的函数的参数，并将表达式提升到外部以成为内存中在函数调用之间共享的单个对象。因此，如果我们要精确的话，您无法仅通过查看源代码来确定，这就是为什么对于将共享的内容没有任何绝对严格的参考。语言语义向您承诺一个结果，但不向您承诺任何特定的评估策略。

然而，这些转换被用作优化。编译器将尝试确保仅在提高代码性能时才进行这些更改；如果应用其中任何一个并对性能产生很大的负面影响，GHC 开发人员可能会将其视为编译器错误。因此，可以很安全地将其视为“如果您命名它，那么它是同一个对象，否则它们是不同的对象”。任何偏差都不太重要；根据简单的经验法则，编译器的运行速度可能比您预期的要快，这可能会让您感到惊讶，但它可能不会以产生大问题的方式违反您的预期。如果您试图从代码中榨取最后一点性能，您通常只需要担心它到底会做什么。