Find the most nested list inside a list in Common Lisp

Question

I'm new to Common Lisp and functional programming, but I have a lot of experience in languages like C, C++, C#, Java and so on. I'm having trouble finding the most nested list inside a list. My input is 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 is

(7)

I did have an idea that I could flatten the list somehow, until there was only one sub-list left. To illustrate what I mean, here is a few steps:

Step 1. - input:

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

Step 2. - flatten on "first level":

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

Step 3. - flatten on "second level":

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

Now there's only one nested list left, which means that was the most nested list. But I see a problem here, when two or more such lists would occur. Please share your thoughts on this.

I'm having problems putting this procedure to reality in Common Lisp, so I would be grateful for some pointers in the right direction, maybe some example code and so on. This is a homework assignment, so I don't really expect a full solution, but would be glad if someone pointed out perhaps an easier and better solution and its implementation.

Answer 1

Here's my solution, using a similar approach to the OP's. (In the case of multiple deepest items, they are all returned.)

I wrote it in Scheme, which probably won't be immediately translatable to Common Lisp, so I don't feel that it'd be a complete giveaway. Still, it has the potential to be spoilery, so tread with caution.

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

Answer 2

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 (x y) (if (> (car x) (car y)) x y))
               (dl (car lst) (1+ depth))
               (dl (cdr lst) depth))))))
    (rest (dl lst 0))))

Answer 3

Your approach of iteratively flattening the list should probably work fine, although it's not the most efficient or (subjectively) elegant way to do it.

If there are more than one such list, the correct output would depend on the specification -- should you return all of them, or just the first one, or throw an error?

If I were you, I'd look in to coming up with a recursive function to solve the problem. Each level of recursion would basically process the elements of a given level of the nested lists. Think of what each recursive call should do -- it's very simple if once it clicks!