This assignment is to be completed with the same partner as PS9.
Assignment goals:
Be sure to do Part I in a separate file from Parts II and III, as Part I must be submitted separately.
Edit your game from PS8 according to your grader’s comments. Be sure to fix any and all problems that your grader has discovered, and add tests to detect those problems to your test suite.
If your PS8 was perfect or nearly so, there is nothing to do for this problem; this problem does not count toward your Problem Set 1 grade. If it wasn’t perfect, fixing your game will allow you to recover up to 80% of the points lost on your PS8 grade.
Edit your game from PS8 to take advantage of list
abstractions such as map
, filter
,
foldr
, and build-list
.
Find at least two appropriate places to replace
hand-written recursion with one of the
list abstractions in Figure 57, using local
if necessary.
Here is a data definition for a non-empty list:
;; A [NELof X] is one of: ;; -- (cons X empty) ;; -- (cons X [NELof X])
What is the template for processing a [NELof X]
?
Following the four template questions, we know that it must have
a cond
with two branches, but what should we use for
the cond
clause tests? Supposing that the argument
is called a-nelox
, (empty? a-nelox)
will be false
in both cases and
(cons? a-nelox)
will be true
in both, so that doesn’t help. However, since both cases of
the data definition are cons
es, we can safely use
first
and rest
on them. So, we can
check (empty? (rest a-nelox))
or
(cons? (rest a-nelox))
to distinguish the
two cases.
Abstract the following two functions into a single function,
f-est-num
:
;; least : [NELof Number] -> Number ;; To determine the smallest number in nelon (define (least nelon) (cond [(empty? (rest nelon)) (first nelon)] [else (if (< (first nelon) (least (rest nelon))) (first nelon) (least (rest nelon)))])) ;; greatest : [NELof Number] -> Number ;; To determine the largest number in nelon (define (greatest nelon) (cond [(empty? (rest nelon)) (first nelon)] [else (if (> (first nelon) (greatest (rest nelon))) (first nelon) (greatest (rest nelon)))]))
Redefine least
and greatest
in terms
of the abstracted function f-est-num
. (If
you’ve pasted the original definitions into your file,
you will have to comment out the original definitions
in order to redefine them.)
Test them with these lists:
(list 5 4 18 11 6)
(list 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1)
(list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22)
Why are greatest
and least
slow on the long lists?
You can make both greatest
and least
faster by modifying f-est-num
. Use
local
to give a name to the result of the
recursive call.
Test greatest
and least
again with the same inputs—both functions should
now run quickly in all three cases.
HTDP, Exercise 21.2.1
There is no reason that f-est-num
needs to be
limited to non-empty lists of numbers. We might want to find
the longest string in a [NELof String]
or the
image with the least area in a [NELof Image]
.
(Don’t worry about ties.)
Design a function f-est
,
a generalization of f-est-num
, that works
for a [NELof X]
for any class of data
X
. Be sure to write a correct general
contract and purpose.
Make sure that you can define functions
longest-string
and smallest-image
,
as described above, in terms of f-est
.
Extend the data definition of
Problem Set 9, Part I
so that we can represent the application of a user-defined
function of one parameter to an expression, for example
(f (- 5 1))
or (* 3 (g 2))
.
The application expression should be represented as a structure
with two fields. The first field contains the name of the function, the
second one the representation of the argument expression.
A full-fledged evaluator can also deal with function definitions. Provide a structure definition and a data definition to represent function definitions. Recall that a function definition has three essential attributes:
This suggests the introduction of a structure with three fields. The first two contain strings, the last a representation of the function’s body, which is an expression.
Translate the following definitions into your representation:
(define (g x) (- 3 x))
(define (h x) (* 3 x))
(define (i u) (g (* 2 u)))
(define (j v) (- (* v v) (* v v)))
(define (k w) (* (h w) (j w)))
Design a function lookup-def
that takes a
function name f
and a list of function
definitions defs
.
If there is a definition for a function named f
defs, it returns that function. If there is no function with
the requested name, it signals an error using
error
.
Part I is to be submitted to a different hand-in server assignemnt than the other two parts. Please submit Part I (your game) to the assignment hw8-redo and Parts II and III (the other problems) to hw10. Follow the electronic homework submissions instructions for each.
Last updated 11 March 2010.