Dan's Thoughts

22Aug/090

Exercise 2.37 of SICP

Exercise 2.37: Suppose we represent vectors $v=(v_i)$ as sequences of numbers, and matrices $m = (m_{ij})$ as sequences of vectors (the rows of the matrix). For example, the matrix

$M = \begin{bmatrix} 1&2&3&4\\ 4&5&6&6\\ 6&7&8&9 \end{bmatrix}$

is represented as the sequence ((1 2 3 4) (4 5 6 6) (6 7 8 9)). With this representation, we can use sequence operations to concisely express the basic matrix and vector operations. These operations (which are described in any book on matrix algebra) are the following:

(dot-product v w)	returns the sum $\sum_{i} v_iw_i$
(matrix-*-vector m v)	returns the vector t, where $t_i = \sum_{j} m_{ij}v_j$
(matrix-*-matrix m n)	returns the matrix p where, $p_{ij} = \sum_{k} m_{ik}n_{kj}$
(transpose m)	returns the matrix n where, $n_{ij} = m_{ji}$

We can define the dot product as:

(define (dot-product v w)
  (accumulate + 0 (map * v w)))

Fill in the missing expressions in the following procedures for computing the other matrix operations. (The procedure accumulate-n is defined in exercise 2.36.)

(define (matrix-*-vector m v)
  (map <??> m))
(define (transpose mat)
  (accumulate-n <??> <??> mat))
(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map <??> m)))

Solutions:

(define (accumulate fn init-value items)
  (if (null? items)
    init-value
    (fn (car items)
        (accumulate fn init-value (cdr items)))))
 
(define (accumulate-n op init seqs)
  (if (null? (car seqs))
    '()
      (cons (accumulate op init (map (lambda (e) (car e)) seqs))
            (accumulate-n op init (map (lambda (e) (cdr e)) seqs)))))

(define (matrix-*-vector m v)
  (map (lambda (row) (dot-product row v)) m))

(define (transpose mat)
  (accumulate-n cons '() mat))

(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map (lambda (row) (matrix-*-vector cols row))
         m)))

> (define n (list (list 1 2) (list 3 4)))
> (matrix-*-vector n (list 10 20))
(50 110)
> (transpose n)
((1 3) (2 4))
> (define m (list (list 1 2 3) (list 4 5 6) (list 7 8 9)))
> (matrix-*-matrix m m)
((30 36 42) (66 81 96) (102 126 150))
> (define q (list (list 9 1) (list 3 4) (list 6 7) (list 1 8)))
> (matrix-*-matrix (list (list 1 2 3 4) (list 5 6 7 8)) q)
((37 62) (113 142))

Filed under: SICP, lisp, math No Comments

21Aug/090

Exercise 2.36 of SICP

Exercise 2.36: The procedure accumulate-n is similar to accumulate except that it takes as its third argument a sequence of sequences, which are all assumed to have the same number of elements. It applies the designated accumulation procedure to combine all the first elements of the sequences, all the second elements of the sequences, and so on, and returns a sequence of the results. For instance, if s is a sequence containing four sequences, ((1 2 3) (4 5 6) (7 8 9) (10 11 12)), then the value of (accumulate-n + 0 s) should be the sequence (22 26 30). Fill in the missing expressions in the following definition of accumulate-n:

(define (accumulate fn init-value items)
  (if (null? items)
    init-value
    (fn (car items)
        (accumulate fn init-value (cdr items)))))
 
(define (accumulate-n op init seqs)
  (if (null? (car seqs))
    '()
      (cons (accumulate op init (map (lambda (e) (car e)) seqs))
            (accumulate-n op init (map (lambda (e) (cdr e)) seqs)))))

> (define s (list (list 1 2 3) (list 4 5 6) (list 7 8 9) (list 10 11 12)))
> (accumulate-n + 0 s)
(22 26 30)

Filed under: SICP, lisp No Comments

20Aug/090

Exercise 2.35 of SICP

Exercise 2.35: Redefine count-leaves from section 2.2.2 as an accumulation:

(define (count-leaves t)
  (accumulate <??> <??> (map <??> <??>)))

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

The goal here is for map to create something that accumulate can consume to count the number of leaves. The initial value must be 0 just like in count-leaves. The hard part is to come up with fn that will add up the leaves. If the tree is flatted a simple length function will compute the number of trees.

(define (accumulate fn init-value items)
  (if (null? items)
    init-value
    (fn (car items)
        (accumulate fn init-value (cdr items)))))
 
