Article 3998 of comp.lang.lisp:
Path: pt.cs.cmu.edu!rochester!rutgers!usc!wuarchive!decwrl!shelby!neon!news
From: iam@Gang-of-Four.Stanford.EDU (Ian Mason)
Newsgroups: comp.lang.lisp
Subject: deriving mirror
Message-ID: <1990Oct13.205439.7240@Neon.Stanford.EDU>
Date: 13 Oct 90 20:54:39 GMT
Sender: news@Neon.Stanford.EDU (USENET News System)
Organization: Computer Science Department, Stanford University
Lines: 73

Using the very elegant version of mirror by Noritake Yonezawa as
a specification of the desired algorithm:

(defun mirror (x) 
  (if (atom x)
      x
      (reverse (mapcar #'mirror x))))

We derive an efficient implementation of the algorithm. 
We first observe that since mapcar conses up a new list,
the spine of this list maybe safely reused. hence 
an operationally equivalent version is 

(defun mirror (x) 
  (if (atom x)
      x
      (nreverse (mapcar #'mirror x))))

This new version should now only need half the cons cells
of the origonal specification.
Now one possible definition of nreverse is the following

(defun nreverse (x) (nrev x nil))

(defun nrev (x y) (if x (nrev (cdr x) (rplacd x y)) y))

So unfolding the call to nreverse in the body of mirror results
in

(defun mirror (x) 
  (if (atom x)
      x
      (nrev (mapcar #'mirror x) nil)))

Now in the spirit of Scherlis we concentrate on simplifying
the expression  (nrev (mapcar #'mirror x) nil). To do this we
define the function f

(defun f (x y) (nrev (mapcar #'mirror x) y))

the aim now is to find a tail-recursive version of f.
Unfolding the call to mapcar and simplifying yields


(defun f (x y) 
  (if x
      (nrev (cons (mirror (car x)) (mapcar #'mirror (cdr x))) y)
      y))

Unfolding the call to nrev and simplifying yields

(defun f (x y) 
  (if x
      (nrev (mapcar #'mirror (cdr x)) (cons (mirror (car x)) y))
      y))

and now folding yields

(defun f (x y) (if x (f (cdr x) (cons (mirror (car x)) y))  y))

Thus the final result is the program

(defun mirror (x) 
 (labels ((f (x y) (if x (f (cdr x) (cons (mirror (car x))  y)) y)))
    (if (atom x)  x (f x nil))))


Of course to fairly compare these programs, as well as the other solutions
presented, one should time the compiled versions rather than the
interpreted ones.
 
--
		-iam-