Scheme에서 이진 트리의 모든 노드에 대해 동일한 인덱스를 필터링합니까?

Question

이것은 SICP에서 운동 2.29의 오해로 시작되어 개인 호기심이되었습니다. 그것은 간단합니다. 나는 모든 경우에 사용할 수있는 솔루션을 찾는 데 어려움을 겪고 있습니다. 분명히 나는 ​​트리에서 노드를 계산하는 방법과 모든 노드의 값을 하나의 목록으로 열거하는 방법을 알고 있지만 어느 알고리즘도 모든 노드의 동일한 인덱스에 대해 필터링하는 것을 도와주지 못합니다.

각 노드가 하나 또는 두 개의 정수를 포함하는 중첩 목록으로 표시되는 모든 이진 트리가 주어진 경우 모든 노드에서 첫 번째 값 목록을 반환하는 함수와 모든 노드에서 두 번째 값을 반환하는 함수가 있어야합니다 (모든 노드가 두 번째 값을 갖는 것은 아닙니다).

(define (first-values tree) 
    (cond ((null? tree) '()) 
     ((not (pair? tree)) (list tree)) 
     (else (cons (car (first-values (car tree))) 
        (first-values (car (cdr tree))))))) 

(define (second-values tree) 
    (cond ((null? tree) '()) 
     ((not (pair? tree)) (list tree)) 
     (else (cons (cdr (second-values (car tree))) 
        (second-values (car (cdr tree))))))) 

(define (make-tree left right) 
    (list left right)) 

(define test (make-tree 
       (make-tree 2 5) 
       (make-tree (make-tree 4 10) (make-tree 6 20)))) 

test 
(first-values test) 
(second-values test) 

그리고 결과 : 당신이 볼 수 있듯이

((2 5) ((4 10) (6 20))) 
(2 4 6 20) 
((5) (10)() 20) 

, 첫 번째 함수는 하위 목록에서 값을 필터링하지 않습니다 여기에

내가 간단한 테스트 케이스가 지금까지 가지고 무엇을 두 번째는 불필요한 하위 목록을 남겨 두었습니다. 열거 형 함수로 필터링해야합니다. 나는 정말로 내가 생각할 수 있었던 차와 cdr의 모든 변화를 시험해 보았다. 그리고 이것은 내가 간 가장 가까운 것이었다. 명확한 예제를 통해 문제가되지는 않았지만 목록 구조로 작업하는 것을 완전히 이해하지 못한다는 것을 분명히 알 수 있습니다.

은 바이올린을 켜는 조금 후

Answer 1

을 (참고로 나는 R5RS 사용하고 있습니다), 나는이 함께했다. 희망이 도움이됩니다! 테스트 데이터 사용

(define (first-values tree) 
    (cond ((null? tree) '()) 
     ((not (pair? (car tree))) (list (car tree))) 
     (else (append (first-values (car tree)) 
         (first-values (cdr tree)))))) 

(define (second-values tree) 
    (cond ((null? tree) '()) 
     ((not (pair? (car tree))) (cdr tree)) 
     (else (append (second-values (car tree)) 
         (second-values (cdr tree)))))) 

: 여기

(first-values test) 
=> '(2 4 6) 

(second-values test) 
=> '(5 10 20) 

Answer 2

다른 솔루션 접근 방식 : 우리는 다음 부모에서의 위치와 모든 반환 잎 값에 태그를 태그에 의해 필터링 :

(define (first-values tree) 
    (filter-tag 0 (collect-leaf-values 0 tree))) 

(define (second-values tree) 
    (filter-tag 1 (collect-leaf-values 0 tree))) 

이제 filter-tag 및 collect-leaf-values의 기능은 다음과 같습니다.

(define (filter-tag tag tagged-list) 
    (map cdr (filter (lambda (x) (= (car x) tag)) tagged-list))) 

(define (leaf? x) 
    (not (pair? x))) 

(define (collect-leaf-values index tree) 
    (if (leaf? tree) 
     (list (cons index tree)) 
     (append-map collect-leaf-values '(0 1) tree))) 

SRFI 1은이 시점에서 필요한 모든 것을 이미 정의합니다. 당신은 그냥 평범한 방식을 사용한다고 가정하지만 이후,의는 filter 및 append-map가 정의 할 수 있습니다 (append-map 사용주의 any하는 SRFI 1도 제공-트로닉도 여기에 단순화 된 버전을 정의) :

(define (filter pred lst) 
    (cond ((null? lst) '()) 
     ((pred (car lst)) (cons (car lst) (filter pred (cdr lst)))) 
     (else (filter pred (cdr lst))))) 

(define (any pred lst) 
    (cond ((null? lst) #f) 
     ((pred (car lst)) => values) 
     (else (any pred (cdr lst))))) 

(define (append-map func . lists) 
    (let recur ((lists lists)) 
    (if (any null? lists) 
     '() 
     (append (apply func (map car lists)) (recur (map cdr lists))))))