Flatten Nests Function in Lisp - need help understanding

Question

I've been trying to find a way to condense nested lists into numbers that go back in the original list, but I having some trouble.

I've been looking at the flatten function (that is so widely available) which is given here:

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

I understand this example is recursion, but how does it work? It check if the element is null or an atom, but what does it do if the element falls into these conditions?

Answer 1

In my day instead of (loop for a in l appending (g a)) we wrote (mapcan #'g l). Which is equivalent to (apply #'append (mapcar #'g l)), more or less:

(defun flatten (l) 
    (if l 
        (if (atom l) 
            (list l) 
            (mapcan #'flatten l))))

So what does it mean in this case? Imagine you call (flatten (list 1 2 3 4 5)), i.e. the argument list has only atoms in it. Each atom in that list gets enclosed in a list -- becomes a singleton list, like (1) (2) etc. Then they are all appended together, giving us back ... the original list:

(  1   2   3   4   5  )

( (1) (2) (3) (4) (5) )

(  1   2   3   4   5  )

So flattening a list of atoms is an identity operation (in Common LISP, that's #'identity). Now imagine flattening a list which has some atoms in it as well as a list of atoms. Again, each element of the list gets transformed by flatten and then they are all appended together. A list of atoms stays as itself, as we just saw. Atoms get enclosed each in a list. So appending will give us back all the atoms that were on both levels in the nested list, now flattened:

(  11   12  (1 2 3 4)  13  )

( (11) (12) (1 2 3 4) (13) )

(  11   12   1 2 3 4   13  )

And so on and so forth, for more levels of nesting as well.

NILs as elements in lists pose a problem. NIL is an empty list, and empty list contains nothing, so should not contribute anything. But NIL is also an atom. So we make a special case for it, to not enclose it in a singleton list - leave it as it is, so when appended, it'll just disappear.

Answer 2

(defun flatten (l)

Above defines a function FLATTEN with one argument called L.

  (cond

IF

    ((null l) nil)

the value of the argument L is the empty list, return the empty list.

    ((atom l) (list l))

or if the argument L is an atom (i.e. not a list), then return a list with the atom as its only item.

    (t 

or else we have a non-empty list

       (loop for a in l

then loop through all the items in the list which is the value of L

        appending (flatten a)

and append the results of flattening each list item.

))))