How to remove nested parentheses in LISP

Question

How can I remove nested parentheses recursively in Common LISP Such as

  (unnest '(a b c (d e) ((f) g))) => (a b c d e f g)
  (unnest '(a b))                 => (a b)
  (unnest '(() ((((a)))) ()))     => (a)

Thanks

Whorish

You do not remove parentheses. Parentheses are just an aspect of a printed representation for lists. What you are doing is flattening lists. – Carothers

Answer 1

Here's what I'd do:

(ql:quickload "alexandria")
(alexandria:flatten list)

That works mainly because I have Quicklisp installed already.

Teleutospore

So modest! That works mainly because you created Quicklisp already. – Khalif

Answer 2

(defun flatten (l)
  (cond ((null l) nil)
        ((atom l) (list l))
        (t (loop for a in l appending (flatten a)))))

Mitochondrion

Because all the lists you append come from the list call in line 3, you can use nconcing instead of appending. – Booze

Answer 3

I realize this is an old thread, but it is one of the first that comes up when I google lisp flatten. The solution I discovered is similar to those discussed above, but the formatting is slightly different. I will explain it as if you are new to lisp, as I was when I first googled this question, so it's likely that others will be too.

(defun flatten (L)
"Converts a list to single level."
    (if (null L)
        nil
        (if (atom (first L))
            (cons (first L) (flatten (rest L)))
            (append (flatten (first L)) (flatten (rest L))))))

For those new to lisp, this is a brief summary.

The following line declares a function called flatten with argument L.

(defun flatten (L)

The line below checks for an empty list.

    (if (null L)

The next line returns nil because cons ATOM nil declares a list with one entry (ATOM). This is the base case of the recursion and lets the function know when to stop. The line after this checks to see if the first item in the list is an atom instead of another list.

        (if (atom (first L))

Then, if it is, it uses recursion to create a flattened list of this atom combined with the rest of the flattened list that the function will generate. cons combines an atom with another list.

            (cons (first L) (flatten (rest L)))

If it's not an atom, then we have to flatten on it, because it is another list that may have further lists inside of it.

            (append (flatten (first L)) (flatten (rest L))))))

The append function will append the first list to the start of the second list. Also note that every time you use a function in lisp, you have to surround it with parenthesis. This confused me at first.

Accursed

and is it tail recursive? – Provence

It’s not tail recursive and furthermore the question does not matter: the CL spec makes no requirements for tail call elimination and so one may not rely on it. This will blow up for long lists as well as deep lists. The solution from another answer using loop will only blow up for deep lists. – Booze

Answer 4

You could define it like this for example:

(defun unnest (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)))

Sp

Answer 5

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

Ovular

Answer 6

Lisp has the function remove to remove things. Here I use a version REMOVE-IF that removes every item for which a predicate is true. I test if the thing is a parenthesis and remove it if true.

If you want to remove parentheses, see this function:

(defun unnest (thing)
  (read-from-string
   (concatenate
    'string
    "("
    (remove-if (lambda (c)
                 (member c '(#\( #\))))
               (princ-to-string thing))
    ")")))

Note, though, as Svante mentions, one does not usually 'remove' parentheses.

Interurban

Answer 7

Most of the answers have already mentioned a recursive solution to the Flatten problem. Using Common Lisp Object System's multiple dispatching you could solve the problem recursively by defining 3 methods for 3 possible scenarios:

(defmethod flatten ((tree null))
  "Tree is empty list."
  ())
(defmethod flatten ((tree list))
  "Tree is a list."
  (append (flatten (car tree))
          (flatten (cdr tree))))
(defmethod flatten (tree)
  "Tree is something else (atom?)."
  (list tree))

(flatten '(2 ((8) 2 (9 (d (s (((((a))))))))))) ; => (2 8 2 9 D S A)

Inexactitude

Answer 8

Just leaving this here as I visited this question with the need of only flattening one level and later figure out for myself that (apply 'concatenate 'list ((1 2) (3 4) (5 6 7))) is a cleaner solution in that case.

Scarf

Answer 9

This is a accumulator based approach. The local function %flatten keeps an accumulator of the tail (the right part of the list that's already been flattened). When the part remaining to be flattened (the left part of the list) is empty, it returns the tail. When the part to be flattened is a non-list, it returns that part prefixed onto the tail. When the part to be flattened is a list, it flattens the rest of the list (with the current tail), then uses that result as the tail for flattening the first part of the list.

(defun flatten (list)
  (labels ((%flatten (list tail)
             (cond
               ((null list) tail)
               ((atom list) (list* list tail))
               (t (%flatten (first list)
                            (%flatten (rest list)
                                      tail))))))
    (%flatten list '())))

CL-USER> (flatten '((1 2) (3 4) ((5) 6) 7))
(1 2 3 4 5 6 7)

Stanzel

Answer 10

I know this question is really old but I noticed that nobody used the push/nreverse idiom, so I am uploading that here.

the function reverse-atomize takes out each "atom" and puts it into the output of the next call. At the end it produces a flattened list that is backwards, which is resolved with the nreverse function in the atomize function.

(defun reverse-atomize (tree output)
    "Auxillary function for atomize"
    (if (null tree)
      output
      (if (atom (car tree))
          (reverse-atomize (cdr tree) (push (car tree) output))
          (reverse-atomize (cdr tree) (nconc (reverse-atomize (car tree)
                                                               nil)
                                              output)))))

(defun atomize (tree)
    "Flattens a list into only the atoms in it"
     (nreverse (reverse-atomize tree nil)))

So calling atomize '((a b) (c) d) looks like this:

(A B C D)

And if you were to call reverse-atomize with reverse-atomize '((a b) (c) d) this would occur:

(D C B A)

People like using functions like push, nreverse, and nconc because they use less RAM than their respective cons, reverse, and append functions. That being said the double recursive nature of reverse-atomize does come with it's own RAMifications.

Laundry

Answer 11

This popular question only has recursive solutions (not counting Rainer's answer).

Let's have a loop version:

(defun flatten (tree &aux todo flat)
  (check-type tree list)
  (loop
     (shiftf todo tree nil)
     (unless todo (return flat))
     (dolist (elt todo)
       (if (listp elt)
           (dolist (e elt)
             (push e tree))
           (push elt flat))))))

Ichthyo

Answer 12

(defun unnest (somewhat)
  (cond
   ((null somewhat) nil)
   ((atom somewhat) (list somewhat))
   (t
    (append (unnest (car somewhat)) (unnest (cdr somewhat))))))

Avaricious

Answer 13

I couldn't resist adding my two cents. While the CL spec does not require tail call optimization (TCO), many (most?) implementations have that feature.

So here's a tail recursive version that collects the leaf nodes of a tree into a flat list (which is one version of "removing parentheses"):

(defun flatten (tree &key (include-nil t))
  (check-type tree list)
  (labels ((%flatten (lst accum)
             (if (null lst)
                 (nreverse accum)
                 (let ((elem (first lst)))
                   (if (atom elem)
                       (%flatten (cdr lst) (if (or elem include-nil)
                                               (cons elem accum)
                                               accum))
                       (%flatten (append elem (cdr lst)) accum))))))
    (%flatten tree nil)))

It preserves null leaf nodes by default, with the option to remove them. It also preserves the left-to-right order of the tree's leaf nodes.

Note from Google lisp style guide about TCO: You should favor iteration over recursion.

...most serious implementations (including SBCL and CCL) do implement proper tail calls, but with restrictions:

The (DECLARE (OPTIMIZE ...)) settings must favor SPEED enough and not favor DEBUG too much, for some compiler-dependent meanings of "enough" and "too much".

And this from SBCL docs: ... disabling tail-recursion optimization ... happens when the debug optimization quality is greater than 2.

Suspense