在Haskell中避免使用++

Question

在CodeReview的答案中,提问者和回答者似乎都对(++)运算符表示不屑.这是由于它的速度(导致算法明确地在O(n ^ 2)中运行,其中n是列表的长度iirc)？如果不进行其他测试,这是否是预优化,因为Haskell因难以推断时间复杂性而闻名？其他人是否应该避免程序中的(++)运算符？

Answer 1

这取决于.

考虑表达式

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

总而言之,注意这些情况,你应该没事.