 Due date: 10/07
Purpose:
The goal of this problem set is to help you design functions that deal with
arbitrarily large data, especially trees, forests of trees and trees of
forests, and forests of forests.
Drill:
HtDP: 14.1.4, 14.1.6, 14.2.1, 14.2.2, 14.2.3, 14.2.4, 17.6.4, 17.6.6,
17.7.1, 17.7.2, 17.7.3, 17.7.4
Required Problems:
Note: You must use DrScheme's HtDP Intermediate Student
Language.

Economists use "choice trees" to record how decisions are made in
socalled binary situations:
(definestruct choice (left right))
;; An ChoiceTree is one of:
;;  Number
;;  (makechoice ChoiceTree ChoiceTree)
The weight of a ChoiceTree is the sum of its numbers.
For the analysis of ChoiceTree s we need two functions:
balanced? , which determines whether a
ChoiceTree is balanced.
Definition: A balanced choice tree contains only instances of
choice structures whose two subtrees have the same weight.
decide , which consumes an ChoiceTree and a list of
Directions s to find a final decisiona leafin the
tree.
Definition: A Direction is one of:
"left" or "right" .
Naturally, decide works just like a person who is given a
list of directions in a city. When, however, the function exhausts the
list and hasn't discovered a leaf yet, it signals an error. Similarly,
it is also an error if the function reaches a leaf and there are some
directions left.
 Design the function
sumF , which adds up all the numbers
that occur in a forest. Here are the relevant data definitions:
;; A Forest is one of:
;;  empty
;;  (cons Tree Forest)
;; A Tree is one of:
;;  Number
;;  (cons Forest (cons Number (cons Forest empty)))
 Design a program that renders an
Expr as an image:
(definestruct pls (x in?))
(definestruct mul (x in?))
;; Expr is one of:
;;  Number
;;  (makepls (cons Expr 1LON) Boolean)
;;  (makemul (cons Expr 1LON) Boolean)
;; 1LON is one of:
;;  (cons Expr empty)
;;  (cons Expr 1LON)
;; interp. a pls struct represents an addition expression
;; with at least two subexpressions; a mul represents a
;; multiplication; the boolean flag indicates whether it
;; represents an infix or a prefix expression.
The rendering program consumes an Expr and produces an image.
It ignores the boolean flags and instead renders all expressions as prefix
expressions.
Here are two examples:
(makepls (list 1 3 2) true)


(makemul (list (makepls (list 1 3 2) true)
(makemul (list 1 3 2) true))
false)


Hint: This problem is related to problems 1.3 and 2.3.
Domain knowledge:
The rendering places only the first subexpression of an addition or
multiplication on the same line as the operator. All others are
on separate lines below the first line, always indented by five pixels 
relative to the beginning of the innermost
subexpression.
The closing parentheses of an expression appears on its last line.
 Mini Project:
Design a Space Invader program.
The player is in control of a ``tank'' (render as
a small rectangle) that
must defend earth (the bottom of the canvas) from a UFO (``flying
saucer'') that descends from the top of the canvas to the bottom. In order
to stop the UFO from landing, the player may fire missiles (triangles,
smaller than the ``tank'')  as many as desired. To fire a missile, the player hits the space
bar and, in response, a missile emerges from the tank. If the UFO
collides with any of the fired missile, the
player wins; otherwise the UFO lands and
the player and ``earth'' is lost.
Here are some details concerning the movement of the three game
objects. First, the tank moves a constant velocity along the bottom of the
canvas. The player may use the left arrow key and the right arrow key to
change directions. Second, the UFO descends at a constant speed but makes
small random jumps to the left or rightwithout ever disappearing from
the canvas. Third, once fired a missile ascends along a straight vertical
line at a constant speed at least twice as fast as the UFO
descends. Finally, the UFO and the missile ``collide'' if their reference
points are close enoughfor whatever you think ``close enough'' should
mean.
BSL and ISL come with the function
;; random : NaturalNumber > NaturalNumber
;; (random n) produces a number in [0,n)
(define (random n)
;; magic happens here
...)
Use this function to move the UFO randomly, but remember to always keep
the UFO inside the canvas's boundaries.  To test functions that employ
random , create a main function that calls an auxiliary
function. The auxiliary function should not use
random and should perform all computations. Instead the main
function should call the auxiliary function on random numbers.
That way you can still test the auxiliary function where all the real
computation happens.

