haskell - (++) 惰性求值的性能

Question

我一直想知道这个问题，但没有找到满意的答案。

为什么(++)“贵”？在惰性评估下，我们不会评估像

这样的表达式

xs ++ ys

在必要之前，甚至到那时，我们只会在需要时评估我们需要的部分。

有人可以解释一下我缺少什么吗？

Answer 1

如果您访问整个结果列表，延迟计算将不会节省任何计算。它只会延迟它，直到您需要每个特定元素，但最后，您必须计算相同的东西。

如果遍历串联列表xs ++ ys ，访问第一部分 ( xs ) 的每个元素会增加一点常量开销，检查是否 xs是否已被花费。

所以，如果你关联++，就会产生很大的不同。向左或向右。

• 如果您关联 n长度列表k向左侧，例如 (..(xs1 ++ xs2) ... ) ++ xsn然后访问第一个k中的每一个元素将采用 O(n)时间，访问每个下一个 k需要O(n-1)等等。所以遍历整个列表将需要 O(k n^2) 。你可以检查一下

  sum $ foldl (++) [] (replicate 100000 [1])
  

  需要真的很长的时间。

• 如果您关联 n长度列表k到右侧，例如 xs1 ++ ( ..(xsn_1 ++ xsn) .. )那么你只会得到每个元素的恒定开销，因此遍历整个列表将只是 O(k n) 。你可以检查一下

  sum $ foldr (++) [] (replicate 100000 [1])
  

  很有道理。

<小时/>

编辑:这就是ShowS背后隐藏的魔力。 。如果将每个字符串 xs 转换至showString xs :: String -> String ( showString 只是 (++) 的别名)并组合这些函数，然后无论您如何关联它们的组合，最终它们都会从右到左应用 - 这正是我们获得线性时间复杂度所需的。 (这只是因为 (f . g) x 是 f (g x) 。)

您可以检查两者

length $ (foldl (.) id (replicate 1000000 (showString "x"))) ""

和

length $ (foldr (.) id (replicate 1000000 (showString "x"))) ""

在合理的时间内运行( foldr 更快一些，因为从右侧编写函数时开销较小，但两者在元素数量上都是线性的)。