flatten list in lisp

Question

So I've been looking at flattening a list in lisp.

However, what I wanted to do is flatten a list level by level.

So instead of having

(flatten '(a (b (d (g f))) e)) = (a b d g f e)

i want

(flatten '(a (b (d (g f))) e)) = (a b (d (g f )) e )

Any idea on how to do this guys?

Much appreciated =)

Answer 1

You could do something like this, for example:

(defun fletten-level (tree)
  (loop for e in tree
        nconc
        (if (consp e)
            (copy-list e)
          (list e))))

(fletten-level '(a (b (d (g f))) e))
;; (A B (D (G F)) E)

This loops over the original tree top-level branches and creates a new list containing if the branch was a leaf, that leaf, and if the branch had two other branches, then both the first leaf and the rest of the branches.

EDIT: sorry, it wasn't good the first time actually, now it should be fixed.

EDIT2: just because I almost got confused myself. (cons (car e) (cdr e)) looks a little weird because it is basically the same as saying just e. However, I realized that nconc will destructively modify the conses, so it has to be this way (i.e. create a new cons cell to be concatenated rather than reuse the old one).

EDIT3: Wow... actually, it has to be copy-list, because it will modify the original list this way.

Answer 2

Heres my quick and dirty take on a non-destructive version:

(defun flatten-level (tree)
  (cond ((null tree) ())
        ((consp (car tree)) (concatenate 'list (car tree) 
                                         (flatten-level (cdr tree))))
        (t (cons (car tree) (flatten-level (cdr tree))))))

This is a recursive function that walks the tree and for each element, if it is a cons'ed element it concatenates it onto the rest of the tree, flattened.