An Early LISP Program

March 1, 2011

Today we have another exercise in our continuing theme of historical computing, celebrating the publication of the Lisp I Programmer’s Manual on this date fifty-one years ago. Over at his blog Abstract Heresies, LISP/Scheme expert and general curmudgeon Joe Marshall recalls this program from that manual, written by Phyllis Fox:

   ((ATOM,L), (CONS,L,NIL))
COLLAPSE ((((A,B),((C))),((D,(E,F)),(G),((H))))) ()
COLLAPSE ((A,(B,(C,(D,(E))),F,(G,(H,J))))) ()
COLLAPSE ((((((A),B),C),D),E)) ()

The program collapses a nested list into an un-nested one. Here’s the same program in modern Lisp:

(defun collapse (l)
  (cond ((atom l) (cons l nil))
        ((null (cdr l))
         (cond ((atom (car l)) l)
             (t (collapse (car l)))))
        (t (append (collapse (car l))
                   (collapse (cdr l))))))

Your task is to write a function to un-nest a nested list. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2