Filtering for the same index on all nodes of a binary tree in Scheme?

2
votes

This started as a misinterpretation of exercise 2.29 in SICP and became a personal curiosity. It seems simple enough I feel embarrassed I'm having such trouble finding a solution that works for all cases. Obviously I know how to count the nodes on a tree and how to enumerate the values in every node into one list, but neither algorithm is helping me filter for the same index in every node.

Given any binary tree represented as a nested list where each node holds either one or two integers, there should be one function that returns a list of the first value in every node and one that returns the second value in every node (keeping in mind not all nodes will have a second value).

Here's what I have so far with a simple test case:

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

And the result:

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

As you can see, the first function won't filter values in sublists and the second leaves extraneous sublists I would need to filter out with an enumerate function. I really tried every variation of car and cdr I could think of and this was the closest I came. It clearly shows I still don't fully understand working with list structure even though it hasn't been an issue with simpler examples.

(For reference I'm using R5RS)

2
treeschemelispbinary-treesicp

2 Answers

2
votes

After a bit of fiddling, I ended up with this. Hope it helps!

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

Using your test data:

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

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

Here's a different solution approach: we tag every returned leaf value with its position in its parent, then filter by the tag:

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

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

Now, the filter-tag and collect-leaf-values functions:

(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 already defines everything necessary at this point. But since you say you're just using plain Scheme, let's define filter and append-map (note that append-map uses any which SRFI 1 also provides—we'll define a simplified version here too):

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