SICP Exercise 2.35: Counting leaves of a tree

"Life is all about sharing. If we are good at something, pass it on." - Mary Berry

SICP Exercise 2.35: Counting leaves of a tree

2021-10-14

Exercise 2.35: Redefine count-leaves from section 2.2.2 as an accumulation:
1(define (count-leaves t)
2    (accumulate <??> <??> (map <??> <??>)))

The count-leaves procedure from section 2.2.2:

1(define (count-leaves x)
2    (cond ((null? x) 0)
3          ((not (pair? x)) 1)
4          (else (+ (count-leaves (car x))
5                   (count-leaves (cdr x))))))

The accumulate procedure from section 2.2.3:

1(define (accumulate op initial sequence)
2    (if (null? sequence)
3        initial
4        (op (car sequence)
5            (accumulate op initial (cdr sequence)))))

The first thing comes to my mind is: to count leaves of a tree, we need to flatten out that tree. Recall the fringe produce from exercise 2.28:

1(define (fringe x)
2    (cond ((null? x) null)
3        ((pair? (car x))
4            (append (fringe (car x)) (fringe (cdr x))))
5        (else
6            (cons (car x) (fringe (cdr x))))))

Let’s see what is the output if we apply fringe function to each element of the input list:

1(define t (cons (list 1 2) (list 3 4)))
2(map fringe t)

 1$ racket 2.35-count-leaves-accumulation.rkt
 2>(fringe '(1 2))
 3> (fringe 1)
 4< '(1)
 5> (fringe '(2))
 6> >(fringe 2)
 7< <'(2)
 8> >(fringe '())
 9< <'()
10< '(2)
11<'(1 2)
12>(fringe 3)
13<'(3)
14>(fringe 4)
15<'(4)
16'((1 2) (3) (4))

Now we can just compute the length of each element:

1(define (count-leaves t)
2    (accumulate (lambda (x y)
3                    (+ (length x) y))
4                0
5                (map fringe t)))
6
7(define t (cons (list 1 2) (list 3 4)))
8(map fringe t)
9(count-leaves t)

Test:

 1$ racket 2.35-count-leaves-accumulation.rkt
 2'((1 2) (3) (4))
 3>(accumulate #<procedure:...es-accumulation.rkt:15:16> 0 '((1 2) (3) (4)))
 4> (accumulate #<procedure:...es-accumulation.rkt:15:16> 0 '((3) (4)))
 5> >(accumulate #<procedure:...es-accumulation.rkt:15:16> 0 '((4)))
 6> > (accumulate #<procedure:...es-accumulation.rkt:15:16> 0 '())
 7< < 0
 8< <1
 9< 2
10<4
114

After coming up with this solution, I looked around to see if there is a better way. So, instead of applying fringe to each element of the input list (map fringe t), what function can be used to apply to the entire list?

1(map <??> (fringe t))

Let’s print the output of fringe t:

1(define t (cons (list 1 2) (list 3 4)))
2(fringe t)

 1$ racket 2.35-count-leaves-accumulation.rkt
 2>(fringe '((1 2) 3 4))
 3> (fringe '(1 2))
 4> >(fringe 1)
 5< <'(1)
 6> >(fringe '(2))
 7> > (fringe 2)
 8< < '(2)
 9> > (fringe '())
10< < '()
11< <'(2)
12< '(1 2)
13> (fringe '(3 4))
14> >(fringe 3)
15< <'(3)
16> >(fringe '(4))
17> > (fringe 4)
18< < '(4)
19> > (fringe '())
20< < '()
21< <'(4)
22< '(3 4)
23<'(1 2 3 4)
24'(1 2 3 4)

This is a flattened list. To count leaves, we can just simply return 1 for each element:

1(define (count-leaves t)
2    (accumulate +
3                0
4                (map (lambda (x) 1) (fringe t))))

Test:

 1$ racket 2.35-count-leaves-accumulation.rkt
 2'(1 2 3 4)
 3>(accumulate #<procedure:+> 0 '(1 1 1 1))
 4> (accumulate #<procedure:+> 0 '(1 1 1))
 5> >(accumulate #<procedure:+> 0 '(1 1))
 6> > (accumulate #<procedure:+> 0 '(1))
 7> > >(accumulate #<procedure:+> 0 '())
 8< < <0
 9< < 1
10< <2
11< 3
12<4
134

Tags: sicp scheme

Edit on GitHub