# Chapter 1. Inductive Sets of Data¶

## Exercise 1.1¶

1. $$\{3n + 2 \mid n \in N\}$$

Top-down:

A natural number $$n$$ is in $$S$$ if and only if

1. $$n = 2$$, or
2. $$n - 3 \in S$$.
Bottom-up:

Define the set $$S$$ to be the smallest set contained in $$N$$ and satisfying the following two properties:

1. $$2 \in S$$
2. if $$n \in S$$, then $$n + 3 \in S$$
Rules of inference:
$2 \in S$
$\frac { n \in S } { n + 3 \in S }$
2. $$\{2n + 3m + 1 \mid n, m \in N\}$$

Top-down:

A natural number $$n$$ is in $$S$$ if and only if

1. $$n = 1$$, or
2. $$n - 2 \in S$$, or
3. $$n - 3 \in S$$
Bottom-up:

Define the set $$S$$ to be the smallest set contained in $$N$$ and satisfying the following two properties:

1. $$1 \in S$$
2. if $$n \in S$$, then $$n + 2 \in S$$ and $$n + 3 \in S$$
Rules of inference:
$1 \in S$
$\frac { n \in S } { n + 2 \in S, n + 3 \in S }$
3. $$\{(n, 2n + 1) \mid n \in N\}$$

Top-down:

A pair of natural numbers $$(n, m)$$ is in $$S$$ if and only if

1. $$n = 0$$ and $$m = 1$$, or
2. $$(n - 1, m - 2) \in S$$
Bottom-up:

Define the set $$S$$ to be the smallest set contained in $$\{n, m \mid n \in N, m \in N\}$$ and satisfying the following two properties:

1. $$(0, 1) \in S$$
2. if $$(n, m) \in S$$, then $$(n + 1, m + 2) \in S$$
Rules of inference:
$(0, 1) \in S$
$\frac { (n, m) \in S } { (n + 1, m + 2) \in S }$
4. $$\{(n, n^2 \mid n \in N)\}$$

Top-down:

A pair of natural numbers $$(n, m)$$ is in $$S$$ if and only if

1. $$n = 0$$, and $$m = 0$$, or
2. $$(n - 1, m - 2n + 1) \in S$$
Bottom-up:

Define the set $$S$$ to be the smallest set contained in $$\{n, m \mid n \in N, m \in N\}$$ and satisfying the following two properties:

1. $$(0, 0) \in S$$
2. if $$(n, m) \in S$$, then $$(n + 1, m + 2n + 1) \in S$$
Rules of inference:
$(0, 0) \in S$
$\frac { (n, m) \in S } { (n + 1, m + 2n + 1) \in S }$

## Exercise 1.2¶

1. $$(0, 1) \in S \quad \displaystyle \frac{(n, k) \in S}{(n + 1, k + 7) \in S}$$

$\{(n, 7n + 1) \mid n \in N\}$
2. $$(0, 1) \in S \quad \displaystyle \frac{(n, k) \in S}{(n + 1, 2k) \in S}$$

$\{(n, 2^n) \mid n \in N\}$
3. $$(0, 0, 1) \in S \quad \displaystyle \frac{(n, i, j) \in S}{(n + 1, j, i + j) \in S}$$

$\{(n, F(n), F(n + 1)) \mid n \in N\}$

where $$F(n)$$ is defined as

$\begin{split}F(n) = \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ F(n - 1) + F(n - 2) & n > 1 \end{cases}\end{split}$
4. $$(0, 1, 0) \in S \quad \displaystyle \frac{(n, i, j) \in S}{(n + 1, i + 2, i + j) \in S}$$

