if (++) were left associative ?

[Iavor Diatchki]

greetings,

the problem is that (++) rebuilds its first argument.
in the example bellow the leftmost ++ rebuilds a list 
of length 0, the next (++) rebuilds a list of length 1,
next one rebuilds a list of length 2, etc.  this is where
the quadratic complexity comes in.  i am counting how many consings
are happening. of course this is only quadratic if you need
all the elements in the new list.  if as in the example bellow
you only need the head of the list, you only need to rebuild
enough to get it.  you noticed that you need to
call ++ 3 times (and in general as many times as there are ++s,
so we have a linear-time opertaion).
in contrast, if the ++s were associated to the right, this is
a constant time operation. 

and of course if you dont use any of the new list the whole thing
happens in constant time :-)

bye
iavor

On Sun, Apr 07, 2002 at 12:04:04PM -0700, Konst Sushenko wrote:
> Thanks, but it still does not help...
> 
> 
> > Well, you've removed the parentheses that give you the
> > information you want.
> > 
> 
> Yes, I overlooked the parentheses. I meant what you said below:
> 
> > foldl (++) [] [[1],[2],[3],[4]]
> ...
> > -> (((([] ++ [1]) ++ [2]) ++ [3]) ++ [4])
> > 
> 
> > now you have to ask what has to be evaluated in order to get
> > the head of the result.
> > 
> > The answer is that you have to evaluate ((([] ++ [1]) ++
> > [2]) ++ [3]) before you can find it, and to get that, you
> > have to evaluate (([] ++ [1]) ++ [2]) and so on.
> > 
> 
> I understand that I have to evaluate all that to get the head of the
> result, I just do not see how this ends up being quadratic. I have no
> problem seeing that if each function's argument had to be evaluated
> before the function is called but this is not the case here, right?
> 
> To simplify, lets have (([] ++ [1]) ++ [2]) ++ [3].
> 
> To get the head of result (++) is called recursively three times. The
> last invocation returns [1] because its left argument is []. The
> invocation before it (... ++ [2]) receives [1], and can return (1:..)
> now, so it does. It does not finish constructing its whole result before
> something is returned to (... ++ [3]). Here is the root of my
> misunderstanding. The way I see it is that every time an element is
> output by (++) at the bottom of the invocation chain, it is propagated
> up the chain. No?
> 
> konst
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

-- 
---------------------------------------+----------------------------------------
Iavor S. Diatchki                      | email: diatchki@cse.ogi.edu           
Dept. of Computer Science              | web: http://www.cse.ogi.edu/~diatchki
OGI School of Science and Engineering  | work phone: 5037481631                
OHSU                                   | home phone: 5034996536
---------------------------------------+----------------------------------------