Znajdź najbardziej zagnieżdżoną listę na liście w Common Lisp

Question

Jestem nowy w Common Lisp i programowania funkcjonalnego, ale mam duże doświadczenie w językach takich jak C, C++, C#, Java i tak dalej. Mam problem ze znalezieniem najbardziej zagnieżdżonej listy na liście. Mój wkład jest mniej więcej tak:

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

Chciałbym uzyskać listę najbardziej zagnieżdżony wewnątrz tej liście, która w tym przypadku jest

(7) 

miałem pojęcia, że ​​mogę wyprostować listę jakoś , dopóki nie pozostała tylko jedna podlista. Aby zilustrować, co mam na myśli, tutaj jest kilka kroków:

Krok 1. - wejście:

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

Krok 2. - spłaszczyć na "pierwszego poziomu":

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

kroku 3. - spłaszczyć na „drugiego poziomu”:

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

teraz istnieje tylko jedna lista zagnieżdżona w lewo, co oznacza, że ​​była lista najbardziej zagnieżdżonych. Ale widzę tu problem, gdy wystąpią dwie lub więcej takich list. Proszę podziel się swoimi przemyśleniami na ten temat.

Mam problemy z wprowadzeniem tej procedury w życie w Common Lisp, więc byłbym wdzięczny za kilka wskazówek we właściwym kierunku, może jakiś przykładowy kod i tak dalej. Jest to zadanie domowe, więc nie oczekuję pełnego rozwiązania, ale byłbym zadowolony, gdyby ktoś wskazał być może łatwiejsze i lepsze rozwiązanie oraz jego wdrożenie.

Answer 1

Oto moje (nie bardzo czysty) rozwiązanie w 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:

Po drugim myśli, że jest to nieco czystsze rozwiązanie:

(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

Twoje podejście polegające na iteracyjnym spłaszczeniu listy powinno prawdopodobnie działać dobrze, chociaż nie jest to najskuteczniejszy lub (subiektywnie) elegancki sposób na to.

Jeśli istnieje więcej niż jedna taka lista, poprawne wyniki zależą od specyfikacji - czy należy zwrócić wszystkie z nich, czy tylko pierwsze, lub podać błąd?

Gdybym był tobą, chciałbym przyjrzeć się funkcji rekursywnej, aby rozwiązać problem. Każdy poziom rekursji zasadniczo przetwarzałby elementy danego poziomu zagnieżdżonych list. Pomyśl o tym, co każde wywołanie rekurencyjne powinno zrobić - to bardzo proste, jeśli raz kliknie!

Answer 3

Oto moje rozwiązanie, używając podobnego podejścia do PO. (W przypadku wielu najgłębszych pozycji wszystkie są zwracane).

Napisałem to na Scheme, co prawdopodobnie nie będzie możliwe do natychmiastowego przetłumaczenia na Common Lisp, więc nie uważam, że byłoby to kompletne gratisów. Mimo to ma potencjał, by być zepsutym, więc zachowaj ostrożność.

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