$\{(n, 2n + 1, n^2 \mid n \in N\}$
Proof:

Let $$(n_k, i_k, j_k)$$ be the $$k$$-th element of $$S$$ generated by the rules of inference. Then we have:

$\begin{split}n_0 &= 0 \\ n_k &= n_{k-1} + 1 = n_{k-1} + 1 \times 1 \\ &= n_{k-2} + 1 + 1 = n_{k-2} + 2 \times 1 \\ &= n_{k-k} + 1 + \dots + 1 = n_{k-k} + k \times 1 \\ &= n_0 + k \times 1 \\ &= k\end{split}$

and

$\begin{split}i_0 &= 1 \\ i_k &= i_{k-1} + 2 = i_{k-1} + 1 \times 2 \\ &= i_{k-2} + 2 + 2 = i_{k-1} + 2 \times 2 \\ &= i_{k-k} + 2 + \dots + 2 = i_{k-k} + k \times 2 \\ &= i_0 + 2k \\ &= 2k + 1\end{split}$

and

$\begin{split}j_0 &= 0 \\ j_k &= i_{k-1} + j_{k-1} \\ &= 2(k - 1) + 1 + j_{k-1} \\ &= 2(k - 1) + 1 + i_{k-2} + j_{k-2} \\ &= 2(k - 1) + 1 + 2(k - 2) + 1 + j_{k-2} \\ &= 2(k - 1) + 1 + 2(k - 2) + 1 + \dots + 2(k - k) + 1 + j_{k-k} \\ &= \left ( \sum_{x=1}^k 2(k - x) + 1 \right ) + j_0 \\ &= 2 \left ( k^2 - \frac{(1 + k)k}{2} \right ) + k \\ &= 2k^2 - (1 + k)k + k \\ &= 2k^2 - k - k^2 + k \\ &= k^2\end{split}$

Thus we have

$S = \{ (n, 2n + 1, n^2) \mid n \in N \}$

Q.E.D.

## Exercise 1.3¶

$0 \in T$
$1 \in T$
$\frac { n \in T } { n + 3 \in T }$

## Exercise 1.4¶

    List-of-Int
=>  (Int . List-of-Int)
=>  (-7 . List-of-Int)
=>  (-7 . (Int . List-of-Int))
=>  (-7 . (3 . List-of-Int))
=>  (-7 . (3 . (Int . List-of-Int)))
=>  (-7 . (3 . (14 . List-of-Int)))
=>  (-7 . (3 . (14 . ())))


## Exercise 1.5¶

Proof:

This proof is by induction on the depth of $$e$$. The depth of $$e$$, $$d(e)$$, is defined as follows:

1. If $$e$$ is $$Identifier$$, $$d(e) = 1$$
2. If $$e$$ is $$\texttt{(lambda (}Identifier\texttt{) }e_1\texttt{)}$$, $$d(e) = d(e_1) + 1$$
3. If $$e$$ is $$\texttt{(}e_1, e_2\texttt{)}$$, $$d(e) = \textrm{max}(d(e_1, e_2)$$

The induction hypothesis, $$IH(k)$$, is that for any $$e \in LcExp$$ of depth $$\leq k$$ has the same number of left and right parentheses.

1. There are no such $$e$$ that $$d(e) = 0$$, so $$IH(0)$$ holds trivially.
2. Let $$k$$ be an integer such that $$IH(k)$$ holds.
• If $$e$$ is $$Identifier$$, we have $$k = 1$$, and there are no parentheses. So $$IH(1)$$ holds.
• If $$e$$ is $$\texttt{(lambda (}Identifier\texttt{) }e_1\texttt{)}$$, we have $$k = d(e_1) + 1$$. Since $$d(e_1) < k$$, $$IH(d(e_1))$$ holds, i.e., $$e_1$$ have the same number of left and right parentheses. Since $$e$$ adds exactly two left parentheses and two right parentheses, $$IH(k)$$ holds.
• If $$e$$ is $$\texttt{(}e_1, e_2\texttt{)}$$, $$d(e) = \textrm{max}(d(e_1, e_2)$$, we have $$k = \textrm{max}(e_1, e_2)$$. Since $$d(e_1) < k$$, $$IH(d(e_1)$$ holds. Similarly, $$IH(d(e_2))$$ holds. Since $$e$$ adds one left parenthesis and one right parenthesis to $$e_1 e_2$$, $$IH(k)$$ holds

Q.E.D.

## Exercise 1.6¶

The procedure may crash when given an empty list because we are trying to apply car to '().

## Exercise 1.7¶

  1 2 3 4 5 6 7 8 9 10 11 (define (nth-element lst n) (let nth-element-impl ([lst0 lst] [n0 n]) (if (null? lst0) (report-list-too-short lst n) (if (zero? n0) (car lst0) (nth-element-impl (cdr lst0) (- n0 1)))))) (define (report-list-too-short lst n) (eopl:error 'nth-element "List ~s does not have ~s elements" lst n)) 

## Exercise 1.8¶

If the last line is replaced, this procedure drops the first occurrence of s together with all the elements before it:

drop-until : Sym x Listof(Sym) -> Listof(Sym)
usage: (drop-until s los) returns a list with the same
elements arranged in the same order as los,
except that the first occurrence of the symbol s
and all elements before it are removed.


## Exercise 1.9¶

 1 2 3 4 5 6 (define (remove s los) (if (null? los) '() (if (eqv? (car los) s) (remove s (cdr los)) (cons (car los) (remove s (cdr los)))))) 

## Exercise 1.10¶

Exclusive or, or “xor”.

## Exercise 1.11¶

The thing that gets smaller is the number of occurrences of old.

## Exercise 1.12¶

 1 2 3 4 5 6 7 8 9 (define (subst new old slist) (if (null? slist) '() (let ([head (car slist)] [tail (cdr slist)]) (cons (if (symbol? head) (if (eqv? head old) new head) (subst new old head)) (subst new old tail))))) 

## Exercise 1.13¶

 1 2 3 4 5 6 7 8 9 (define (subst new old slist) (map (lambda (sexp) (subst-in-s-exp new old sexp)) slist)) (define (subst-in-s-exp new old sexp) (if (symbol? sexp) (if (eqv? sexp old) new sexp) (subst new old sexp))) 

## Exercise 1.14¶

Proof:

Translated to mathematical language, partial-vector-sum is equivalent to the following function $$f(n)$$:

$\begin{split}f(n) = \begin{cases} v_0 & n = 0 \\ v_n + f(n - 1) & n > 0 \end{cases}\end{split}$

Let’s prove by induction on $$n$$. The induction hypothesis $$IH(k)$$, is

$f(n) = \sum_{i = 0}^{n}{v_i}$
1. When $$k = 0$$, $$IH(k)$$ holds because $$f(0) = v_0$$.

2. When $$k > 0$$, we have

$f(k) = v_k + f(k - 1)$

Since $$IH(k - 1)$$ holds, we have

$f(k) = v_k + \sum_{i = 0}^{k - 1}{v_i} = \sum_{i = 0}^{k}{v_i}$

Q.E.D.

## Exercise 1.15¶

 1 2 3 4 (define (duple n sexp) (if (zero? n) '() (cons sexp (duple (- n 1) sexp)))) 

## Exercise 1.16¶

 1 2 3 4 (define (invert lst) (map (lambda (pair) (list (cadr pair) (car pair))) lst)) 

## Exercise 1.17¶

 1 2 (define (down lst) (map list lst)) 

## Exercise 1.18¶

  1 2 3 4 5 6 7 8 9 10 11 12 (define (swapper s1 s2 slist) (map (lambda (sexp) (swapper-in-s-sexp s1 s2 sexp)) slist)) (define (swapper-in-s-sexp s1 s2 sexp) (cond [(symbol? sexp) (cond [(eqv? s1 sexp) s2] [(eqv? s2 sexp) s1] [else sexp])] [else (swapper s1 s2 sexp)])) 

## Exercise 1.19¶

 1 2 3 4 5 6 (define (list-set lst n x) (if (zero? n) (cons x (cdr lst)) (cons (car lst) (list-set (cdr lst) (- n 1) x)))) 

## Exercise 1.20¶

  1 2 3 4 5 6 7 8 9 10 (define (count-occurrences s slist) (if (null? slist) 0 (+ (count-occurrences-in-s-sexp s (car slist)) (count-occurrences s (cdr slist))))) (define (count-occurrences-in-s-sexp s sexp) (if (symbol? sexp) (if (eqv? sexp s) 1 0) (count-occurrences s sexp))) 

## Exercise 1.21¶

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 (define (product sos1 sos2) (flat-map (lambda (e1) (map (lambda (e2) (list e1 e2)) sos2)) sos1)) (define (flat-map proc lst) (if (null? lst) '() (append (proc (car lst)) (flat-map proc (cdr lst))))) (check-equal? (product '(a b c) '(x y)) '((a x) (a y) (b x) (b y) (c x) (c y))) 

## Exercise 1.22¶

  1 2 3 4 5 6 7 8 9 10 (define (filter-in pred lst) (if (null? lst) '() (let ([head (car lst)] [filtered-tail (filter-in pred (cdr lst))]) (if (pred head) (cons head filtered-tail) filtered-tail)))) (check-equal? (filter-in number? '(a 2 (1 3) b 7)) '(2 7)) 

## Exercise 1.23¶

 1 2 3 4 5 6 (define (list-index pred lst) (cond [(null? lst) #f] [(pred (car lst)) 0] [else (let ([index (list-index pred (cdr lst))]) (if index (+ 1 index) #f))])) 

## Exercise 1.24¶

 1 2 3 4 (define (every? pred lst) (cond [(null? lst) #t] [(pred (car lst)) (every? pred (cdr lst))] [else #f])) 

## Exercise 1.25¶

 1 2 3 4 (define (exists? pred lst) (cond [(null? lst) #f] [(pred (car lst)) #t] [else (exists? pred (cdr lst))])) 

## Exercise 1.26¶

 1 2 3 4 5 6 (define (up lst) (cond [(null? lst) '()] [(list? (car lst)) (append (car lst) (up (cdr lst)))] [else (cons (car lst) (up (cdr lst)))])) 

## Exercise 1.27¶

 1 2 3 4 5 6 (define (flatten slist) (cond [(null? slist) '()] [(list? (car slist)) (append (flatten (car slist)) (flatten (cdr slist)))] [else (cons (car slist) (flatten (cdr slist)))])) 

## Exercise 1.28¶

 1 2 3 4 5 6 7 (define (merge loi1 loi2) (cond [(null? loi1) loi2] [(null? loi2) loi1] [(< (car loi1) (car loi2)) (cons (car loi1) (merge (cdr loi1) loi2))] [else (cons (car loi2) (merge loi1 (cdr loi2)))])) 

## Exercise 1.29¶

 1 2 3 4 5 6 7 (define (sort loi) (define (merge-sort lst) (cond [(null? lst) '()] [(null? (cdr lst)) lst] [else (merge-sort (cons (merge (car lst) (cadr lst)) (merge-sort (cddr lst))))])) (car (merge-sort (map list loi)))) 

## Exercise 1.30¶

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 (define (sort/predicate pred loi) (define (merge-sort lst) (cond [(null? lst) '()] [(null? (cdr lst)) lst] [else (merge-sort (cons (merge/predicate pred (car lst) (cadr lst)) (merge-sort (cddr lst))))])) (car (merge-sort (map list loi)))) (define (merge/predicate pred loi1 loi2) (cond [(null? loi1) loi2] [(null? loi2) loi1] [(pred (car loi1) (car loi2)) (cons (car loi1) (merge/predicate pred (cdr loi1) loi2))] [else (cons (car loi2) (merge/predicate pred loi1 (cdr loi2)))])) 

## Exercise 1.31¶

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 (define (leaf n) n) (define (interior-node name lson rson) (list name lson rson)) (define (leaf? tree) (number? tree)) (define lson cadr) (define rson caddr) (define (contents-of tree) (cond [(leaf? tree) tree] [else (car tree)])) 

## Exercise 1.32¶

 1 2 3 4 5 6 7 (define (double-tree tree) (cond [(leaf? tree) (leaf (* 2 (contents-of tree)))] [else (interior-node (contents-of tree) (double-tree (lson tree)) (double-tree (rson tree)))])) 

## Exercise 1.33¶

  1 2 3 4 5 6 7 8 9 10 (define (mark-leaves-with-red-depth tree) (let mark [(n 0) (node tree)] (cond [(leaf? node) (leaf n)] [(eqv? (contents-of node) 'red) (interior-node 'red (mark (+ n 1) (lson node)) (mark (+ n 1) (rson node)))] [else (interior-node (contents-of node) (mark n (lson node)) (mark n (rson node)))]))) 

## Exercise 1.34¶

  1 2 3 4 5 6 7 8 9 10 11 12 (define (path n bst) (let [(value-of car) (lson cadr) (rson caddr)] (cond [(null? bst) (eopl:error 'path "Element ~s not found" n)] [(= (value-of bst) n) '()] [(< n (value-of bst)) (cons 'left (path n (lson bst)))] [else (cons 'right (path n (rson bst)))]))) 

## Exercise 1.35¶

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 (define (number-leaves tree) (define (number n node) (if (leaf? node) (list (+ n 1) (leaf n)) (let* [(lson-result (number n (lson node))) (lson-n (car lson-result)) (new-lson (cadr lson-result)) (rson-result (number lson-n (rson node))) (rson-n (car rson-result)) (new-rson (cadr rson-result))] (list rson-n (interior-node (contents-of node) new-lson new-rson))))) (cadr (number 0 tree))) 

## Exercise 1.36¶

  1 2 3 4 5 6 7 8 9 10 11 (define (number-elements lst) (if (null? lst) '() (g (list 0 (car lst)) (number-elements (cdr lst))))) (define (g head tail) (if (null? tail) (list head) (let* [(n (car head)) (next (car tail)) (new-next (cons (+ n 1) (cdr next)))] (cons head (g new-next (cdr tail))))))