[plt-scheme] append!?

From: Carl Eastlund (cce at ccs.neu.edu)
Date: Sun Oct 21 13:12:20 EDT 2007

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

Posted on the users mailing list.