If you run any of the functions (as opposed to just testing them), comment out the code for running the functions before you submit your solution.
N.B.: Tests are not runs. A test is when you evaluate an expression and compare it to some expected result, while a run is when you evaluate an expression without anticipating any particular result for the expression.
Due date: 10/28 @ NOON
The purpose of this problem set is to revisit self-referential data
definitions and to understand functions that consume several complex arguments
at once (multiplexing).
You will benefit from local definitions for this problem set though
you can solve all problems without this knowledge.
recursion: 14.1.3, 14.1.5, 14.3.3, 14.4.1, 14.4.2, 14.4.3, 14.4.4
multiplexing: 17.7.1, 17.7.2, 17.7.3, 17.7.4
Additional Problem 1:
Design the function
find-sublist. It consumes two lists of
pat, and determines whether
the latter occurs en-block somewhere in the former.
Additional Problem 2:
A set is a collection of things that are all mutually distinct.
You can represent a set of symbols as a list of symbols such that all
symbols are mutually unequal (symbol=?).
Design the function element-of?, which determines whether a given
element is in a given set.
Design the function add-element, which consumes a symbol and a set
and constructs a new set that includes this symbol.
Design the function remove-element, which removes a given symbol
from a given set. Hint: Is it always true that
for all elements e and sets s?
(boolean=? (element-of? e (remove-element e s)) false)
Design the function union, which creates a set from the elements of
two given sets.
Design the function intersect, which creates a set from the
elements that are common to two given sets.
Additional Problem 3:
[Note: This problem continues problem 2.]
A relation is a set of tuples. For illustrative purposes, we use tuples of
;; A tuple is (list Symbol Symbol).
(define a-tuple '(a b))
;; A relation is a set of tuples.
Design the function domain, which collects all firsts from a given
relation in a set.
Design the function range, which collects all seconds from a given
relation in a set.
Design the function at. It consumes a set Sand a relation
R. Its purpose is to collect all the seconds from all tuples in
R whose first is a member of S.
Design the function x. It consumes two sets and creates a relation
that combines all elements from the first set with all elements from the second
(equal? (x '(a b) '(x y z))
'((a x) (a y) (a z) (b x) (b y) (b z)))
Challenge Problem [no points]:
This data definition describes a tree of symbols:
Design a function that consumes such a tree and produces an image of the
tree. The function should draw each leaf (empty) as a red bullet and
each branch as the combination of two trees via a fork:
(define-struct node (name left right))
;; Tree = empty | (make-node Symbol Tree Tree)
The left and the right tree should sit on top of the left and right branch of
the fork, respectively; both should use the same width. The downward stem
should be centered. Hint: Design functions that help you compose images
vertically and horizontally; both should consume images whose pinhole is at
;; draw-fork : Number String -> Image
;; produce a branching picture like this:
;; | |
;; width: w; left up at 1/4 * w;
;; right up at 3/4 * w;
;; down at 1/2 * w
;; pinhole @ (0,0)
(define (draw-fork w label) ...)