(define (enumerate-tree x)
  (cond ((null? x) '())
        ((not (pair? x))
         (list x))
        (else
          (append (enumerate-tree (car x)) (enumerate-tree (cdr x))))))
 
(define (count-leaves t)
  (accumulate (lambda (x y) (+ 1 y)) 
              0
              (map (lambda (x) x) (enumerate-tree t))))

I am not sure why map is needed in this example. It just serves to confuse. The lambda argument is really a throw away.
I am aware that it is possible to solve this problem using map in a way that recursively calls count-leaves. I feel like instead of making the computational process clearer as in square-tree and even-fibs it becomes more convoluted and mysterious. Nevertheless I include it bellow for completeness.

(define (count-leaves t)
  (accumulate
    +
    0 
    (map (lambda (elem)
           (if (not (pair? elem))
             1
             (count-leaves elem))) t)))

The example I like is:

(define (deep-reverse seq)
  (map (lambda (e) 
         (if (not (pair? e))
           e
           (deep-reverse e)))
       (reverse seq)))

Filed under: SICP, lisp No Comments

19Aug/090

Exercise 2.34 of SICP

Exercise 2.34: Evaluating a polynomial in x at a given value of x can be formulated as an accumulation. We evaluate the polynomial
$p(x) = a_n x^n + a_{n-1}x^{n-1} + \cdots + a_1 x+ a_0$
using a well-known algorithm called Horner's rule, which structures the computation as
$(\cdots (a_n x + a_{n-1})x + \cdots + a_1)x + a_0$
In other words, we start with an, multiply by x, add a_n-1, multiply by x, and so on, until we reach a₀. Fill in the following template to produce a procedure that evaluates a polynomial using Horner's rule. Assume that the coefficients of the polynomial are arranged in a sequence, from a₀ through a_n.

(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms) <??>)
              0
              coefficient-sequence))

For example, to compute $1 + 3x + 5x^3 + x^5$ at $x = 2$ you would evaluate

(horner-eval 2 (list 1 3 0 5 0 1))

I included a non-abstracted version of Horner's method for clarity.

(define (accumulate fn init-value items)
  (if (null? items)
    init-value
    (fn (car items)
        (accumulate fn init-value (cdr items)))))
 
(define (he x coeff-seq)
  (if (null? coeff-seq)
    0
    (+ (car coeff-seq)
       (* x (he x (cdr coeff-seq))))))
 
(define (horner-eval x coeff-seq)
  (accumulate (lambda (this-coeff higher-terms)
                (+ this-coeff (* x higher-terms)))
              0
              coeff-seq))

> (horner-eval 2 (list 1 3 0 5 0 1))
79
> (horner-eval 2 (list 1))
1
> (horner-eval 2 (list ))
0
> (horner-eval 2 (list 1 1))
3

Filed under: SICP, lisp, math No Comments

18Aug/090

Exercise 2.33 of SICP

Exercise 2.33: Fill in the missing expressions to complete the following definitions of some basic list-manipulation operations as accumulations:

(define (map p sequence)
  (accumulate (lambda (x y) <??>) nil sequence))
(define (append seq1 seq2)
  (accumulate cons <??> <??>))
(define (length sequence)
  (accumulate <??> 0 sequence))

(define (accumulate fn init-value items)
  (if (null? items)
    init-value
    (fn (car items)
        (accumulate fn init-value (cdr items)))))
 
