[plt-scheme] append!?

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Sun Oct 21 21:52:57 EDT 2007

I don't know what functional programming is but Kazimir's type  
description is perfectly fine data description for Scheme:

   ListB is (box List)

   List is one of:
    -- null
    -- (cons Data List)

   Note: List is the built-in type.

Now you really want to "lift" functions from the built-in type List  
to ListB, e.g.,

  (define (mapB f l)
    (set-box! l (map f (unbox l))))

  (define (appendB l1 l2)
    (set-box! l1 (append l1 l2)))

etc.

All he loses is the immediate applicability of the existing library.  
Ugly but doable.

Unless he meant something else. -- Matthias










On Oct 21, 2007, at 8:32 PM, Robert Nikander wrote:

>
> 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
>
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme



Posted on the users mailing list.