[plt-scheme] append!?

From: Majorinc, Kazimir (kazimir at chem.pmf.hr)
Date: Sun Oct 21 18:45:21 EDT 2007

Matthew Flatt wrote:
> Also, `append!' is going away in v4.0, since `cons' will create
> immutable pairs, `append' will append immutable lists, and so on.
>   
So, we'll have to create new list if we want to insert single element at 
the end of the list? In some circumstances it is slow. What will be the 
cure for that?

>> i.e. linked lists that start with cell (cons) instead of 
>> pointer to cons (that could be nil for empty list) are good only if one 
>> does not need empty list at all.
>>     
>
> I think you have in mind a mutable-container abstraction, such as
> Java's "LinkedList". But that kind of container is different from a
> Scheme "list".
>   

I don't know about Java, but it is kind of a common knowledge. If one 
want single linked lists that could change dynamically he usually does 
something like

type list is record
   next: (pointer to node) or NIL;
end
type node is record
  data: pointer to anything;
  next: (pointer to node) or NIL
end

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? I know, it is almost trivial topic, 
but I suspect it caused small but numerous troubles to Lisp users and 
implementors due to unnecessarily special nature of the empty list.




Posted on the users mailing list.