作为左折叠实现的列表连接的性能

Question

考虑将列表串联实现为左折叠，即 foldl (++) []。在诸如 Haskell 之类的惰性求值语言中，此实现的复杂性如何？我知道在严格的语言中，性能是元素总数的二次方，但是当涉及惰性时会发生什么？

我尝试手动计算表达式 ([1,2,3] ++ [4,5,6]) ++ [7,8,9]（对应于 foldl (++) [] [[1,2,3], [4,5,6], [7,8,9]]）而且好像每个元素我们只遍历一次，但是我不确定我的推理是否正确：

([1,2,3] ++ [4,5,6]) ++ [7,8,9]
= { rewrite expression in prefix notation }
(++) ((++) [1,2,3] [4,5,6]) [7,8,9]
= { the first (++) operation needs to pattern match on its first argument; so it evaluates the first argument, which pattern matches on [1,2,3] }
(++) (case [1,2,3] of {[] -> [4,5,6]; x:xs' -> x:(++) xs' [4,5,6]}) [7,8,9]
= { x = 1, xs' = [2,3] }
(++) (1:(++) [2,3] [4,5,6]) [7,8,9]
= { the first (++) operation can now pattern match on its first argument }
1:([2,3] ++ [4,5,6]) ++ [7,8,9]

我假定 (++) 的以下实现：

(++) :: [a] -> [a] -> [a]
xs ++ ys = case xs of [] -> ys
                      (x:xs') -> x : (xs' ++ ys)

Answer 1

假设我们有 ([1,2,3]++[4,5,6])++[7,8,9]

([1,2,3]++[4,5,6])++[7,8,9]
(1:([2,3]++[4,5,6))++[7,8,9]
1:(([2,3]++[4,5,6])++[7,8,9])
1:((2:([3]++[4,5,6])++[7,8,9])
1:2:(([3]++[4,5,6])++[7,8,9])
1:2:(3:([]++[4,5,6])++[7,8,9])
1:2:3:(([]++[4,5,6])++[7,8,9])
1:2:3:([4,5,6]++[7,8,9])
1:2:3:4:([5,6] ++ [7,8,9])
1:2:3:4:5:([6] ++ [7,8,9])
1:2:3:4:5:6:([] ++ [7,8,9])
1:2:3:4:5:6:[7,8,9]
[1,2,3,4,5,6,7,8,9]

注意到第一个列表中的每个元素都必须移动两次吗？那是因为从最后算起是两个。一般来说，如果我们有 (((a1++a2)++a3)++..an) 列表中的每个元素 ai 将必须移动 n-i 次。

因此，如果您想要整个列表，它是二次方的。如果你想要第一个元素，并且你有 n 个列表，那就是 n-1* 操作（我们需要执行 ++ n 次的步骤）。如果你想要第 i 个元素，它是它之前所有元素的操作数，加上 k-1，它在第 k 个列表中的位置，从末尾开始计算。

*再加上 foldl 本身的 n 操作，如果我们想要迂腐的话

作为左折叠实现的列表连接的性能

Performance of list concatenation implemented as a left fold

performance

haskell

list

lazy-evaluation

time-complexity