Finden Sie die meisten geschachtelten Liste in einer Liste in Common Lisp

Question

Ich bin neu in Common Lisp und funktionale Programmierung, aber ich habe eine Menge Erfahrung in Sprachen wie C, C++, C#, Java und so weiter. Ich habe Probleme, die verschachtelte Liste in einer Liste zu finden. Mein Eingang ist so etwas wie diese:

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

Ich mag die meisten verschachtelte Liste innerhalb dieser Liste erhalten, die in diesem Fall ist

(7) 

Ich habe hatte eine Idee, die ich irgendwie die Liste abflachen könnte , bis nur noch eine Unterliste übrig war. Um zu zeigen, was ich meine, hier ist ein paar Schritte:

Schritt 1 - Eingang:

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

Schritt 2. - flach auf "first level":

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

Schritt 3. - flach auf „zweiten Ebene“:

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

Jetzt ist es nur eine verschachtelte Liste links, was bedeutet, dass die verschachtelte Liste war. Aber ich sehe hier ein Problem, wenn zwei oder mehr solcher Listen auftreten würden. Bitte teile deine Gedanken dazu.

Ich habe Probleme, dieses Verfahren in Common Lisp in die Realität umzusetzen, also wäre ich dankbar für einige Hinweise in die richtige Richtung, vielleicht ein Beispielcode und so weiter. Dies ist eine Hausaufgabe, daher erwarte ich nicht wirklich eine vollständige Lösung, würde mich aber freuen, wenn jemand auf eine einfachere und bessere Lösung und deren Umsetzung hinweist.

Answer 1

Hier ist meine (nicht sehr sauber) Lösung 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:

Nach einem zweiten Gedanken, das ist eine etwas sauberere Lösung:

(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

Ihr Ansatz der iterativen Verflachung der Liste sollte wahrscheinlich gut funktionieren, obwohl es nicht die effizienteste oder (subjektiv) elegante Art ist, dies zu tun.

Wenn es mehr als eine solche Liste gibt, würde die korrekte Ausgabe von der Spezifikation abhängen - sollten Sie alle oder nur die erste zurückgeben oder einen Fehler ausgeben?

Wenn ich Sie wäre, würde ich nach einer rekursiven Funktion suchen, um das Problem zu lösen. Jede Rekursionsebene würde grundsätzlich die Elemente einer gegebenen Ebene der verschachtelten Listen verarbeiten. Denken Sie daran, was jeder rekursive Aufruf tun sollte - es ist sehr einfach, wenn es einmal klickt!

Answer 3

Hier ist meine Lösung, mit einem ähnlichen Ansatz zu den OPs. (Im Falle mehrerer tiefster Objekte werden sie alle zurückgegeben.)

Ich habe es in Scheme geschrieben, das wahrscheinlich nicht sofort in Common Lisp übersetzbar sein wird, so dass ich nicht das Gefühl habe, dass es komplett wäre hergeben. Dennoch, es hat das Potenzial zu spoilery, also schreite mit Vorsicht.

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