The performance of (++) with lazy evaluation

Question

I have been wondering about this a lot, and I haven't found satisfying answers.

Why is (++) "expensive"? Under lazy evaluation, we won't evaluate an expression like

xs ++ ys

before necessary, and even then, we will only evaluate the part we need, when we need them.

Can someone explain what I'm missing?

Answer 1

If you access the whole resulting list, lazy evaluation won't save any computation. It will only delay it until you need each particular element, but at the end, you have to compute the same thing.

If you traverse the concatenated list xs ++ ys, accessing each element of the first part (xs) adds a little constant overhead, checking if xs was spent or not.

So, it makes a big difference if you associate ++ to the left or to the right.

• If you associate n lists of length k to the left like (..(xs1 ++ xs2) ... ) ++ xsn then accessing each of the first k elements will take O(n) time, accessing each of the next k ones will take O(n-1) etc. So traversing the whole list will take O(k n^2). You can check that

  sum $ foldl (++) [] (replicate 100000 [1])
  

  takes really long.

• If you associate n lists of length k to the right like xs1 ++ ( ..(xsn_1 ++ xsn) .. ) then you'll get only constant overhead for each element, so traversing the whole list will be only O(k n). You can check that

  sum $ foldr (++) [] (replicate 100000 [1])
  

  is quite reasonable.

---

Edit: This is just the magic hidden behind ShowS. If you convert each string xs to showString xs :: String -> String (showString is just an alias for (++)) and compose these functions, then no matter how you associate their composition, at the end they will be applied from right to left - just what we need to get the linear time complexity. (This is simply because (f . g) x is f (g x).)

You can check that both

length $ (foldl (.) id (replicate 1000000 (showString "x"))) ""

and

length $ (foldr (.) id (replicate 1000000 (showString "x"))) ""

run in a reasonable time (foldr is a bit faster because it has less overhead when composing functions from the right, but both are linear in the number of elements).

Answer 2

It's not too expensive on its own, the problem arises when you start combining a whole lot of ++ from left to right: such a chain is evaluated like

  ( ([1,2] ++ [3,4]) ++ [5,6] ) ++ [7,8]
≡ let a = ([1,2] ++ [3,4]) ++ [5,6]
        ≡ let b = [1,2] ++ [3,4]
                ≡ let c = [1,2]
                  in  head c : tail c ++ [3,4]
                    ≡ 1 : [2] ++ [3,4]
                    ≡ 1 : 2 : [] ++ [3,4]
                    ≡ 1 : 2 : [3,4]
                    ≡ [1,2,3,4]
          in  head b : tail b ++ [5,6]
            ≡ 1 : [2,3,4] ++ [5,6]
            ≡ 1:2 : [3,4] ++ [5,6]
            ≡ 1:2:3 : [4] ++ [5,6]
            ≡ 1:2:3:4 : [] ++ [5,6]
            ≡ 1:2:3:4:[5,6]
            ≡ [1,2,3,4,5,6]
  in head a : tail a ++ [7,8]
   ≡ 1 : [2,3,4,5,6] ++ [7,8]
   ≡ 1:2 : [3,4,5,6] ++ [7,8]
   ≡ 1:2:3 : [4,5,6] ++ [7,8]
   ≡ 1:2:3:4 : [5,6] ++ [7,8]
   ≡ 1:2:3:4:5 : [6] ++ [7,8]
   ≡ 1:2:3:4:5:6 : [] ++ [7,8]
   ≡ 1:2:3:4:5:6 : [7,8]
   ≡ [1,2,3,4,5,6,7,8]

where you clearly see the quadratic complexity. Even if you only want to evaluate up to the n-th element, you still have to dig your way through all those lets. That's why ++ is infixr, for [1,2] ++ ( [3,4] ++ ([5,6] ++ [7,8]) ) is actually much more efficient. But if you're not careful while designing, say, a simple serialiser, you may easily end up with a chain like the one above. This is the main reason why beginners are warned about ++.

That aside, Prelude.++ is slow compared to e.g. Bytestring operations for the simple reason that it works by traversing linked lists, which have always suboptimal cache usage etc., but that's not as problematic; this prevents you from achieving C-like performance but properly written programs using only plain lists and ++ can still easily rival similar programs written in e.g. Python.

Answer 3

I would like to add one thing or two to Petr's answer.

As he pointed out, repeatedly appending lists at the beginning is quite cheap, while appending to the bottom is not. This is true as long as you use haskell's lists. However, there are certain circumstances in which you HAVE TO append to the end (e.g., you are building a string to be printed out). With regular lists you have to deal with the quadratic complexity mentioned by his answer, but there's a way better solution in these cases: difference lists (see also my question on the topic).

Long story short, by describing lists as compositions of functions instead of concatenation of shorter lists you are able to append lists or individual elements at the beginning or at the end of your difference list by composing functions, in constant time. Once you're done, you can extract a regular list in linear time (in the number of elements).