Tags SICP

Tree-recursion, yay !

#### Exercise 2.24

The interpretation is `(1 (2 (3 4)))`. I’ll skip the drawings because they’re too time consuming for such a simple exercise.

#### Exercise 2.25

```[22]> (setf lst '(1 3 (5 7) 9))
(1 3 (5 7) 9)
[23]> (car (cdr (car (cdr (cdr lst)))))
7

[24]> (setf lst '((7)))
((7))
[25]> (car (car lst))
7

[37]> (setf lst '(1 (2 (3 (4 (5 (6 7)))))))
(1 (2 (3 (4 (5 (6 7))))))
7
```

The last one is tricky, because `cdr` returns a list, so I use `cadr` (`car` of `cdr`) instead to get inside the lists.

#### Exercise 2.26

```[39]> (setf x '(1 2 3))
(1 2 3)
[40]> (setf y '(4 5 6))
(4 5 6)
[41]> (append x y)
(1 2 3 4 5 6)
[42]> (cons x y)
((1 2 3) 4 5 6)
[43]> (list x y)
((1 2 3) (4 5 6))
```

#### Exercise 2.27

Similarly to `count-leaves`, we must differentiate between three cases:

1. nil 2. pair 3. not pair (atom)

The CL function for checking if something is a pair is `consp`[1]:

```(defun deep-reverse (lst)
(cond ((null lst) nil)
((consp (car lst))
(append
(deep-reverse (cdr lst))
(list (deep-reverse (car lst))))) ; [A]
(t
(append
(deep-reverse (cdr lst))
(list (car lst))))))
```

Take a look at the line marked with [A]. The call to `list` is very important here, because otherwise `append` just stitches the contents of the list `deep-reverse` returns. `list` makes it append them as a single list, which is what we need.

#### Exercise 2.28

```(defun fringe (lst)
(cond ((null lst) nil)
((not (consp lst)) (list lst))
(t
(append
(fringe (car lst))
(fringe (cdr lst))))))
```

#### Exercise 2.29

a.

```(defun make-mobile (left right)
(list left right))

(defun left-branch (mobile)
(first mobile))

(defun right-branch (mobile)
(second mobile))

(defun make-branch (len structure)
(list len structure))

(defun branch-len (branch)
(first branch))

(defun branch-structure (branch)
(second branch))
```

I’m using CL’s convenience accessors for lists. `first` is equivalend to `car`, `second` to `cadr` (the `car` of the `cdr`). CL supports such accessors up to `tenth`, together with the generic accessor `nth`.

b.

I’m adding another abstraction – the predicate `structure-is-weight?`.

```(defun structure-is-weight? (structure)
(atom structure))

(defun weight-of-branch (branch)
(let ((struct (branch-structure branch)))
(if (structure-is-weight? struct)
struct
(weight-of-mobile struct))))

(defun weight-of-mobile (mobile)
(+  (weight-of-branch (left-branch mobile))
(weight-of-branch (right-branch mobile))))
```

Note how `weight-of-mobile` and `weight-of-branch` are defined. These are mutually recursive functions. Defining them this way makes for a very natural code, IMO.

c.

I’m going to use the same technique (mutually recursive functions) to figure out whether a given mobile is balanced:

```(defun torque-of-branch (branch)
(*  (branch-len branch)
(weight-of-branch branch)))

(defun branch-balanced? (branch)
"A branch is balanced either when it has a structure
that's a simple weight, or when the structure is
a balanced mobile"
(let ((struct (branch-structure branch)))
(or
(structure-is-weight? struct)
(mobile-balanced? struct))))

(defun mobile-balanced? (mobile)
(let ((lb (left-branch mobile))
(rb (right-branch mobile)))
(and
(=
(torque-of-branch lb)
(torque-of-branch rb))
(branch-balanced? lb)
(branch-balanced? rb))))
```

Note the documentation string added to `branch-balanced?`. It is a standartized feature of Common Lisp, allowing me to find out what a function does from the REPL:

```[5]> (documentation  'branch-balanced? 'function)
"A branch is balanced either when it has a structure
that's a simple weight, or when the structure is
a balanced mobile"
[6]>
```

d.

I only need to change the accessors `left-branch, right-branch, branch-len, branch-structure` and the predicate `structure-is-weight?`. The rest of the code builds on top of the abstraction created by these functions and doesn’t need to be changed.

#### Exercise 2.30

```(defun square-tree-direct (tree)
(cond ((null tree) nil)
((not (consp tree)) (square tree))
(t
(cons (square-tree-direct (car tree))
(square-tree-direct (cdr tree))))))

(defun square-tree-map (tree)
(mapcar
(lambda (subtree)
(if (consp subtree)
(square-tree-map subtree)
(square subtree)))
tree))
```

#### Exercise 2.31

```(defun tree-map (func tree)
(mapcar
(lambda (subtree)
(if (consp subtree)
(tree-map func subtree)
(funcall func subtree)))
tree))
```

#### Exercise 2.32

In set theory, the set of all subsets of some set S is called the powerset of S. So I’m naming the function accordingly. This is a piece of completely futile mathematical pedantry :-)

```(defun powerset (s)
(if (null s)
(list nil)
(let ((rest (powerset (cdr s))))
(append
rest
(mapcar (lambda (r)
(cons (car s) r))
rest)))))
```

To understand why this works, let’s do the most natural thing and “walk over” the code mentally. So, the powerset of S is `nil` if S itself is `nil`. This is trivial. But what happens when S is a list ?

Well, it is somewhat similar to change counting from the previous sections. We “pick up” the first element of the list and concatenate two sets:

1. The powerset of all the elements without the first. 2. The powerset of all the elements without the first, with the first element prepended to each subset.

Consider the set `(1)`. Its powerset is `(nil (1))`. Now, consider the larger set `(2 1)`. According to the procedure above, its powerset is the concatenation of:

1. The powerset of all the elements without 2, that is `(1)`. Which we already saw is `(nil (1))`. 2. The element 2 prepended to each subset of the powerset of `(1)`, that is, 2 prepended to `nil` and 2 prepended to `(1)`, in total: `((2) (2 1))`

Concatenating the above two gives: `(nil (1) (2) (1 2))`, which is indeed the powerset of `(2 1)`. Using the same reasoning, we can compute the powerset of `(3 2 1)`. I hope it is clear by now why the procedure is correct.

1 The convention of CL is to use the ending `p` for predicates, although it’s not too consistent – consider the predicates `null` and `atom`, for example. Personally I prefer Scheme’s idiom of ending a predicate with a question sign.