# if (++) were left associative ?

**David Feuer
**
dfeuer@cs.brown.edu

*Sun, 7 Apr 2002 06:21:20 -0400*

On Sun, Apr 07, 2002, Konst Sushenko wrote:
>* Hello,
*>*
*>* this is probably embarrassing, but I just realised that I do not
*>* understand why list concatenation operation takes quadratic time if it
*>* is associated from left to right (see e.g. 'The Haskell School of
*>* Expression' by Hudak, p. 335):
*>*
*>* cat1 = (++)
*>* cat2 = (++)
*>*
*>* ( [1,2] `cat1` [3,4] ) `cat2` [5,6]
*>*
*>*
*>* My understanding is that cat2 is invoked before cat1, and as soon as the
*>* first element of cat1 is available, cat2 starts building its own result.
*>* cat2 does not need to wait until the whole list is emitted by cat1, does
*>* it? Where is quadratic time complexity?
*
Suppose we define
listseq [] x = x
listseq (a:b) x = listseq b x
l = [1..n]
inter = foldl (++) [] (map (:[]) foo)
final = listseq inter inter
Then inter will be the result of concatenating [1],[2],[3],... from
left to right. One meaningful question is: how long will it take to
calculate "final"? This is (I believe) called the _shared cost_ of
inter (while inter does not actually do any significant work, it
produces a chain of suspensions that together do quite a bit.... I'm not
sure if the way they are chained still allows this to be considered the
shared cost, but I'm not sure).
1. How long does it take to calculate final ?
Well, let's try it for n = 4:
inter = foldl (++) [] [[1],[2],[3],[4]]
= foldl (++) ([]++[1]) [[2],[3],[4]] = foldl (++) [1] [[2],[3],[4]]
= foldl (++) ([1]++[2]) [[3],[4]] = foldl (++) [1,2] [[3],[4]]
= foldl (++) ([1,2]++[3]) [[4]] = foldl (++) [1,2,3] [[4]]
= foldl (++) ([1,2,3]++[4]) [] = foldl (++) [1,2,3,4] []
= [1,2,3,4]
Note that in successive iterations, the following are calculated:
[]++[1]
[1]++[2]
[1,2]++[3]
[1,2,3]++[4]
Since l1++l2 takes order length(l1), each concatenation takes more time
than the previous one (linearly), so the total time for all of them is
quadratic.
David Feuer