How does this piece create list of all sublists for a given list?

Question

Can someine please explain me the following piece of code? I understand what every small piece does, but can't seem to understand how they all work together The function is getting a list such as:

(1 2 (3 (4 5) (6 7)) 8 (9 10))

which has 5 sublists and it returns the list of all sublists:

((1 2 (3 (4 5) (6 7)) 8 (9 10)) (3 (4 5) (6 7)) (4 5) (6 7) (9 10))

The code is:

(defun all_sublists (l)
    (cond
        ((atom l) nil)
        (T (apply 'append (list l) (mapcar 'all_sublists l)))
    )
)

i understand that first cond says if l is an atom return nil, but can you please explain me what does the second line? Why is there that T which i understand means True, and can you explain it to me as simple as possible?

Renzo Renzo · Accepted Answer · 2020-12-13T14:26:23

all_sublists is a typical recursive function. When analysing a recursive function like this we can procede in this way:

Before looking at that implementation of the function, we assume that it is correct. So what does this function? We have been told that it takes a list containg sublists, and returns a new list with the concatenation of the original list with all its sublists (recursively, so if an internal sublist contains other sublists those are returned together with internal sublist). So we assume that this is true, and look at the function.
The first line is simple to understand: in the case of an empty list, that is a list with no elements, neither atom nor sublists, we return nil which is in fact the list itself, and this is in accord with the definition of the function.
To understand the second line, we start from the internal expression. So, what does (mapcar 'all_sublists l)? mapcar returns a list obtained by concatenating the results of applying a certain function to all the elements of a list. Here we apply all_sublists to all the elements of l, so we return a list containing the results of all such applications: in other words, the results of applying all_sublists to each element of l. When an element is an atom, it returns nil, while, if an element is a list, it returns the list obtained by concatenating such element with all its sublists (we know already what all_sublists returns!). So a list with all those results are returned. Now look at the outer expression: (apply 'append (list l) the-result-of-mapcar). apply applies a function (in this case append) to a list of argument. So, in this case, we append, to the list containing as unique element the original list l, the-result-of-mapcar. So we obtain a list constitued by l and all its sublists, produced recursively by the function.

Just a final note: this seems in some way “magic”, or maybe “absurd”. Don't be discouraged if intially you do not completely understand it. We all had this same sensation. But if you insist in trying to understand this kind of recursion, you will eventually succeed!

How does this piece create list of all sublists for a given list?

1 Answers