Common Lisp의 목록에서 가장 중첩 된 목록 찾기

Question

Common Lisp 및 함수 프로그래밍을 처음 접했지만 C, C++, C#, Java 등의 언어로 많은 경험이 있습니다. 목록에서 가장 중첩 된 목록을 찾는 데 문제가 있습니다.

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

내가이 경우에 내가 어떻게 든 목록을 평평 수있는 생각을했다

(7) 

입니다이 목록 내에서 가장 하위 목록을 좀하고 싶습니다 : 내 입력이 같은 것입니다 , 하나의 하위 목록 만 남을 때까지. 무슨 뜻인지 설명하기 위해, 여기에 몇 가지 단계 :

1 단계 - 입력 :

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

2 단계 - "첫 번째 수준"에 평평 :

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

3 단계. - "두 번째 수준"에 평탄화 됨 :

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

이제 가장 중첩 된 목록 인 중첩 목록이 하나만 남았습니다. 그러나 두 개 이상의 목록이 나타날 때 문제가 발생합니다. 이 점에 대해 의견을 나누십시오.

나는이 절차를 Common Lisp에서 현실적으로 다루는 데 어려움을 겪고있다. 그래서 나는 올바른 방향으로 어떤 포인터에 대해 감사하고, 몇 가지 예제 코드 등을 고맙게 생각한다. 이것은 숙제 임으로 풀 솔루션을 기대하지는 않지만 누군가가 아마도 더 쉽고 우수한 솔루션과 그 구현을 지적한다면 기쁜 일입니다.

Answer 1

는 CL 내 (매우 깨끗하지 않음) 솔루션입니다

(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

목록을 반복적으로 병합하는 방법은 가장 효과적이거나 (주관적으로) 우아한 방법은 아니지만 잘 작동해야합니다.

이러한 목록이 두 개 이상있는 경우 올바른 출력은 사양에 따라 달라집니다. 모든 내용을 반환하거나 첫 번째 내용 만 반환하거나 오류가 발생해야합니까?

내가 너라면, 문제를 해결하기 위해 반복적 인 함수를 생각해 볼 것입니다. 재귀의 각 레벨은 기본적으로 중첩 목록의 주어진 레벨의 요소를 처리합니다. 각각의 재귀 호출이해야 할 일을 생각해보십시오. 한번 클릭하면 매우 간단합니다!

Answer 3

다음은 내 솔루션입니다. OP와 비슷한 방식을 사용합니다. (가장 깊은 항목이 여러 개인 경우 모두 반환됩니다.)

제가 Common Lisp로 즉시 변환 할 수없는 Scheme에서 작성 했으므로 완전한 것으로 느껴지지 않습니다. 공짜. 그래도 여전히 위험 할 수 있으므로 조심스럽게 밟습니다.

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

편집 : 여기

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