<![CDATA[
CSE341 Key to Final, Spring 2010 handout #24
1. Scheme expressions.
Part A:
(define a 2)
(define b 3)
(define c 5)
(let ((b (* a c))
(a (* b c)))
(list a b c))
(15 10 5)
Part B:
(define a 2)
(define b 3)
(define c 5)
(let* ((b (* a b))
(a (* a b)))
(list a b c))
(12 6 5)
Part C:
(define x 2)
(define (f n) (* x y n))
(define y 3)
(define a (f 7))
(define x 5)
(define b (f 2))
(define c a)
(set! a 13)
(list a b c)
(13 30 42)
Part D:
(define a '(1 2 3))
(define b (cons 1 (cdr a)))
(define c (append '(0) b))
(list c (eq? a b) (eq? (cdr a) (cdr b)) (eq? (cdr c) b))
((0 1 2 3) #f #t #t)
2. Two possible solutions appear below.
(define (numbers? lst)
(or (null? lst) (and (number? (car lst)) (numbers? (cdr lst)))))
(define (numbers? lst)
(andmap number? lst))
3. Two possible solutions appear below.
(define (nonzero-product lst)
(cond ((null? lst) 1)
((null? (cdr lst)) (car lst))
((= (car lst) 0) (nonzero-product (cdr lst)))
(else (* (car lst) (nonzero-product (cdr lst))))))
(define (nonzero-product lst)
(foldl * 1 (filter (lambda (n) (not (= n 0))) lst)))
4. One possible solution appears below.
(define (times n thunk)
(define (helper m result)
(if (= m 0)
(reverse result)
(helper (- m 1) (cons (thunk) result))))
(if (< n 0)
(error "negative n")
(helper n ())))
5. One possible solution appears below.
(define (add v tree)
(cond ((null? tree) (list v () ()))
((<= v (car tree)) (list (car tree) (add v (cadr tree))
(caddr tree)))
(else (list (car tree) (cadr tree)
(add v (caddr tree))))))
6. One possible solution appears below.
(define (multiply n data)
(if (null? data)
()
(append (times n (lambda () (car data)))
(multiply n (cdr data)))))
7. One possible solution appears below.
(define (intermingle lst)
(define (helper data)
(cond ((null? data) ())
((not (number? (car data))) (error "not a number"))
((null? (cdr data)) data)
((not (number? (cadr data))) (error "not a number"))
(else (cons (car data) (cons (- (cadr data) (car data))
(helper (cdr data)))))))
(if (list? lst)
(helper lst)
(error "not a list")))
8. One possible solution appears below.
(define (partitionable lst)
(define (explore rest sum1 sum2)
(if (null? rest)
(= sum1 sum2)
(or (explore (cdr rest) (+ sum1 (car rest)) sum2)
(explore (cdr rest) sum1 (+ sum2 (car rest))))))
(explore lst 0 0))
9. Ruby expressions.
Part A:
y.each {|s| puts s + " " + s}
foo foo
bar bar
baz baz
mumble mumble
Part B:
y.find_all {|s| s.length == 3}
["foo", "bar", "baz"]
Part C:
z = []
for n in x do
z.push -n
end
[2, 1, 0, -1, -2]
10. Two possible solutions appear below.
class Integer
def digits()
n = self.abs
loop do
yield n % 10
n /= 10
break if n == 0
end
self
end
end
class Integer
def digits2()
n = self.abs
yield n % 10
if n >= 10
(n / 10).digits {|n| yield n}
end
self
end
end
11. One possible solution appears below.
def prepend(s1, lst)
lst.map {|s2| s1 + s2}
end
12. One possible solution appears below.
class Array
def closed
for x in self
for y in self
return false if !self.member?(yield(x, y))
end
end
true
end
end
13. One possible solution appears below.
def generate(data)
if data.length == 0
return data
elsif data.length == 1
return [data[0].to_s]
else
other = generate(data[1..-1])
return prepend(data[0].to_s + " + ", other) +
prepend(data[0].to_s + " - ", other) +
prepend(data[0].to_s + " * ", other)
end
end
]]>