Lisp smoothing function in Lisp - need help

Question

I am trying to find a way to condense nested lists into numbers that return to the original list, but I have some problems.

I looked at the smoothing function (which 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 checks if the element is zero or an atom, but what does it do if the element falls into these conditions?

Answer 1

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

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

So what does that mean in this case? Imagine that you are calling (flatten (list 1 2 3 4 5)) . Each atom of your list falls into the list - it becomes a list of singleton, for example (1) (2) , etc. Then they are all added together, returning to us ... the original list:

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

Thus, smoothing the list of atoms is an id operation (in Common LISP, #'identity ). Now imagine that you are compacting a list that has atoms, as well as a list of atoms. Again, each item in the list is converted to flatten , and then they all join together. The list of atoms remains as it is, as we just saw. Atoms are on the list. Thus, the addition will return to us all the atoms that were at two levels in the nested list, are 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.

NIL , because items in lists create a problem. NIL is an empty list, and an empty list does not contain anything, so it should not contribute anything. But NIL also an atom. Therefore, we are making a special case for it, so as not to enclose it in a singleton list - leave it as it is, so when you add it it just disappears.

Answer 2

 (defun flatten (l) 

The FLATTEN function with one argument L defined above.

  (cond 

IF

  ((null l) nil) 

argument value L is an empty list; returns an empty list.

  ((atom l) (list l)) 

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

  (t 

otherwise we have a non-empty list

  (loop for a in l 

then iterate over all the items in the list, which is the value of L

  appending (flatten a) 

and add the smoothing results of each item in the list.

 )))) 

Answer 3

• If the item you are looking at is nil the end of the list, return zero.

• If the item you are looking at is not a list returning a list containing that element (I'm not sure if this is correct, because given an atom that is not a list, it will return a list with an atom, not the atom itself).

• Otherwise (if this is a list), swipe through it all the elements and add all the flattened subtrees (which you smooth out by calling flatten ), and then return them.

This is a short but not the most efficient algorithm, since the append must go all the way to the end of the list in order to combine one part with the tail of the other part. Below is a bit confusing, but looks like a more efficient version:

 (defun flatten (x &optional y) (cond ((null x) (cond ((null y) nil) ((listp (car y)) (flatten (car y) (cdr y))) (t (cons (car y) (flatten (cdr y)))))) ((listp (car x)) (flatten (car x) (if y (list (cdr x) y) (cdr x)))) (t (cons (car x) (flatten (cdr x) y))))) 

The algorithm of this function performs the following:

• If we have neither the first element, nor the rest - we did everything, so just return nil (end of list).

• If there is no first element, divide the second into the first, and the rest and repeat.

• If there is a first element, it delays it in the list; if there is a second element, save it, otherwise select the next element and repeat.

EDIT: I changed # 3 because the interpretation was really vague / maybe wrong.