Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!decwrl!hayes.fai.alaska.edu!accuvax.nwu.edu!anaxagoras!krulwich
From: krulwich@ils.nwu.edu (Bruce Krulwich)
Newsgroups: comp.lang.lisp
Subject: Re: Adding items to the end of a list.
Message-ID: <1623@anaxagoras.ils.nwu.edu>
Date: 5 Sep 90 17:35:21 GMT
References: <1990Sep5.011910.1177@mentor.com>
Sender: news@anaxagoras.ils.nwu.edu
Reply-To: krulwich@ils.nwu.edu (Bruce Krulwich)
Organization: Institute for the Learning Sciences, Northwestern University, Evanston, IL 60201
Lines: 45
In-reply-to: plogan@mentor.com (Patrick Logan)

plogan@mentor (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? 

It's more complicated than that.  In and of itself it's more efficient to
construct a list backwards, because a good compiler can use register
operations instead of memory operations (in T under Orbit, for example, this
makes a big difference).  In the cases when you don't have to do the
reversal (say, order doesn't matter, or you can keep it reversed for a
while) it's better to do it backwards.  Obviously, the reversal cost
probably outweighs the gains in register op's, so in general you're right if
you have to do the reversal, but it's not as simple as you say.


>Here is a procedure (in Scheme) that copies a list by adding items to
>the end of a list and then returns that list.
>
>(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)))))))

You can make this a bit better (getting rid of the wasted HEADER CONS cell)
by special casing the (NULL? lis) case and then starting off header with the
copy of the first element:

(define (COPY-LIST lis)
  (if (null? lis)
      nil
    (let ((header (list (car lis))))
      (let loop ((tail header) (lis (cdr lis)))
        (if (null? lis)
            header
            (begin (set-cdr! tail (cons (car lis) '()))
                   (loop (cdr tail) (cdr lis))))))))


Bruce Krulwich
Institute for the Learning Sciences