if (++) were left associative ?

Konst Sushenko konsu@microsoft.com
Sun, 7 Apr 2002 01:46:51 -0800


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 =3D (++)
        cat2 =3D (++)

        ( [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?