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).
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-b for the
endpoints, and a single predicate function
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.
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.
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)
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-rest!) to avoid creating new
cons cells in our function execution, thus making the program
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).
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?
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,
'((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
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).
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
Question: What restriction must we place on the input list to
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
whenever possible (it is not always avoidable).
Last modified on Wednesday, 09 January 2019, at 14:31 hours.