SICP 全笔记

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