[plt-scheme] append!?

On 10/21/07, jerzy.karczmarczuk at info.unicaen.fr
<jerzy.karczmarczuk at info.unicaen.fr> wrote:
> Carl Eastlund writes:
>
> > <jerzy.karczmarczuk at info.unicaen.fr> wrote:
> >> The append! function - whatever say people who would like to change the
> >> specification of Scheme, is an *economic* procedure, which avoids the
> >> copying of the *left*, first argument. This, especially in a recursive
> >> context, may transform a linear algorithm into quadratic.
> >
> > I'm skeptical of that last claim.  The append function is linear, it
> > just has different constant factors to its running time and less space
> > consumption than append! (linear, rather than none).  Linear plus
> > linear is still linear, not quadratic.  Where would increased time
> > complexity come from?
>
> OK, I should be more precise, sorry for the mess. I wasn't defending
> append!, rather criticizing append. append is *always* linear in the length
> of the first argument, there is nothing you can do about. The *usage*
> of append! need not be, it may be constant. Imagine that in a program
> where the concatenation is frequent, you keep together with the list,
> a pointer to its last cons cell, in which case the original append!
> may be reduced to the append! of this last cell.
>
> Well, then obviously there is no need for append!, set-cdr! suffices...
> But in order to simplify the program, this auxiliary access can be hidden,
> and an optimized append! defined.

That's not append!, though.  That's a different function that only
operates in programs that (a) maintain tail pointers and (b) don't
allow undisciplined set-cdr!.  The general Scheme function append!
cannot rely on either of those: Scheme allows undisciplined set-cdr!,
which in turn may invalidate any tail pointers (potentially multiple
at once, due to shared list tails).  I'm pretty sure the normal
append! needs to be linear.

-- 
Carl Eastlund