[plt-scheme] append!?

From: jerzy.karczmarczuk at info.unicaen.fr (jerzy.karczmarczuk at info.unicaen.fr)
Date: Sun Oct 21 11:06:50 EDT 2007

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. 

Jerzy Karczmarczuk 



Posted on the users mailing list.