CSE 1729 – Introduction to Principles of Programming October 23, 2016 Problem Set 6
1.
There are a number of equality functions in Scheme: =, eq?, eqv?, equal? for example, but none of them “do it all” that is, work for symbols, numbers, and lists. For example, none of these will say #t when comparing ’(a b c (1 2) 3.0) and ’(a b c (1 2) 3), although (= 3 3.0) is true,and(equal? ’(a b c (1 2) 3.0) ’(a b c (1 2) 3.0)istrue.
Write a Scheme function (better-equal? a b) that works for symbols, numbers, and lists using the following definition:
2.
(a) For lab you wrote a (remove-all x lst) function that removed anything in lst that was equal to x. For this problem, write the scheme function (remove-if f lst) that returns the list with all elements for which (f x) is true removed.
(b) Your remove-all function that did not remove any nested elements. Now define a function nested-remove that will remove items from nested lists as well. To add to the challenge, you should also be able to remove lists from lists, using better-equal? as your equality test. You should remove all of the items in the list that are equal to the thing to be removed. For example,
>(nested-remove ’(a b) ’(1 2 (a b))) (1 2)
>(nested-remove ’b ’(1 2 (a b)))
(1 2 (a))
(better-equal? a b) =
#t if a and b are symbols and (eq? a b),
#t if a and b are numbers and (= a b),
#t if a and b are lists whose corresponding members are better-equal?, #f otherwise
3. More fun with sets Using an unordered list to represent sets (as in lab, and in Section 2.3.3 in the textbook), implement the following set functions. Feel free to define appropriate helper functions.
(a) (superset? a b) Returns #t if set a is a superset of set b, that is, every element of set b is a member of set a; #f otherwise.
(b) (set-difference a b) Returns the set-difference between set a and set b. This difference, denoted a − b, is defined as
a − b = {x : (x ∈ a ∧ x ̸∈ b)}
1
4.
(c) (cross-product a b) Returns the set of tuples (x,y) such that x is in a and y is in b. Use two-element lists for tuples. This is denoted a × b, and is defined as
a × b = {(x, y) : x ∈ a ∧ y ∈ b}
Define a Scheme function, (nestless x), that takes a list and returns a list with the same
elements but no nesting. For example:
>(nestless ’((a b) c (d e (f g)))) (a b c d e f g)
>(nestless ’(a b))
(a b)
>(nestless ’()) ()
5. (a)
6.
Define a Scheme function (partition lst pivot) that takes as parameters lst, a list of numbers, and pivot, a number. It evaluates to a list of three lists, containing 1) the items in the list less than pivot, 2) the items in the list equal to pivot, and 3) the items in the list greater than pivot. For example:
>(partition ’(1 3 4 2 5 9 11 3 5 8) 5) ((1 3 4 2 3)(5 5)(9 11 8))
is a possible result–there are no guarantees about the order of elements within the lists.
(b) An interesting feature of partition is that if the pivot value is equal to some member of the list, then both the first and last lists in the result are shorter than the original list, which means they are good candidates for recursive calls.
Using partition, define a Scheme function (kth-smallest lst pos) which returns the number that would be in the kth position if the list were sorted in ascending order – (kth-smallest lst 1) returns the smallest element, and so forth. If 2m + 1 is the length of the list, (kth-smallest lst m) would be the median value (as long as m is an integer). How can I do this without sorting the list? Use partition with some element of the list as the pivot. Suppose we are looking for the kth element of the list:
1. If the first list in the partition has at least k elements, then the kth element of the original list is the kth element of the first list.
2. If k is greater than the length of the first list, but less than or equal to the combined length of the first two lists, then the kth smallest is one of the elements of the second list (which are all the same as the pivot).
3. If the combined length of the first two lists is less than k, then the answer is the (k – combined length of first two lists)th element of the third list.
Define a Scheme function, merge, which takes two lists l1 and l2 as arguments. Assuming that each of l1 and l2 are sorted lists of integers (in increasing order, say), merge must return the sorted list containing all elements of l1 and l2.
To carry out the merge, observe that since l1 and l2 are already sorted, it is easy to find the smallest element among all those in l1 and l2: it is simply the smaller of the first elements of
2
l1 and l2. Removing this smallest element from whichever of the two lists it came from, we can recurse on the resulting two lists (which are still sorted), and place this smallest element at the beginning of the result.
7. As as extra challenge: Define a Scheme function (gen-cross l) that takes a list of sets and returns the cross product of all the sets in the list, that is, a set of tuples, each having one element from each set, in order.
This task can be solved, but you need do a good job breaking it down into manageable pieces. No points, but huge glory.
3