Redefine
count-leaves
from section 2.2.2 as an
accumulation:
(define (count-leaves t) (accumulate <??> <??> (map <??> <??>)))In the "Sequence operations" section the authors define the procedure
enumerate-tree
which flattens a tree into a list that contains only the leaf nodes of the tree. We can use this to simplify our job here - we're only interested in the leaf nodes and this saves us the complexity of writing our own tree-traversal. The length of this list is equal to the number of leaf nodes in the tree...However, the procedure template we're given above doesn't allow us to do that - we have to
map
across a list and then accumulate
in some way across the result of the mapped list. So what mapping should we use, and what accumulation?Well, when we defined
length
in terms of accumulate
in exercise 2.33, we started with an initial value of 0 and incremented this by 1 for each element in the tree. We could achieve the same effect by using +
as our op
for accumulate
, 0 as the initial
value, and pass it a sequence
that's a list with the same number of elements as there are leaf nodes, but with each element having the value 1... And we can produce such a sequence by mapping each element from the list returned by enumerate-tree
to 1.Here's my implementation:
(define (count-leaves t) (accumulate + 0 (map (lambda (x) 1) (enumerate-tree t))))...and in practice:
> (define x (cons (list 1 2) (list 3 4))) > (define y (list 1 (list 2 3) (cons (list 4 5) (list 6 7)))) > (count-leaves x) 4 > (count-leaves (cons x x)) 8 > (count-leaves y) 7 > (count-leaves (list x y)) 11
I don't think the "workarounds" (length (fringe t)) or (length (enumerate-tree t)) are appropriate for this exercise. The point of the exercise is to not use that and use solely the accumulate template. Like this:
ReplyDelete(define (count-leaves t) (accumulate + 0 (map (lambda (x) (if (not (pair? x)) 1 (count-leaves x))) t)))
I disagree. One of the key techniques in developing software is abstraction. I'm using an existing abstraction to remove complexity and simplify readability.
Delete