Encuentra la lista más anidada dentro de una lista en Common Lisp

Question

Soy nuevo en Common Lisp y en la programación funcional, pero tengo mucha experiencia en lenguajes como C, C++, C#, Java, etc. Tengo problemas para encontrar la lista más anidada dentro de una lista. Mi entrada es algo como esto:

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

me gustaría obtener la lista más anidada dentro de esta lista, que en este caso es

(7) 

Yo tenía una idea de que podía aplanar la lista de alguna manera , hasta que solo quedaba una sub-lista. Para ilustrar lo que quiero decir, aquí hay un par de pasos:

Paso 1. - Entrada:

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

Paso 2. - aplanar el "primer nivel":

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

el paso 3. - aplanar el "segundo nivel":

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

Ahora sólo hay una lista anidada a la izquierda, lo que significa que fue la lista más anidada. Pero veo un problema aquí, cuando dos o más de esas listas ocurrirían. Por favor comparte tus pensamientos sobre esto.

Tengo problemas para hacer que este procedimiento se vuelva realidad en Common Lisp, así que agradeceré algunos consejos en la dirección correcta, tal vez algún código de ejemplo, y así sucesivamente. Esta es una tarea para el hogar, por lo que realmente no espero una solución completa, pero estaría contento si alguien señalara quizás una solución más fácil y mejor y su implementación.

Answer 1

Aquí está mi solución (no muy limpio) en la 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)) 

edición:

Después de un segundo pensamiento, esta es una solución un poco más limpio:

(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 2

Su enfoque de aplacar iterativamente la lista probablemente debería funcionar bien, aunque no es la manera más eficiente o (subjetivamente) elegante de hacerlo.

Si hay más de una lista, la salida correcta dependerá de la especificación. ¿Debería devolver todas, o solo la primera, o lanzar un error?

Si yo fuera usted, buscaría una función recursiva para resolver el problema. Cada nivel de recursión básicamente procesará los elementos de un nivel dado de las listas anidadas. Piense en lo que debería hacer cada llamada recursiva: ¡es muy simple si hace clic!

Answer 3

Aquí está mi solución, usando un enfoque similar al de OP. (En el caso de varios elementos más profundos, todos son devueltos.)

Lo escribí en Scheme, que probablemente no se pueda traducir inmediatamente a Common Lisp, por lo que no creo que sea un completo regalar. Aún así, tiene el potencial de ser spoiler, así que pise con precaución.

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