在this answer on CodeReview中，提问者和回答者似乎都对(++)运算符表示不屑。这是由于它的速度(导致算法在O(n ^ 2)中显式运行，其中n是列表iirc的长度)吗？如果未经其他测试，这是否是预优化，因为Haskell因难以推理时间复杂性而闻名？其他人应该在程序中避免使用(++)运算符吗？
最佳答案
取决于。
考虑表达
foldl (++) [] list
该表达式将列表的列表连接为单个列表，但是具有上述二次复杂度。发生这种情况是因为
(++)的实现遍历了整个左侧列表，并将每个元素都添加到了右侧列表中(同时保持正确的顺序)。使用正确的折痕，我们得到线性复杂度:
foldr (++) [] list
这是由于
(++)运算符的实现所致，该实现仅遍历左侧参数并将其前置在右侧。[1,2] ++ [3,4] ++ [5,6]
等于
-- Example as created by foldr
[1,2] ++ ([3,4] ++ [5,6])
== [1,2] ++ [3,4,5,6]
== [1,2,3,4,5,6] -- all good, no element traversed more than once
仅遍历每个列表元素一次。
现在，将括号切换到前两个列表的开销更大，因为现在多次遍历了某些元素，因此效率很低。
-- Example as created by foldl
([1,2] ++ [3,4]) ++ [5,6]
== [1,2,3,4] ++ [5,6]
== [1,2,3,4,5,6] -- the sublist [1,2] was traversed twice due to the ordering of the appends
总而言之，当心此类情况，您应该会很好。