"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

Categories:

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:

Related Posts: