Avoiding ++ in Haskell

Question

In this answer on CodeReview, the question asker and the answerer both seem to show disdain for the (++) operator. Is this due to it's speed (causing the algorithm to explicitly run in O(n^2) where n is the length of the list iirc)? Is this a pre-optimization if not otherwise tested, as Haskell is known for being difficult to reason about time complexity? Should others avoid the (++) operator in their programs?

Answer 1

It depends.

Consider the expression

foldl (++) [] list

This expression concatenates a list of lists into a single list, but has aforementioned quadratic complexity. This happens because the implementation of (++) traverses the entire left list and prepends each element to the right list (while keeping the correct order of course).

Using a right fold, we get linear complexity:

foldr (++) [] list

This is due to the (++) operator's implementation, which traverses only the left argument and prepends it to the right.

[1,2] ++ [3,4] ++ [5,6]

is equal to

-- 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

which only traverses each list element once.

Now switching the parentheses around to the first two lists is more expensive, since now some elements are traversed multiple times, which is inefficient.

-- 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

All in all, watch out for such cases and you should be fine.