|
|
Tutorial 2: Service
Managers and Destructive Methods (May 11)
This tutorial first briefly covers the use of service managers to achieve
encapsulation. Then we delve more deeply into destructive functions, especially
destructive list processing.
These concepts are introduced in Lecture Module 2
(see Handouts).
- Service Managers
- Closed line interval
A closed interval on the real number line between numbers a and
b is
usually denoted by [a,b],
and this represents all numbers x such that
a ≤ x ≤ b.
We want to encapsulate the notion of an interval using a service manager,
with mutation functions set-a and set-b for the
endpoints, and a single predicate function contains? which
consumes a number and returns true iff that number is in the interval.
Write a function make-interval which consumes two initial
endpoints a and b and produces a service manager which
can handle the three messages given above.
- Keeping a running average (Part II)
In last week's lab, we saw an example where we want
to add test scores into some type of structure, and to be told the running
average of all scores entered so far at each step. This was implemented as
a single function which returned a 1-ary lambda expression. A sample solution is
as follows:
;;make-running-average: -> (num -> num)
(define (make-running-average)
(local ((define sum 0)
(define n 0))
(lambda (new)
(begin (set! sum (+ sum new))
(set! n (+ n 1))
(/ sum n)))))
Now we want to extend this solution by using the service-manager paradigm
for encapsulation, and adding a little more functionality. The functions we
want to support are:
add-score: num →
Adds in the given score and updates internal variables accordingly
get-avg: → num
Returns the average of all scores entered so far.
get-max: → num
Returns the highest score entered so far.
get-min: → num
Returns the lowest score entered so far.
get-num-scores: → num
Returns the number of scores entered so far
Write a function, make-score-averager, which takes no
arguments and returns a service manager supporting the above functionality.
- New semantics for mutation
In lecture, we showed why we need new semantics to deal with mutation
when we have self-referential and co-referential data structures. Using these
new semantics, work through the evaluation of the following code snippets.
You should also be able to show the effects of the examples using box and
pointer diagrams.
These will likely be useful to you to help visualize what is
happening, but remember they are not a replacement for the strict semantics.
(define-struct node (ssn name left right))
(define node1 (make-node 5 'Tingting false false))
(define node2 (make-node 1 'James false node1))
(set-node-ssn! node1 6)
(define lst-1 (cons 'b (cons 'c empty)))
(define lst-2 (cons 'a (rest lst-1)))
(set-rest! (rest lst-2) (cons 'd empty))
(set! lst-1 (cons 'a (cons 'd empty)))
(set-rest! lst-2 (rest (rest lst-2)))
(set-rest! lst-1 empty)
- Destructive List Processing
When we speak of "destructive list processing", what we usually mean is
that the original list or lists passed in to the function as arguments may
be changed (or "destroyed"). A natural question is why we would ever want to
do this. The reason is that we make use of list mutation (i.e.
set-first! and set-rest!) to avoid creating new
cons cells in our function execution, thus making the program
more memory-efficient.
The following exercises ask you to write some destructive list processing
functions. A useful technique in some of these may be to write the
non-destructive version of the function first, and then try to modify this
solution to use mutation and avoid creating new cons cells (this is done for
you in the first example).
- Merging two sorted lists
Given two lists of numbers in ascending order, it is a relatively
common operation to merge those two lists, resulting in one list of numbers
in ascending order. The following is a simple implementation of
merge that does not use mutation:
(define (merge alon1 alon2)
(cond [(empty? alon1) alon2]
[(empty? alon2) alon1]
[(< (first alon2) (first alon1))
(cons (first alon2) (merge alon1 (rest alon2)))]
[else
(cons (first alon1) (merge (rest alon1) alon2))]))
Create a new function, merge!, which behaves similarly to
merge, but uses mutation to avoid creating any new
cons cells - that is, using destructive list processing.
Question: What will the input lists look like after
merge! finishes execution? Should we even care?
- Flattening a list of lists
To "flatten" a list of lists is to create a single list which contains
each element in each list of the list of lists, in order. So, for instance,
"flattening" '((1 2) () (3) (4 5 6)) would produce
'(1 2 3 4 5 6).
Write a function, flatten!, which consumes a list of lists,
and flattens to create a single list, using mutation to avoid creating new
cons cells.
- Removing even-indexed elements
Write a function,
remove-evens!, which consumes a list and
modifies that list to contain only the odd-indexed elements. Note that sometimes
with destructive list processing, we do not care what happens to the original
input lists, but here the whole point is that the original list should be
mutated in a specific way. So, for example, after executing
the following two lines of code:
(define lst '(a b c d e f g))
(remove-evens! lst)
the value of lst should be '(a c e g).
- Removing odd-indexed elements
Write a function, remove-odds!, which consumes a list and modifies
that list to contain only the even-indexed elements. This is of course
quite similar to the previous exercise, and in fact you are encouraged to call
remove-evens! as a helper function. But there is a rather
significant complication.
Question: What restriction must we place on the input list to
remove-odds!? Why?
- All-encompassing example
- Sorted List
We want to encapsulate a list of numbers sorted in ascending order,
and a few operations on that list. The underlying representation could be
a binary tree, but we will just use normal Scheme lists for simplicity.
We want to implement the following operations on sorted lists:
insert: num →
Inserts the given number into the list in the correct position
remove: num → true/false
Removes the first occurance of the given number from the list, returning
false if and only if the number was not found in the list.
contains: num → true/false
Checks if the given number is in the list, and returns false if and only if
it is not.
size: → num
Returns the number of elements in the list.
Write a service manager-based implementation of a sorted list as
described above, with the four given operations. Your implementation should
use destructive list processing to avoid creating new cons cells
whenever possible (it is not always avoidable).
|