Avoidance ++ in Haskell

Question

In this answer to CodeReview, the questionnaire and responder seem to show contempt for the operator (++). Is this due to this speed (forcing the algorithm to explicitly work in O (n ^ 2), where n is the length of the iirc list)? Is this preliminary optimization unless otherwise verified, since it is known that Haskell is difficult to explain time complexity? Should others avoid the operator (++) in their programs?

Answer 1

It depends.

Consider the expression

foldl (++) [] list 

This expression combines a list of lists into a single list, but has the aforementioned quadratic complexity. This is because the implementation (++) goes through the entire left list and adds each element to the right list (while maintaining the correct order, of course).

Using the right fold, we get linear complexity:

 foldr (++) [] list 

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

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

equally

 -- 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 goes through one list item.

Now switching parentheses in the first two lists is more expensive, since now some elements intersect several 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 

In general, watch out for such cases, and you should be fine.