Exercise 2.35. Redefine count-leaves from section 2.2.2 as an accumulation:
(define (count-leaves t)
(accumulate <??> <??> (map <??> <??>)))
题目中所给的 count-leaves 将使用 map 对树的每一个分支进行某种操作,然后 accumulate 最后的结果。这里很容易就想到是否可以直接填写
(define (count-leaves t)
(accumulate + 0 (map count-leaves t)))
当然,运行之后会有类似于下面的
(count-leaves/accumulate '((1 2) 3 (3 4 5 (6))))
;The object 1, passed as an argument to map, is not a list.
看到这里就知道如何对 map 中的过程进行修改了。之前的错误在于完全依赖于 count-leaves 去求解树的每个部分。现在我们将对数的每个部分进行判断–是否是叶子,然后使用 accumulate 对结果进行处理。
;;; count-leaves in section 2.2.2
(load "33-accumulate.scm")
(define (count-leaves/accumulate t)
(accumulate + 0 (map (lambda (sub)
(if (pair? sub)
(count-leaves/accumulate sub)
1))
t)))
另外还有一些其他的处理方法。我们可以不使用这样的递归,首先就把树中所有叶子节点全部收集起来,然后使用 accumulate 来模仿 length(当然我们也可以使用 length 过程)去数数收集起来的叶子节点到底有多少个。下面是这个过程以及整个程序的测试。
(define (count-leaves/correct x)
(cond ((null? x) 0)
((not (pair? x)) 1)
(else (+ (count-leaves/correct (car x))
(count-leaves/correct (cdr x))))))
(define (enumerate-tree tree)
(cond ((null? tree) '())
((not (pair? tree)) (list tree))
(else (append (enumerate-tree (car tree))
(enumerate-tree (cdr tree))))))
(define (count-leaves/flat t) ; sort of the same with the length procedure
(accumulate (lambda (this-node next)
(1+ next))
0
(enumerate-tree t)))
;;; tests begin
(load "../testframe.scm")
(let ((l0 '())
(l1 '(1))
(l2 '(1 3))
(l3 '(1 (2 (3 (4)))))
(l4 '((((4) 3) 2) 1)))
(assert= (count-leaves/correct l0) (count-leaves/accumulate l0))
(assert= (count-leaves/correct l0) (count-leaves/flat l0))
(assert= (count-leaves/correct l1) (count-leaves/accumulate l1))
(assert= (count-leaves/correct l1) (count-leaves/flat l1))
(assert= (count-leaves/correct l2) (count-leaves/accumulate l2))
(assert= (count-leaves/correct l2) (count-leaves/flat l2))
(assert= (count-leaves/correct l3) (count-leaves/accumulate l3))
(assert= (count-leaves/correct l3) (count-leaves/flat l3))
(assert= (count-leaves/correct l4) (count-leaves/accumulate l4))
(assert= (count-leaves/correct l4) (count-leaves/flat l4)))