Computer Exercise 1:
Here we use the last procedure
defined in the tutorial exercises:
(define (last lst)
(if (null? (cdr lst))
(car lst)
(last (cdr lst))))
(define (price-trend previous-close ticker)
(- (last ticker) previous-close))
As a quick check, let's verify the value for the ibm ticker,
and then see what we get for acme:
ibm-previous-close ;Value: 100. ibm-prices ;Value: (100.5 101.) (price-trend ibm-previous-close ibm-prices) ;Value: 1. (price-trend acme-previous-close acme-prices) ;Value: -3.25The price-trend procedure calls last, which results in an iterative process (there are no deferred operations after the recursive call to last from within last). The process is linear iterative, because the order of growth in space is S(n) = Theta(1), and in time is T(n) = Theta(n).
Computer Exercise 2:
Here's an iterative solution which does not use any higher
order procedures:
(define (price-average ticker)
(define (helper ticker sum count)
(if (null? ticker)
(/ sum count)
(helper (cdr ticker)
(+ sum (car ticker))
(+ count 1))))
(helper (cdr ticker) (car ticker) 1))
(price-average acme-prices)
;Value: 47.475
The price-average process from the above procedure is again
linear iterative: the growth in space is S(n) = Theta(1), and in time
is T(n) = Theta(n) where n is the prices on the ticker.
Computer Exercise 3:
Here are two different versions of list-max; the first
results in a recursive process (due to the deferred operation max
that must be performed after the recursive call to list-max).
The second version is linear iterative.
(define (list-max lst)
(if (null? (cdr lst))
(car lst)
(max (car lst) (list-max (cdr lst)))))
(list-max (list 1 5 10 3 2))
;Value: 10
(define (list-max lst)
(define (helper lst max-so-far)
(if (null? lst)
max-so-far
(helper (cdr lst)
(max max-so-far (car lst)))))
(helper (cdr lst) (car lst)
(price-high ibm-prices)
;Value: 101.
(price-high acme-prices)
;Value: 49.75
; A. price-high
(define (price-high ticker)
(accumulate (lambda (x y) (if (> x y) x y))
(car ticker)
(cdr ticker)))
; Same thing using built-in procedure max:
(define (price-high ticker)
(accumulate max (car ticker) (cdr ticker)))
(price-high acme-prices)
;Value: 49.75
This results in a recursive process because accumulate
as provided has a deferred operation (the max procedure) which
must wait until the result is returned from internal
accumulate call.
; B. Iter accumulate
(define (iter-accumulate combiner init lst)
(define (helper so-far lst)
(if (null? lst)
so-far
(helper (combiner (car lst) so-far)
(cdr lst))))
(helper init lst))
(define (price-high ticker)
(iter-accumulate max (car ticker) (cdr ticker)))
(price-high acme-prices)
;Value: 49.75
The two procedures accumulate and iter-accumulate
will not always give the same result. One example where they
do is the above price-high (which is equivalent to a
list-max procedure). An example where accumulate
and iter-accumulate give different examples is if we
attempt to copy a list (remember implementing copy using
accumulate in the tutorial exercises?):
(accumulate cons nil (list 1 2 3 4)) ;Value: (1 2 3 4) (iter-accumulate cons nil (list 1 2 3 4)) ;Value: (4 3 2 1)The key point to notice is that accumulate operates (with the passed in procedure) on the list in right to left order because it cdr's down the list first, then "combines up" (in this case using cons) an answer. In the case of iter-accumulate, on the other hand, the operator combines things up from left to right order. So the condition for equivalent use of the two is that the procedure or operator must be commutative -- that is, the order of the two arguments shouldn't matter to the procedure.
(define (price-range ticker)
(define (helper ticker low-so-far high-so-far)
(if (null? ticker)
(list low-so-far high-so-far)
(helper (cdr ticker)
(min low-so-far (car ticker))
(max high-so-far (car ticker)))))
(helper (cdr ticker) (car ticker) (car ticker)))
(price-range ibm-prices)
;Value: (100.5 101.)
(price-range acme-prices)
;Value: (45. 49.75)
(define (price-spreads ask-lst bid-lst)
(if (null? ask-lst)
nil
(cons (- (ask-price (car ask-lst))
(bid-price (car bid-lst)))
(price-spreads (cdr ask-lst) (cdr bid-lst)))))
(price-spreads ibm-ask ibm-bid)
;Value: (.5 0. 0.)
(price-spreads acme-ask acme-bid)
;Value: (.25 0. 1.5 0. 4. 0. 3. 0. 0. 1. 0. 1. 0. 0. 2. 0. 2.5 0.)
Note how we cdr down the two lists at the same time. This
results in a linear recursive process (due to the deferred
cons), with orders of growth in space S(n) = Theta(n), and in
time of T(n) = Theta(n).
(define (map2 proc lst1 lst2)
(if (null? lst1)
nil
(cons (proc (car lst1) (car lst2))
(map2 proc (cdr lst1) (cdr lst2)))))
(map2 + (list 1 2 3) (list 10 11 12))
;Value: (11 13 15)
(define (price-spreads ask-lst bid-lst)
(map2 (lambda (ask bid) (- (ask-price ask) (bid-price bid)))
ask-lst
bid-lst))
(price-spreads acme-ask acme-bid)
;Value: (.25 0. 1.5 0. 4. 0. 3. 0. 0. 1. 0. 1. 0. 0. 2. 0. 2.5 0.)
Computer Exercise 8:
The procedure trade? is a simple predicate, where we are
careful to use the accessor functions rather than car and
cdr directly.
(define (trade? ask bid)
(>= (bid-price bid) (ask-price ask)))
(define (ticker-prices asks bids)
(cond ((null? asks) nil)
((trade? (car asks) (car bids))
(cons (ask-price (car asks))
(ticker-prices (cdr asks) (cdr bids))))
(else (ticker-prices (cdr asks) (cdr bids)))))
(ticker-prices ibm-asks ibm-bids)
;Value: (100.5 101.)
(ticker-prices acme-ask acme-bid)
;Value: (49.75 48.75 47. 45. 46.25 48. 47.5 48.5 47.25 46.75)
(define (merge2 pred proc list1 list2)
(cond ((null? list1) nil)
((pred (car list1) (car list2))
(cons (proc (car list1) (car list2))
(merge2 pred proc (cdr list1) (cdr list2))))
(else (merge2 pred proc (cdr list1) (cdr list2)))))
(merge2 (lambda (x y) (and (odd? x) (odd? y)))
+
(list 1 2 3 4)
(list 5 3 5 3))
;Value: (6 8)
(define (ticker-prices asks bids)
(merge2 trade?
(lambda (ask bid) (ask-price ask))
asks bids))
(ticker-prices acme-ask acme-bid)
;Value: (49.75 48.75 47. 45. 46.25 48. 47.5 48.5 47.25 46.75)
(define (ticker-shares asks bids)
(merge2 trade?
(lambda (ask bid)
(min (cdr ask) (cdr bid)))
asks bids))
(ticker-shares acme-ask acme-bid)
;Value: (100 100 100 400 100 200 200 100 100 100)
(define (total-shares asks bids)
(accumulate + 0 (ticker-shares asks bids)))
(total-shares acme-ask acme-bid)
;Value: 1500
(define (price-volume asks bids)
(accumulate +
0
(map2 *
(ticker-shares asks bids)
(ticker-prices asks bids))))
(price-volume acme-ask acme-bid)
;Value: 70525.
Computer Exercise 13:
Here we convert the tree into a list of just its leaves
using the fringe procedure from the tutorial exercises.
Then we just need to sum up the items in the list:
(define (assembly-line-hours tree-of-hours)
(accumulate + 0 (fringe tree-of-hours)))
(define (fringe tree)
(cond ((null? tree) nil)
((not (pair? tree)) (list tree))
(else (append (fringe (car tree))
(fringe (cdr tree))))))
(assembly-line-hours NeoWidget-hours)
;Value: 15
(assembly-line-hours MegaWidget-hours)
;Value: 85
Computer Exercise 14:
Here is a tree-accumulate procedure that applies
a combiner procedure to the results of recursing down
both the car and the cdr branches. When we
hit a leaf, we use the op on it to get a value.
(define (tree-accumulate combiner op initial tree)
(cond ((null? tree) initial)
((not (pair? tree))
(op tree))
(else
(combiner (tree-accumulate combiner op initial (car tree))
(tree-accumulate combiner op initial (cdr tree))))))
(define (assembly-line-hours tree-of-hours)
(tree-accumulate + (lambda (x) x) 0 tree-of-hours))
(assembly-line-hours MegaWidget-hours)
;Value: 85
Computer Exercise 15:
This is essentially just a count-leaves procedure:
(define count-line-stations count-leaves)
(define (count-leaves tree)
(cond ((null? tree) 0)
((not (pair? tree)) 1)
(else (+ (count-leaves (car tree))
(count-leaves (cdr tree))))))
(count-line-stations NeoWidget-hours)
;Value: 5
(count-line-stations MegaWidget-hours)
;Value: 11
Note that we could also implement count-leaves (or
count-line-stations) using accumulate:
(define (count-line-stations tree) (tree-accumulate + (lambda (item) 1) 0 tree))
Computer Exercise 16:
This one was a little tricky. At each level, we can
use map to get the parallel assembly hours for each
subtree under that, and then pick of the max value using
our list-max procedure.
(define (assembly-parallel-hours tree)
(cond ((null? tree) 0)
((not (pair? tree)) tree)
(else
(+ 1 (list-max (map assembly-parallel-hours tree))))))
(assembly-parallel-hours NeoWidget-hours)
;Value: 7
(assembly-parallel-hours MegaWidget-hours)
;Value: 18
Computer Exercise 17:
Our procedure tree-accumulate doesn't really work here,
because that only let us provide a procedure that operates on leaves.
In this case, we need to be able to count internal nodes in the tree.
Indeed, count-parallel-stations is equivalent to counting
the sum of the number of nodes and the number of leaves.
This sounds difficult unless one really breaks the problem down to the base cases, and then uses wishful thinking. An empty list has no nodes and no leaves. A leaf (not a pair) counts as 1. If the tree has subtrees in it, then we count 1 for the node, and then add to that the number of leaves and nodes in the subtrees:
(define (count-nodes-and-leaves tree)
(cond ((null? tree) 0)
((not (pair? tree)) 1) ; count the leaf
(else
(+ 1 ; count the node
(accumulate + 0 (map count-nodes-and-leaves tree))))))
(define count-parallel-stations count-nodes-and-leaves)
(count-parallel-stations NeoWidget-hours)
;Value: 8
(count-parallel-stations MegaWidget-hours)
;Value: 19
Computer Exercise 18:
The basic strategy is to calculate the time required for
the original manufacturing plan, and then to build a new tree
with the leaf times scaled by the factor and find the time needed
for that new tree. To make this easier, we'll define map-tree
which creates a new tree from the old tree, applying some procedure
to the leaves; this is just a simple case of our tree-accumulate
procedure.
(define (map-tree proc tree)
(tree-accumulate cons proc nil tree))
(define (parallel-scale component-time-factor tree)
(let ((original-time (assembly-parallel-hours tree))
(new-tree (map-tree (lambda (x) (* x component-time-factor))
tree)))
(/ (assembly-parallel-hours new-tree)
original-time)))
(parallel-scale 0.5 NeoWidget-hours)
;Value: .7142 ; NOTE: problem set handout is WRONG - this is 5/7
(parallel-scale 0.5 MegaWidget-hours)
;Value: .5833
Computer Exercise 19:
Tired of this yet? These procedures are pretty easy if we
use the previous higher order procedures. The main trick is to
figure out how to walk all three trees together at the same time.
In this case, we look at the assembly-tree to decide if
we are ready to accumulate costs or if we just need to add the
parts costs for the subtrees:
(define (sum-parts-cost assembly-tree parts-tree costs-tree)
(cond ((null? assembly-tree) 0)
((not (pair? assembly-tree))
(accumulate + 0 (map2 * parts-tree costs-tree)))
(else
(+ (sum-parts-cost (car assembly-tree)
(car parts-tree)
(car costs-tree))
(sum-parts-cost (cdr assembly-tree)
(cdr parts-tree)
(cdr costs-tree))))))
(sum-parts-cost NeoWidget-hours
NeoWidget-parts-count
NeoWidget-parts-cost)
;Value: 188
(sum-parts-cost MegaWidget-hours
MegaWidget-parts-count
MegaWidget-parts-cost)
;Value: 680
Computer Exercise 20:
This is almost identical to the previous procedure; the only
difference is that instead of ADDING the two subtrees, we simply
cons them together:
(define (summarized-costs-tree assembly-tree parts-tree costs-tree)
(cond ((null? assembly-tree) nil)
((not (pair? assembly-tree))
(accumulate + 0 (map2 * parts-tree costs-tree)))
(else
(CONS (summarized-costs-tree (car assembly-tree)
(car parts-tree)
(car costs-tree))
(summarized-costs-tree (cdr assembly-tree)
(cdr parts-tree)
(cdr costs-tree))))))
(summarized-costs-tree NeoWidget-hours
NeoWidget-parts-count
NeoWidget-parts-cost)
;Value: (30 (30 (24 34)) 70)
(summarized-costs-tree MegaWidget-hours
MegaWidget-parts-count
MegaWidget-parts-cost)
;Value: ((11 29) ((43 173) (35 42)) (34 (10 3)) (140 160))