[plt-scheme] append!?

From: Carl Eastlund (cce at ccs.neu.edu)
Date: Sun Oct 21 08:50:32 EDT 2007

On 10/21/07, jerzy.karczmarczuk at info.unicaen.fr
<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?

Carl Eastlund

Posted on the users mailing list.