[plt-scheme] append!?

On Oct 21, 2007, at 6:45 PM, Majorinc, Kazimir wrote:
>
> 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.


It sounds like the problems you are talking about come from trying to  
write imperative style in the functional language.

The type above is a problem for recursive functions because "next" is  
not a list, so you can't process the first item and recurse on the rest.

So, how do you iterate through the list?  Many imperative languages  
have the concept of an "iterator", but often they mutate, so you  
can't hang on to one as a pointer into your list.  If you try to  
create a "functional iterator", I bet you'll find yourself  
reinventing the Lisp-style list -- your "iterator" will have three  
operations, something like "done?" "current-item" and "next".  And  
"next" will return a new iterator, not mutate anything.  In other  
words, you'll have: null?, car, cdr.

Rob