[comp.lang.scheme] Adding items to the end of a list.

plogan@mentor.com (Patrick Logan) (09/05/90)

I see a lot of LISP code building lists backwards and then reversing
them. I don't know if I've ever seen any C code doing that. Is it too
easy to write sloppy code in LISP? I don't think it is any more
difficult to write efficient list manipulations in Scheme than it is
in C.

Here is a procedure (in Scheme) that copies a list by adding items to
the end of a list and then returns that list. This isn't taught in the
Little LISPer, but it's not beyond the typical C programmer's
abilities.

(define (COPY-LIST lis)
  (let ((header (cons #f '()))) ; Ignore the #f, build the list in the cdr.
    (let loop ((tail header) (lis lis))
      (if (null? lis)
	  (cdr header)
	  (begin (set-cdr! tail (cons (car lis) '()))
		 (loop (cdr tail) (cdr lis)))))))

Here is an "object" that responds to two messages. For the cost of
building a closure of a few words in size, it abstracts the code for
adding items to the end of a list.

Messages:
((object 'EXTEND!) item) ....... Add item to the end of the list.
(object 'LIST) ................. Return the list.

Scheme->C -- 23feb90jfb -- Copyright 1989 Digital Equipment Corporation
> (define (MAKE-TAIL-LIST)
    (let* ((head (cons #f '())) ; Ignore the #f, use for tail-cons'ing.
           (tail head))
      (lambda (msg)
        (case msg
          ((extend!)
           (lambda (item)
             (let ((new-tail (cons item '())))
               (set-cdr! tail new-tail)
               (set! tail new-tail))))
          ((list) (cdr head))))))
MAKE-TAIL-LIST
> (define a (make-tail-list))
A
> (a 'list)
()
> ((a 'extend!) 1)
(1)
> ((a 'extend!) 2)
(2)
> ((a 'extend!) 3)
(3)
> (a 'list)
(1 2 3)
-- 
Patrick Logan, uunet!mntgfx!plogan
Mentor Graphics Corp. 8500 SW Creekside, Beaverton, Oregon 97005-7191

briscoe-duke@cs.yale.edu (Duke Briscoe) (09/06/90)

In article <1990Sep5.011910.1177@mentor.com> Patrick Logan writes:
>I see a lot of LISP code building lists backwards and then reversing
>them. I don't know if I've ever seen any C code doing that. Is it too
>easy to write sloppy code in LISP? I don't think it is any more
>difficult to write efficient list manipulations in Scheme than it is
>in C.
>

I did some timings on compiled T code, and the difference between
copying a list using your copy-list function and using a function
(define (dcl lis) (reverse! (reverse lis))) was only 20%, the
important thing being that this is an algorithmic difference of a
small constant factor.  The reverse functions in T are coded in T, not
hand-coded assembly by the way.  If the operations used to build the
elements of the list are expensive (just copying the elements is the
least expensive thing I can think of) then the reverse! step is going
to make relatively less of a percentage difference.  I think in many
cases there isn't going to be much difference.  If someone is using
reverse instead of reverse! then that could be more serious because of
the extra consing.  I think the important thing is that the standard
functions be coded efficiently, but for most user applications a
person doesn't need to get involved with potentially tricky pointer
manipulations.

Duke