Find the most nested list inside the list in Common Lisp

Question

I am new to Common Lisp and functional programming, but I have a lot of experience in languages ​​like C, C ++, C #, Java, etc. I am having trouble finding the most nested list inside the list. My input looks something like this:

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

I would like to get the most nested list inside this list, which in this case

 (7) 

I had the idea that I can somehow smooth the list until there is only one additional list left. To illustrate what I mean, follow these steps:

Step 1. - input:

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

Step 2. - smooth on the "first level":

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

Step 3. - smooth on the "second level":

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

Now only one nested list is left, which means that this is the most nested list. But I see a problem here when two or more such lists appear. Share your thoughts on this.

I'm having trouble implementing this procedure in Common Lisp, so I would be grateful for some pointers in the right direction, maybe in some sample code, and so on. This is homework, so I do not expect a complete solution, but I would be glad if someone pointed out, perhaps, an easier and better solution and its implementation.

Answer 1

Here is my (not very clean) solution in CL:

 (defun deepest-list (lst) (let ((max-depth 0) ret) (labels ((inner-deepest-lst (lst depth) (cond ((null lst) depth) ((listp (car lst)) (let ((local-max (max (inner-deepest-lst (first lst) (1+ depth)) (inner-deepest-lst (rest lst) (1+ depth))))) (and (> local-max max-depth) (setf ret (first lst) max-depth local-max)) local-max)) (t (inner-deepest-lst (rest lst) depth))))) (inner-deepest-lst lst 1)) ret)) 

edit:

After a second thought, this is a slightly cleaner solution:

 (defun deepest-list (lst) (labels ((dl (lst depth) (cond ((atom lst) (cons 0 lst)) ((every #'atom lst) (cons depth lst)) (t (funcall (lambda (xy) (if (> (car x) (car y)) xy)) (dl (car lst) (1+ depth)) (dl (cdr lst) depth)))))) (rest (dl lst 0)))) 

Answer 2

Here is my solution using a similar approach to OP. (In the case of the few deepest elements, they all return.)

I wrote it in Scheme, which probably won't translate to Common Lisp right away, so I don't feel like it will be a full sale. However, it has the potential to be spoilery, so proceed with caution.

 (define (deepest lst) (let ((filtered (filter pair? lst))) (cond ((null? filtered) lst) (else (deepest (concatenate filtered)))))) 

Answer 3

Your approach to iteratively aligning the list should probably work fine, although this is not the most efficient or (subjectively) elegant way to do this.

If there is more than one such list, the correct result will depend on the specification - should all of them be returned, or only the first, or cause an error?

If I were you, I would try to find a recursive function to solve the problem. Each recursion level will mainly process elements of a given level of nested lists. Think about what each recursive call should do - it's very simple if it clicks!