haskell - 为什么如果 Haskell 列表是左助理，它会更有效

Question

我正在学习 Haskell 的基础知识，并且遇到许多教程说如果使用++ 从左到右构建列表比从右到左构建更有效。但我似乎无法理解为什么。

例如，为什么这

a ++ (b ++ (c ++ (d ++ (e ++ f))))

比

((((a ++ b) ++ c) ++ d) ++ e) ++ f

Answer 1

归结为如何列出和++被执行。你可以认为列表被实现如下

data List a = Empty | Cons a (List a)

只需更换 []与 Empty和 :与 Cons .这是 Haskell 中单向链表的一个非常简单的定义。单向链表的连接时间为 O(n) , 与 n是第一个列表的长度。要理解为什么，请回想一下，对于链表，您持有对头元素或第一个元素的引用，并且为了执行任何操作，您必须遍历列表，检查每个值以查看它是否有后继。

因此，对于每个列表串联，编译器必须遍历第一个列表的整个长度。如果您有列表 a , b , c , 和 d与长度 n1 , n2 , n3 , 和 n4分别，那么对于表达式

((a ++ b) ++ c) ++ d

它先走下去 a构建 a ++ b ，然后将此结果存储为 x , 服用 n1步数 a有 n1元素。你只剩下

(x ++ c) ++ d

现在编译器走下来 x构建 x ++ c ，然后将此结果存储为 y在 n1 + n2步骤(这次它必须走下 a 和 b 的元素)。你只剩下

y ++ d

现在 y走下来执行串联，取 n1 + n2 + n3步，共n1 + (n1 + n2) + (n1 + n2 + n3) = 3n1 + 2n2 + n3脚步。

对于表达式

a ++ (b ++ (c ++ d))

编译器从内括号开始，构造 c ++ d -> x在 n3步骤，导致

a ++ (b ++ x)

然后b ++ x -> y在 n2步骤，导致

a ++ y

最后在n1中崩溃了步，总步数为n3 + n2 + n1 ，绝对小于 3n1 + 2n2 + n3 .