[plt-scheme] append!?

From: Robert Nikander (nikander at nc.rr.com)
Date: Sun Oct 21 22:37:48 EDT 2007

I know more about dysfunctional programming.

I shouldn't have said you "can't" write a recursive function with  
that list type.  I just meant that it is more convenient to write  
recursive functions with the normal scheme lists.


On Oct 21, 2007, at 9:52 PM, Matthias Felleisen wrote:

> 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.