CSE 1729 Introduction to Principles of Programming November 27, 2016 Problem Set 9
You have two weeks for this assignment, but the second of those weeks is “Thanksgiving recess” – there will be no help sessions or office hours during that week, and the TAs will likely be too full to answer Piazza questions promptly. I would suggest, therefore, that you get as much of this done as possible before the break.
Practice with SCHEME collection objects
Each of the folllowing tasks is related to collections of data: sets and multisets, plus iterators, an abstract way to systematically access all of the elements of a collection. The other feature of this problem set is that it is object-oriented: the sets, multisets, and iterators all have state and use destructive modification, but the details are isolated from the users by encapsulating the object in a function.
1. Define a SCHEME object—call it basic-set—that maintains an (initially empty) set of symbols. Your object should have methods that correspond to
• empty?, which should return #t if the set is empty, and #f otherwise; • insert, which should insert a new element into the set; and
• delete, which should delete a particular element from the set; and
• element?, which should determine if a given element is in the set.
• cardinality, which should return the number of elements in the set.
Please implement the set as a standard SCHEME list, and return a dispatcher that provides access to
your methods, as we have done in class, via a symbol (quoted name). Thus, your object should behave as follows:
> (define newset (basic-set)) > ((newset ’empty))
#t
> ((newset ’insert) ’bill)
> ((newset ’element?) ’bill) #t
> ((newset ’cardinality))
1
> ((newset ’delete) ’bill) > ((newset ’empty))
#t
2. Define a SCHEME object—call it stat-set—that maintains an (initially empty) set of numbers along with several statistics pertaining to the set. Your object should have methods that correspond to
1
• empty?, which should return #t if the set is empty, and #f otherwise; • insert, which should insert a new element into the set;
• element?, which should determine if a given element is in the set;
• largest, which should return the largest element in the set;
• smallest, which should return the smallest element in the set;
• size, which should return the size of the set; and
• average, which should return the average of the elements in the set.
Note that your set does not need to implement delete. Please implement the set as a standard SCHEME list, and return a dispatcher that provides access to your methods, as we have done in class, via a token. The function stat-set with no arguments should produce an empty stat-set object.
Important amplification. Your stat-set methods that implement largest, smallest, size, and average, should use only a constant amount of computation to determine their return value: specifically, the amount of time they take to return should not depend on the size of the set. (Thus you cannot scan the list to determine its length, or the maximum element of the list.)
How is this possible? One strategy is to set up some “private variables” in your object called, e.g. current-max, current-min, current-length, etc. These variables should maintain, at all times, the current values of these quantities. When a new number is inserted, you will have to up- date your list (that maintains the set) and, in addition, update each of these statistics appropriately.
I think that the easiest way to “maintain” the current average is to actually maintain the current sum of all the elements in the set, and—when the user asks for the average—return the sum divided by the current size.
Incidentally, why didn’t we ask you to implement the delete operation?
3. One thing that neither of the above set objects have is a way to see what is in the set; the set is encapsulated and invisible to the user. In this question you will remedy this by adding a new method get-iterator to the basic-set objects. You should rename these to iterable-set ob- jects, and define a function (iterable-set) that returns an empty iterable sety object. For more information about iterators, see the explanation at the end of this writeup.
(a) First, define an iterator that would work for basic sets, and “install” it in a renamed copy of your basic set definition – that is, add a method get-iterator to basic set that will return an iterator for the data in the set (which is stored as a list). The iterator will be a procedure that is accessed in a similar way to basic set – see example at end of the writeup.
(b) Once you have iterable-sets working, write a SCHEME function intersect-sets that takes two iterable set objects as arguments and returns a new iterable set object that is the intersec- tion of these two sets. This should be fairly straightforward: make a new set for the result, use an iterator to generate all of the elements of one set. For each of these elements, check to see whether it is in the second set, if so add it to the result.
(c) Use your iterator to write a SCHEME function set-difference that takes two iterable set objects as arguments and returns a new iterable set object that is the difference of these two sets, that is, a set containing all of the elements of the first argument that are not elements of the second argument.
2
4. In SCHEME we can implement a dictionary using an association list, or a-list, which is a list of lists such that the car of each of these is called the key, and the cdr of each is the list of values associated with that key. For our purposes here, we assume that keys and associated values are all symbols. The built-in (assq key a-list) function takes a key and an a-list, and returns the list in a-list whose car is equal to the key. If there is no such list, assq returns #f. For example:
Note that the list of values for key1 is the cdr of what assq returns if not false, that is, (sym1 sym2). For correct behavior, all of the keys must be unique, that is, no symbol is the car of more than one element of the a-list.
(a) First, implement an object implementation of dictionary based on an association list. The association list itself will not be accessible, but the object will provide the functions to access and modify the stored information.
Your object should be initialized by calling method dictionary. It will have methods that correspond to the following functions:
• lookup, which takes one parameter (a key), and returns the list of values associated with that key. It should return ’() if that key is not in the dictionary;
• add-value, takes two parameters (a key and a value). If the key is not in the dictionary, it gets added with this value; if it is in the dictionary, the value gets added to the list of key’s associated values. If value is already associated with key in the dictionary, the dictionary should be unchanged.
• remove-value,takestwoparameters(akeyandavalue)andremovesvaluefromthething associated with key. If key is not in the dictionary, or if value is not associated with key, the dictionary should be unchanged. If value is the only thing associated with key, then key should be removed from the dictionary.
• all-keys, which takes no parameters, and returns a list of all of the keys in the dictionary (just the keys, no values).
(b) Once you have implemented and debugged your dictionary object code, write a function (reverse-map dict) that takes a dictionary object dict and returns a new dictionary ob- ject with the mappings reversed, that is, the keys in the result are the symbols from the value lists in dict. For each key k in the result, the corresponding value is the list of keys in dict where k was found in its value list.
About iterators. An iterator is an object that is associated with a collection of data. It provides two functions, has-next? which returns true or false depending on whether there is more data to access, and next which returns some element of the collection. The iterator should behave as follows:
• If has-next? is true, then next will return a member of the collection it is associated with.
• Ifyoukeepcallingnextwhilehas-next?istrue,youwillaccesseveryelementofthecollection exactly once.
3
> (assq ’key1 ’((key1 sym1 sym2)(key2 sym2))) (key1 sym1 sym2)
> (assq ’key3 ’((key1 sym1 sym2)(key2 sym2))) #f
• If you call next when has-next? is false, it should not return a member of the collection. Likely this will cause an error.
• If you change the collection (add or delete elements), existing iterators may not give you correct answers: they may give you elements that were deleted or miss elements that are currently in the collection. Then again, they might reflect the changes in the collection, so the only “safe” way to use iterators is to only use them between changes to the collection.
We will implement iterators like other SCHEME objects, that is, they are procedures that return functions based on their arguments, so
; assume that alph-set is a object representing a set ; containing elements a and b, and has a get-iterator ; function that returns an iterator.
>(define my-iterator ((alph-set ’get-iterator))) >(my-iterator ’has-next?)
#
>(my-iterator ’next) #
a
>((my-iterator ’next))
b
>((my-iterator ’has-next?)) #f
>((my-iterator ’next)) mcar: contract violation expected: mpair?
given: ()
4