Flattening a tree structure in Lisp

Question

I was struggling with flattening a tree structure. I was doing it recursively by comparing each atomic symbol to the rest in the tree but, a friend of mine suggested the following code which I think looks cleaner. I just don't understand the line:

((atom tree)(list tree))

I understand what each of them do individually, I also know that the loop below takes a list or it causes an error, which I suspect has a lot to due with the reason we're turning the symbol into a list if atom returns true. But I still don't feel like I fully understand the code.

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

An explanation would terrific if anyone could spare the time? Thanks!

Answer 1

The code is rather poorly formatted. In the first part of your question, it's not at all clear why

((atom tree) (list tree))

would appear in any Common Lisp code, since it looks like an attempt to call (atom tree), get a function back, and call that function with (list tree). In context, with proper formatting, it's clearer:

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

It's one clause in a cond. It says that if tree is an atom (which could be a symbol, a number, a vector, etc., anything else that isn't a cons), then return (list tree). As larsmans explained, flatten should always return a list, and this ensures that (flatten 3), for instance, will return (3). Since the (loop for a in tree ...) will work for any tree that is a list, there's really no need to have a case for (null tree), since nil/() is a list. This definition could be simplified to:

(defun flatten (tree)
  (if (atom tree)
      (list tree)
      (loop for a in tree
            appending (flatten a)))))

There are some similar questions out there on Stack Overflow, and some have almost identical code to what you posted (modulo the formatting). Did the friend was basing a suggestion on one of those. At any rate, for the sake of completeness, you might have a look at:

• flatten list in lisp
• Flatten Nests Function in Lisp - need help understanding (almost identical code)
• Common Lisp - flatting a list that may contain symbols (similar code)

Answer 2

I also know that the loop below takes a list or it causes an error, which I suspect has a lot to due with the reason we're turning the symbol into a list if atom returns true.

Spot on. The postcondition of flatten is that its result is always a flat list (not "a flat list or an atom"), so that the recursive calls need only handle one data type.

Answer 3

((atom tree)(list tree)) is a piece of syntax which cannot be understood on its own. It belongs to the cond syntax: it is known in Lisp culture as a cond pair. The cond pair says that if the (atom tree) expression is true, then (list tree) is evaluated. cond then terminates and returns that value.

The cond pair terminology is imprecise because in Common Lisp, the cond clauses are n-ary. They do not have to be pairs. The additional forms can be omitted entirely, so that the clauses are singleton items, allowing cond to be used like or:

(cond (a) (b) (c) ...) <==> (or a b c)

Here, a is evaluated. If it yields true (a value other than nil), then cond stops and returns the value of a. Otherwise it tests b and so on. That's exactly what the or does.

There can be two or more forms:

(cond (a p r s) (b t u) (c x y) ...)

If a yields true, then p r and s are evaluated, and the value of s is returned out of cond. If a yields false, then b is tried and so on.

cond is basically a generalized or, for which you pay with extra parentheses: try this case, or else try that case, etc.