This problem set has two main goals: first, to practice the use of
abstractions; second, to learn how to edit programs that you have already
written, an essential skill for any programmer.
Problem A1:
Part 1:
Complete the following parametric data definition for
a non-empty list:
; an [NEListof X] is one of...
Part 2:
Design the function all-int-squares
which takes in a non-negative integer n and returns a
[NEListof Number] with the squares of all integers from 0 to
n, inclusive (i.e. including both 0 and n).
Part 3:
Write down the parametric data definition for a
UOP (unary operator) which is any function that takes in a
Number and returns a Number. Then abstract all-int-squares
to all-int-results which takes in a non-negative integer
n and a UOP o and returns a [NEListof
Number] with the results of applying o to all integers from
0 to n, inclusive. Redesign your all-int-squares to
use all-int-results.
Part 4:
Design all-int-doubles which uses
all-int-results and a helper UOP, defined with
local inside all-int-doubles, that multiplies
its input by two.
Problem A2:
Part 1:
Write a function find-string that takes
in a [Listof String] and a String and that
reuturns a Boolean, true if and only if the given string was in the
list.
Part 2:
Abstract find-string to
generic-find-string so that the string comparison operation
it uses is a parameter. Then use this abstraction to define
find-string-case-sensitive, which should operate the same
way as the original find-string, and
find-string-case-insensitive, which has the same contract as
find-string but which ignores the case of alphabetic
characters when comparing strings (i.e. the character a is
considered the same as A and so on; non-alphabetic
characters must still match exactly).
Problem A3:
Revise your Missile Defense project. Be sure to fix any and all
problems that your graders have (or would have) discovered. Note: the
ambiguities in the original assignment regarding whether bullets should
explode when they hit missiles and the possible angular paths of missiles
have been corrected in the text of the assignment.
Your revisions should implement the correct functionality.
Next, you are to use local and "loops" (abstractions such
as map, foldr, filter,
etc.) wherever your functions may benefit from them, especially
for the lists of objects in your project.
You should notice that the length of your program decreases
considerably.
If you have a new partner you actually have two different code bases
from which you can start. You are free to pull code from both.
Problem A4:
Part 1:
Develop data definitions for binary trees of Symbols and
binary trees of Numbers. The numbers and symbols should occur at
the leaf positions only.
Create two instances of each, and abstract over the data
definitions.
Design the function height, which consumes any binary
tree of either type and computes its height. That is, the maximum number
of nodes from the root of the given tree to any leaf (including
the leaf, but not including the root node in the count). Here's some
tests to further explain:
(check-expect (height 5) 0)
(check-expect (height (make-node 'yes (make-node 'no 'maybe))) 2)
Part 2:
A leafy binary tree is a binary tree with the symbol
'leaf at its leafs.
Design a function that consumes a natural number n and
creates (a list of) all leafy binary trees of height n.
Hint: Design a function that consumes a natural number n
and creates (a list of) all leafy binary trees of height equal or
less than n.
Note: this is not about
abstraction; it's just a reminder that more interesting (and complex)
programs are around the corner.