(define (map p sequence)
  (accumulate (lambda (x y) (cons (p x) y)) '() sequence))
 
(define (append seq1 seq2)
  (accumulate cons seq2 seq1))
 
(define (length seq)
  (accumulate (lambda (x y) (+ 1 y)) 0 seq))

I find it interesting how length is created by discarding the x in lambda thus discarding (car items).

Filed under: SICP, lisp No Comments

17Aug/090

Exercise 2.32 of SICP

Exercise 2.32: We can represent a set as a list of distinct elements, and we can represent the set of all subsets of the set as a list of lists. For example, if the set is (1 2 3), then the set of all subsets is (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)). Complete the following definition of a procedure that generates the set of subsets of a set and give a clear explanation of why it works:

(define (subsets s)
  (if (null? s)
      (list nil)
      (let ((rest (subsets (cdr s))))
        (append rest (map <??> rest)))))

In order for me to understand what is going on here, I understand how powersets are constructed first and then derive this function.

This program wants to create what is called a powerset.
If S is a set of {a₁,a₂,a₃}
$\mathcal{P}(S) = \{\{\} \{a_3\} \{a_2\} \{a_2 a_3\} \{a_1\} \{a_1 a_3\} \{a_1 a_2\} \{a_1 a_2 a_3\}\}$
The reasoning to construct a powerset is similar to the way the count change example is thought about.
Create a powerset for the cdr elements without using the car element, cons the car element with powerset of cdr elements. To the result append powerset of cdr elements.

When the arguments are an element and a set inject the element into every element of the set creating a new set. Append that result with the original powerset injected into.

P{}
{}

P{a₁}
(append (inject a₁ P{}) P{})
{{a₁} }

P{a₁ a₂}
(append (inject a₁ P{a₂}) P{a₂})
(append {{a₁ a₂} {a₁}} P{a₂})
{{a₁ a₂} {a₁} {a₂} }

P{a₁ a₂ a₃}
(append (inject a₁ P{a₂ a₃}) P{a₂ a₃})
(append (inject a₁ (apend (inject a₂ P{a₃}) P{3}))
        (append (inject a₂ P{a₃}) P{a₃}))

(append (inject a₁ (append (inject a₂ {{a₃} }) {{a₃} }))
        (append (inject a₂ {{a₃} }) {{a₃} }))

(append (inject a₁ (append {{a₃ a₂} {a₂}} {{a₃} }))
        (append (inject a₂ {{a₃} }) {{a₃} }))

(append (inject a₁ {{a₃ a₂} {a₂} {a₃} })
        (append {{a₃ a₂} {a₂}} {{a₃} }))

(append {{a₃ a₂ a₁ } {a₂ a₁} {a₃ a₁} {a₁}}
        (append {{a₃ a₂} {a₂}} {{a₃} }))

(append {{a₃ a₂ a₁ } {a₂ a₁} {a₃ a₁} {a₁}}
        {{a₃ a₂} {a₂} {a₃} })

{{a₃ a₂ a₁} {a₂ a₁} {a₃ a₁} {a₁} {a₃ a₂} {a₂} {a₃} }

Here is the process above in code:

(define (powerset ss)
  (if (null? ss)
    (list '())
    (append (inject (car ss) 
                    (powerset (cdr ss))) 
            (powerset (cdr ss)))))
(define (inject s ss)
  (map (lambda (elem)
           (cons s elem))
       ss))

Finally:

(define (subsets s)
  (if (null? s)
      (list '())
      (let ((rest (subsets (cdr s))))
        (append rest (map (lambda (elem) (cons (car s) elem)) 
                          rest)))))

It's worth noticing that because of the let expression (subsets (cdr s)) is only called once, as opposed to twice in my earlier derivation.

Filed under: SICP, lisp, math No Comments

16Aug/090

Exercise 2.31 of SICP

Exercise 2.31: Abstract your answer to exercise 2.30 to produce a procedure tree-map with the property that square-tree could be defined as

(define (square-tree tree) (tree-map square tree))

(define (tree-map fn tree)
  (map (lambda (sub-tree)
         (if (not (pair? sub-tree))
           (fn sub-tree)
           (tree-map fn sub-tree)))
       tree))
 
(define (square-tree tree) 
  (tree-map (lambda (x) (* x x)) tree))

> (define t (list 1
(list 2 (list 3 4) 5)
(list 6 7)))
> t
(1 (2 (3 4) 5) (6 7))
> (square-tree t)
(1 (4 (9 16) 25) (36 49))

Filed under: SICP, lisp No Comments

15Aug/090

Exercise 2.30 of SICP

Exercise 2.30: Define a procedure square-tree analogous to the square-list procedure of exercise 2.21. That is, square-list should behave as follows:

(square-tree
 (list 1
       (list 2 (list 3 4) 5)
       (list 6 7)))
(1 (4 (9 16) 25) (36 49))

Define square-tree both directly (i.e., without using any higher-order procedures) and also by using map and recursion.

(define (map proc items)
  (if (null? items)
    '()
    (cons (proc (car items)) (map proc (cdr items)))))
 
(define (square x) (* x x))
 
(define (square-tree tree)
  (cond ((null? tree) '())
        ((not (pair? tree)) (square tree))
        (else
          (cons (square-tree (car tree))
                (square-tree (cdr tree))))))
 
(define (map-square-tree tree)
  (map (lambda (sub-tree)
           (if (not (pair? sub-tree))
             (square sub-tree)
             (map-square-tree sub-tree)))
         tree))

> (define t (list 1
(list 2 (list 3 4) 5)
(list 6 7)))
> t
(1 (2 (3 4) 5) (6 7))
> (map-square-tree t)
(1 (4 (9 16) 25) (36 49))
> (square-tree t)
(1 (4 (9 16) 25) (36 49))

Filed under: SICP, lisp No Comments

14Aug/090

Exercise 2.29 of SICP

Exercise 2.29: A binary mobile consists of two branches, a left branch and a right branch. Each branch is a rod of a certain length, from which hangs either a weight or another binary mobile. We can represent a binary mobile using compound data by constructing it from two branches (for example, using list):

(define (make-mobile left right)
  (list left right))

A branch is constructed from a length (which must be a number) together with a structure, which may be either a number (representing a simple weight) or another mobile:

(define (make-branch length structure)
  (list length structure))

a. Write the corresponding selectors left-branch and right-branch, which return the branches of a mobile, and branch-length and branch-structure, which return the components of a branch.

(define (make-mobile left right)
  (list left right))
(define (left-branch mobile)
  (if (null? mobile) 
    '()
    (car mobile)))
(define (right-branch mobile)
  (if (null? mobile) 
    '()
    (car (cdr mobile))))
(define (make-branch length structure)
  (list length structure))
(define (branch-length branch)
  (if (null? branch)
    0
    (car branch)))
(define (branch-structure branch)
  (if (null? branch)
    0
    (car (cdr branch))))

b. Using your selectors, define a procedure total-weight that returns the total weight of a mobile.

(define (total-weight mobile)
  (define (weight? x)
    (not (pair? x)))
  (define (weight-of-branch branch)
    (let ((struct (branch-structure branch)))
      (if (weight? struct)
        struct
        (total-weight struct))))
 
  (let ((lbranch (left-branch mobile))
        (rbranch (right-branch mobile)))
    (cond ((null? mobile) 0)
          (else
            (+ 
              (weight-of-branch lbranch)
              (weight-of-branch rbranch))))))

> (define m (make-mobile (make-branch 1 2) (make-branch 3 4)))
> (total-weight m)
6
> (define n (make-mobile (make-branch 1 (make-mobile (make-branch 1 2) (make-bra
nch 3 4))) (make-branch 2 (make-mobile (make-branch 2 2) (make-branch 3 1)))))
> (total-weight n)
9

c. A mobile is said to be balanced if the torque applied by its top-left branch is equal to that applied by its top-right branch (that is, if the length of the left rod multiplied by the weight hanging from that rod is equal to the corresponding product for the right side) and if each of the submobiles hanging off its branches is balanced. Design a predicate that tests whether a binary mobile is balanced.

(define (torque-balanced? mobile)
  (define (weight? x)
    (not (pair? x)))
  (define (torque branch)
    (let ((struct (branch-structure branch)))
      (* (branch-length branch)
         (if (weight? struct)
           struct
           (+ (torque (left-branch struct))
              (torque (right-branch struct)))))))
  (if (null? mobile) 
    #t
    (= (torque (left-branch mobile))
       (torque (right-branch mobile)))))

> (define m (make-mobile (make-branch 1 2) (make-branch 2 1)))
> (torque-balanced? m)
#t
> (torque-balanced? n)
#t
> (define m (make-mobile (make-branch 1 2) (make-branch 2 2)))
> (torque-balanced? m)
#f

d. Suppose we change the representation of mobiles so that the constructors are

(define (make-mobile left right)
  (cons left right))
(define (make-branch length structure)
  (cons length structure))

How much do you need to change your programs to convert to the new representation?

Only two changes are needed to selectors of the right side elements because (cdr (list 1 (list 2))) returns ((2)). However the nested list problem doesn't happen with dotted pairs.

(define (right-branch mobile)
  (if (null? mobile) 
    '()
    (cdr mobile)))

(define (branch-structure branch)
  (if (null? branch)
    0
    (cdr branch)))

Filed under: SICP, lisp No Comments

13Aug/090

Exercise 2.28 of SICP

Exercise 2.28: Write a procedure fringe that takes as argument a tree (represented as a list) and returns a list whose elements are all the leaves of the tree arranged in left-to-right order. For example,

(define x (list (list 1 2) (list 3 4)))

(fringe x)
(1 2 3 4)

(fringe (list x x))
(1 2 3 4 1 2 3 4)

(define (fringe x)
  (cond ((null? x) '())
        ((not (pair? x))
         (list x))
        (else
          (append (fringe (car x)) (fringe (cdr x))))))

> (define x (list (list 1 2) (list 3 4)))
> (fringe x)
(1 2 3 4)
> (fringe (list x x))
(1 2 3 4 1 2 3 4)

Filed under: SICP, lisp No Comments

« Newer Entries Older Entries »

Dan's Thoughts Thinking somewhat carefully

Exercise 2.37 of SICP

Exercise 2.36 of SICP

Exercise 2.35 of SICP

Exercise 2.34 of SICP

Exercise 2.33 of SICP

Exercise 2.32 of SICP

Exercise 2.31 of SICP

Exercise 2.30 of SICP

Exercise 2.29 of SICP

Exercise 2.28 of SICP

Pages

Categories

Blogroll

Archive

Meta