CS 5010: Problem Set 6
Out: Monday, October 17, 2016
Due: Monday, October 24, 2016
at 600pm local time.
The goal of this problem set is to help you design and use
multiply-recursive and mutually-recursive data definitions, and to
give you practice using the list abstractions and higher-order functions.
Remember that you must follow the design recipe.
You must use DrScheme's HtDP Intermediate Student Language with
As usual, the rubric for grading is here. Remember that you must follow the design recipe. Your deliverables include the data
definitions (including interpretation and templates), contract and
purpose header, halting measure (when needed), strategy, code, and tests. Be sure to sync your work and fill
out a Work Session Report at the end of every work session. Use the
Work Session Report for
You must also turn in a call graph for your program. As in the
preceding problem set, this consists of a diagram showing which
functions call which, so we (and you) can see the overall structure of
your program. You may draw the diagram using a tool or by hand. Turn
this in as a text file, pdf, jpg, or Racket file. Call your file
call-tree with an appropriate suffix, and bring a paper
copy to your codewalk.
You must include a halting measure for every function that calls
itself either directly or indirectly. Be prepared to explain how your
halting measure decreases around every cycle in the call graph for
For all universe programs, you may assume
that the mouse is never dragged or moved outside of the canvas. Once
the mouse enters the canvas, if the mouse ever leaves the canvas, then
the behavior of your system is unspecified.
In this problem, you will design and implement a system for a
graphical interface for trees. Your system will allow you to create
and manipulate trees on a canvas. Create a file called "q1.rkt"
with the following properties:
- The canvas starts empty. Its size is 500 pixels wide by 400
- Nodes of the tree are rendered either as circles or
squares of a fixed size. The circles should be of radius 20, and
the squares should appear the same size as the circles. your
system should allow you to change the size of the nodes for
the next run by changing a single line of your code.
- Unselected nodes should be rendered in outline mode; selected
nodes should be rendered in solid mode.
- When the tree is displayed, there should be a straight blue
line from the center of a node to the center of each of its
- You can select a node by clicking anwyhere inside it.
Selected nodes are displayed as green solid circles. Clicking on a
node selects only the node, not any of its subtrees. If the mouse
is clicked in the overlap of two or more nodes, all the nodes are
selected, even if one node is a son or descendant of the
- Dragging a selected node causes the entire tree rooted at
that node to be dragged, using smooth dragging. The relative
positions of all the nodes in the subtree should stay the same.
It is ok if this action causes some nodes to be moved off the edge
of the canvas; if the node is moved again so that they are now
back on the canvas, they should reappear in the proper place.
- Hitting "c" when a node is selected adds a new son to the
selected node. The new node should be a circle whose center has
an x-coordinate that is 3 radii to the left of the center of the
currently leftmost son, and a y-coordinate that is 3 radii down
from the center of the parent. If the node has no sons, then
hitting "c" should create the node's first son, appearing 3 radii
down and directly beneath the node.
- Hitting "c" when no node is selected creates a new root node
that is a circle. The new node should appear in the center
of the top of the canvas. The root appears tangent to the top of
the canvas and initially has no sons.
- Hitting "s" at any time should behave like "c", except that
the new node created is a square instead of a circle.
- Hitting "d" when a node is selected deletes the selected
node. When a node is deleted, its sons become the
sons of the parent of the deleted node. If the deleted node is a
root node (and therefore has no parent), then its sons become root
nodes. See the video for examples.
Here's a demo.
Your solution should provide the following functions:
initial-world : Any -> World
GIVEN: any value
RETURNS: an initial world. The given value is ignored.
run : Any -> World
GIVEN: any value
EFFECT: runs a copy of an initial world
RETURNS: the final state of the world. The given value is ignored.
world-after-mouse-event : World Integer Integer MouseEvent -> World
GIVEN: a World, a location, and a MouseEvent
RETURNS: the state of the world as it should be following the given mouse event at that location.
world-after-key-event : World KeyEvent -> World
GIVEN: a World and a key event
RETURNS: the state of the world as it should be following the given key event
world-to-trees : World -> ListOfTree
GIVEN: a World
RETURNS: a list of all the trees in the given world.
tree-to-root : Tree -> Node
GIVEN: a tree
RETURNS: the node at the root of the tree
EXAMPLE: Consider the tree represented as follows:
| | | |
B C D E
| | | |
F G H I
If tree-to-root is given the subtree rooted at C, it should return the
data structure associated with node C. This data structure may or may
not include data associated with rest of the tree, depending on
whether you have chosen to represent nodes differently from trees.
tree-to-sons : Tree -> ListOfTree
GIVEN: a tree
RETURNS: the data associated with the immediate subtrees of the given
EXAMPLE: In the situation above, if tree-to-sons is given the subtree
rooted at C, it should return a list consisting of the subtree rooted
at F and the subtree rooted at G.
[Note how these examples are expressed. They are not just tests, but
are constructed to illuminate possible ambiguities or
misunderstandings in the purpose statement. This is what a good
node-to-center : Node -> Posn
RETURNS: the center of the given node as it is to be displayed on the
Note: this function returns a Posn (an ISL builtin). This is for the
convenience of the testing framework, and you may or may not wish to
represent the center of the node in this way.
node-to-selected? : Node -> Boolean
RETURNS: true iff the given node is selected.
- You will find this problem much easier if you follow the slogan
"The Structure of the Program Follows the Structure of the Data"
If you write good data definitions, and follow the templates, you
will be led to a good solution. If you stray from the templates,
you will create a mess.
- Use the System Design Recipe: get a small subset of your system
working first, and then add the other required features, one at a time.
- The specifications talk about Tree and Node, because some
students may wish to implement these as different data definitions.
If you wish to represent Trees and Nodes as the SAME data structure,
that is also permissible.
- The built-in abstraction functions, like map, foldr, and filter,
are your friends. Use them wherever it is feasible to do so. As
before, you may want to write your functions using explicit
recursions, and then rewrite them using the abstractions and
higher-order function combination. You will be penalized for
recursions in your code that "obviously" could have been replaced by
one of the mapping functions. [Meta-Hint: there are a few recursions in
the solution that cannot obviously be replaced by mapping
functions. Figuring out which these are is your problem!]
- It is likely that you will find a lot of code that is duplicated
or almost-duplicated for squares and circles. The best solutions
will cut down this duplication by applying Generalization as
described in Module 5.
- Most likely you will want to use scene+line from the image
library rather than add-line, since the latter changes the
dimensions of the image in surprising ways.
Last modified: Thu Oct 20 11:07:28 Eastern Daylight Time 2016