[plt-scheme] append!?

From: Anton van Straaten (anton at appsolutions.com)
Date: Tue Oct 23 03:11:27 EDT 2007

Majorinc, Kazimir wrote:
> You didn't answered me on this :
> 
> <... on that way there is no significant difference between empty and 
> non-empty list, both are mutable. Obviously, it is not the Lisp way - 
> but it begs for the question, why not? Did original designer or anyone 
> else discussed it in some serious publication, or it was taken for 
> granted without much questioning?>
> 
> So, this particular list implementation with NIL used as a, say, 
> surrogate for empty list - is it well thought and discussed idea ended 
> with a conscious decision in the Lisp or Scheme community or it just 
> happened someone (McCarthy?) did it once, never explained it and nobody 
> really questioned it seriously? In the case it is conscious decision, 
> there should be significant body of a published material dealing with 
> subject, comparing pro's and contra's of a possibilities similar to few 
> discussed here.

There's plenty of literature on the singly-linked list.  You'll notice 
that much of that literature points out that they are the simplest, most 
basic kind of list, just as the pairs they're built from are the 
simplest, most basic kind of structure.  That means you can easily use 
either to build other kinds of structure, which would be less 
appropriate if either of them were more complex.  You don't build bricks 
out of houses.

(Actually, a more nuanced perspective on this is that the 
theoretically-inclined tend to like to build up from simple structures 
for tractability reasons, whereas the engineering-inclined will often 
use the richest structure they can "afford", for reasons which are 
intended to be pragmatic.  Scheme is in the former camp; some of the 
popular OO languages are in the latter.)

Since the "node" type that you defined is a singly-linked list, 
equivalent to Scheme's list type, you already have most of what you're 
asking for.  All you need is a simple wrapper type to give you the kind 
of lists you want.

However, you'd need a very good argument for replacing the simplicity of 
simple singly-linked lists with a more complex structure as a core data 
type.  Being able to mutate the empty list is at best a corner case, not 
a general requirement, and it's demonstrably unnecessary.

Anton



Posted on the users mailing list.