CS 5010: Problem Set 5
Out: Monday, October 13, 2014
Due: Monday, October 20, 2014
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 HOFC.
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. You should also
refer to the more detailed guidelines here.
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 "trees.rkt"
with the following properties:
- The canvas starts empty. Its size is 400 by 400.
- Nodes of the tree are rendered as green outline squares of a
fixed size. The default value for the size (length of the side) is
20, but your system should allow you to change the size for the next
run by changing a single line of your code. You can select a node by
clicking on it, as in previous problems. Selected nodes are
displayed as green solid squares. Clicking on a node selects only
the node, not its sons subtree. 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 other.
- 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 sons.
- When a node is selected, there should be a vertical line
displayed at the position where the left edge of a
new son would be if it were created. (See the "n" command, below).
3 square-lengths to the left of that node's leftmost son.
This delimits the area in which new sons may be created. (See the
"n" command, below). If the selected node has no sons, no line
should be displayed
- Dragging a selected node causes the entire tree rooted at that
node to be dragged. 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.
- When you drag a node, the rectangle should
become centered on the mouse position. (That is, we are not doing
"smooth dragging" in this problem.
- Hitting "t" at any time creates a new root node 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 "n" while a node is selected adds a new son, whose
center has an x-coordinate two square-lengths to the left of the
center of the currently leftmost son, and a y-coordinate 3
square-lengths down from the center of the parent. If a selected
node ever moves into a position so that there is no room for the
son, it should appear as red solid rather than green, and "n" has no
effect. The first son of a node should appear 3 square-lengths down
and directly beneath the node. There is room for a
new son if it would be placed with the whole square entirely within
the canvas. Note that a node should turn red at the same instant
that its vertical line disappears off the left edge of the screen.
- Hitting "d" while a node is selected deletes the node and its
- Hitting "u" (whether a node is selected or not) deletes every
node whose center is in the upper half of
the canvas. (If a node is deleted, all of its children are also
Here's a small demo. It doesn't demonstrate "u", though, nor
does it demonstrate having multiple roots on the screen, sorry.
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 Number Number 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-roots : World -> ListOf<Node>
GIVEN: a World
RETURNS: a list of all the root nodes in the given world.
node-to-center : Node -> Posn
RETURNS: the center of the given node as it is to be displayed on the scene.
node-to-sons : Node -> ListOf<Node>
node-to-selected? : Node -> Boolean
These functions have the purpose statements suggested by their
Before you turn in your solution, make sure it passes the tests
in ps05-qualification.rkt. As before,
download this file, save it in your set05 directory, and run it to
qualify your program for grading. Be sure to commit this file to the repository
so we know that you've done this correctly. DO NOT TURN IN YOUR SOLUTION UNLESS IT PASSES
THE QUALIFICATION TEST! IF YOUR SOLUTION DOES NOT PASS THE
QUALIFICATION TEST, WE MAY NOT GRADE IT.
Please download a fresh copy of
this problem set. The new version should print out a header showing
a version date. For this problem, be sure the version you have is
dated later than Wed Oct 15 13:00:00 2014. When you run your
qualification test, if you get a message
like "undefined function check-location", it means that
your version of extras.rkt is too old and you need to download the
- Follow the design recipe!! 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. If you are following your templates and still creating a
mess, try an alternate path. For example, if you are doing
structural decomposition on one data type, followed immediately by
structural decomposition on another data type, try doing them in the
- 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 HOFC.
- 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.
- My solution to this problem was about 320 lines, plus tests. Median
time on task for this problem for the last two semesters has been
right around 20 hours.
Last modified: Sat Oct 18 09:55:23 Eastern Daylight Time 2014