how should flatten be defined?

[npolyspace]

I have done some programming for a while, and often want to flatten a list. The definition I find in places like onlisp is:

(defun flatten (x)
(labels ((rec (x acc)
(cond ((null x) acc)
((atom x) (cons x acc))
(t (rec (car x) (rec (cdr x) acc))))))
(rec x nil)))

Then when I do something like:
(flatten '(a b c nil d (e f nil g) nil h))
I get
(A B C D E F G H)
in stead of what I really wanted:
(A B C NIL D E F NIL G NIL H)

So I can write:
(defun flatten (x)
(labels ((rec (x acc)
(cond ((null x) acc)
((atom x) (cons x acc))
((equalp (first x) nil) (cons nil (rec (cdr x) acc))) ;I added this line
(t (rec (car x) (rec (cdr x) acc))))))
(rec x nil)))

to get what I wanted. Why is flatten written this first way?

[nuntius]

I think its because NIL is the same as an empty list.

So the following are equivalent.

Code: Select all

(flatten '(a b c nil d (e f nil g) nil h))
(flatten '(a b c () d (e f () g) () h))

When you look at this second form, I think the answer is obvious. Most of the time, this equivalence between NIL and the empty list is handy; but occasionally it does bite.