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))))))