This is a read-only archive of lispforum.com. The forum was locked to new users and posts and is preserved here as static HTML from a database snapshot taken on 2019-09-07.

how should flatten be defined?

2 posts · 920 views

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?

Re: how should flatten be defined?

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

So the following are equivalent.
(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.