if (++) were left associative ?

[Konst Sushenko]

Thanks,

but you are assuming that foldl evaluates the intermediate result right
away. If it were, then I have no problem seeing why time is quadratic. I
am concerned about laziness though...

My understanding of foldl is thus:

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]

Which brings me back to my original question...


> -----Original Message-----
> From: David Feuer [mailto:dfeuer@cs.brown.edu]=20
> Sent: Sunday, April 07, 2002 3:21 AM
> To: haskell-cafe@haskell.org
> Subject: Re: if (++) were left associative ?
>=20
>=20
> On Sun, Apr 07, 2002, Konst Sushenko wrote:
> > Hello,
> >=20
> > this is probably embarrassing, but I just realised that I do not
> > understand why list concatenation operation takes quadratic=20
> time if it
> > is associated from left to right (see e.g. 'The Haskell School of
> > Expression' by Hudak, p. 335):
> >=20
> >         cat1 =3D (++)
> >         cat2 =3D (++)
> >=20
> >         ( [1,2] `cat1` [3,4] ) `cat2` [5,6]
> >=20
> >=20
> > My understanding is that cat2 is invoked before cat1, and=20
> as soon as the
> > first element of cat1 is available, cat2 starts building=20
> its own result.
> > cat2 does not need to wait until the whole list is emitted=20
> by cat1, does
> > it? Where is quadratic time complexity?
>=20
> Suppose we define
>=20
> listseq [] x =3D x
> listseq (a:b) x =3D listseq b x
>=20
> l =3D [1..n]
>=20
> inter =3D foldl (++) [] (map (:[]) foo)
>=20
> final =3D listseq inter inter
>=20
>=20
> 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=20
> bit.... I'm not
> sure if the way they are chained still allows this to be=20
> considered the
> shared cost, but I'm not sure).
>=20
> 1.  How long does it take to calculate final ?
> Well, let's try it for n =3D 4:
>=20
> inter =3D foldl (++) [] [[1],[2],[3],[4]]
>       =3D foldl (++) ([]++[1]) [[2],[3],[4]] =3D foldl (++) [1]=20
> [[2],[3],[4]]
>       =3D foldl (++) ([1]++[2]) [[3],[4]] =3D foldl (++) [1,2] =
[[3],[4]]
>       =3D foldl (++) ([1,2]++[3]) [[4]] =3D foldl (++) [1,2,3] [[4]]
>       =3D foldl (++) ([1,2,3]++[4]) [] =3D foldl (++) [1,2,3,4] []
>       =3D [1,2,3,4]
>=20
> Note that in successive iterations, the following are calculated:
>=20
> []++[1]
> [1]++[2]
> [1,2]++[3]
> [1,2,3]++[4]
>=20
> Since l1++l2 takes order length(l1), each concatenation takes=20
> more time
> than the previous one (linearly), so the total time for all of them is
> quadratic.
>=20