Sunday, June 7, 2009

Ex-2.38

Result from fold-left and fold-right is same only when op is such that (op x y) is equal to (op y x), mathematically its called the commutative property.

Ex-2.37

(define (matrix-*-vector m v)
(map
(lambda (w)
(dot-product v w)) m))
(define (transpose mat)
(accumulate-n
(lambda (x y) (cons x y))
'() mat))
(define (matrix-*-matrix m n)
(let ((cols (transpose n)))
(map
(lambda (v)
(map (lambda (w) (dot-product v w)) cols))
m)))

Ex-2.36

(define (accumulate-n op init seqs)
(if (or (null? seqs) (null? (car seqs)))
'()
(cons (accumulate op init
(map (lambda (x) (car x)) seqs))
(accumulate-n op init
(map (lambda (x) (cdr x)) seqs)))))

Ex-2.35

basically with map we create a flat list containing number of leaves in each subtree and then accumulate is used to sum them up.
(define (count-leaves t)
(accumulate
+ 0
(map (lambda (x)
(if (pair? x)
(count-leaves x) 1)) t)))

Ex-2.34

(define (horner-eval x coefficient-sequence)
(accumulate (lambda (this-coeff higher-terms)
(+ this-coeff (* higher-terms x)))
0
coefficient-sequence))

Ex-2.33

(define (map p sequence)
(accumulate (lambda (x y) (cons (p x) y)) nil sequence))
(define (append seq1 seq2)
(accumulate cons seq2 seq1))
(define (length sequence)
(accumulate (lambda (x y) (+ y 1)) 0 sequence))

Ex-2.32

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

Why it works?
Wishful thinking :)
we assumed that we got subsets of (cdr s), now all we need to think is how to get additional subsets of s that contain (car s) and the answer is simply to include (car s) in all the subsets of (cdr s).