Фильтрация для одного и того же индекса на всех узлах двоичного дерева в схеме?

Question

Это началось как неправильное толкование упражнения 2.29 в SICP и стало личным любопытством. Кажется достаточно простым, я чувствую себя смущенным. У меня возникают проблемы с поиском решения, которое работает для всех случаев. Очевидно, я знаю, как подсчитывать узлы на дереве и как перечислять значения в каждом узле в один список, но ни один из алгоритмов не помогает мне фильтровать один и тот же индекс в каждом узле.

Дано любое двоичное дерево, представленное как вложенный список, где каждый узел содержит одно или два целых числа, должна быть одна функция, которая возвращает список первого значения в каждом узле и тот, который возвращает второе значение в каждом узле (имея в виду, что не все узлы будут иметь второе значение).

Вот что я до сих пор с помощью простого теста:

(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, о которых я мог думать, и это было самое близкое, что я пришел. Это ясно показывает, что я до сих пор не полностью понимаю работу со структурой списка, хотя это не было проблемой с более простыми примерами.

(Для справки я использую R5RS)

Answer 1

После немного возился, я закончил с этим. Надеюсь, поможет!

(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 также обеспечивает-we'll определить упрощенную версию здесь):

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