1

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 =)

Kelsey Abreu
  • 1,094
  • 3
  • 17
  • 42

2 Answers2

6

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.

4

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.

munksgaard
  • 116
  • 4
  • 1
    the version in the other answer is non-destructive too; it uses `nconc` as an implementational tool, but it will only alter the structure freshly allocated with either `list` or `copy-list`. As such, it builds its result in a top-down manner, without extra "consing" or recursion, so is efficient. That's what your code, being ["tail recursive modulo cons"](http://en.wikipedia.org/wiki/Tail_call#Tail_recursion_modulo_cons), could be plausibly *compiled* to (or automatically rewritten) by a system implementing the TRMC optimization. – Will Ness Nov 02 '12 at 08:52