Haskell 中惰性求值下的串联顺序和性能

Question

考虑以下两个执行顺序：

a ++ (b ++ c)

和

(a ++ b) ++ c

为什么第一个执行顺序比第二个快？

我是Haskell的新手，希望得到详细的解释，谢谢！

Answer 1

当全面评估x ++ y的结果时，您必须支付：

1. 全面评估的成本x。
2. 全面评估的成本y。
3. 执行(++)操作时遍历x一次的代价。

现在让我们比较一下 a ++ (b ++ c) 和 (a ++ b) ++ c。让我们将评估 a 的成本写为 CA（以及类似的 CB、CC），以及遍历 a 的成本作为 TA（以及类似的 TB、TC）。那么完全评估a ++ (b ++ c)的代价是：

1. 加利福尼亚a的费用。
2. b ++ c的费用，即
   1. CB
   2. CC
   3. 一次遍历b，TB.
3. TA

这是CA+CB+CC+TA+TB的总和。现在，对于 (a ++ b) ++ c:

1. a ++ b的费用，即
   1. 加拿大
   2. CB
   3. TA
2. CC
3. 遍历一次a ++ b，即TA+TB

这是CA+CB+CC+2*TA+TB的总和。相对于另一条订单，多了a的遍历，多了TA的开销，所以这条订单的开销更大。

我把它留给 reader 来尝试更长的链并开始弄清楚模式。简而言之，坏的关联在每次调用 (++) 时重做它已经完成的所有遍历，再加上一次遍历，而好的关联最多遍历每个列表一次。