Xref: utzoo comp.lang.lisp:3587 comp.lang.scheme:1627
Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!mit-eddie!uw-beaver!zephyr.ens.tek.com!tektronix!sequent!mntgfx!plogan
From: plogan@mentor.com (Patrick Logan)
Newsgroups: comp.lang.lisp,comp.lang.scheme
Subject: Adding items to the end of a list.
Summary: Reversing backward lists is inefficient.
Message-ID: <1990Sep5.011910.1177@mentor.com>
Date: 5 Sep 90 01:19:10 GMT
Followup-To: comp.lang.lisp
Organization: engr
Lines: 55

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