home—lectures—exams—hws—breeze (snow day)
hw05
higher-order functions; tail recursion; reading about grammars
Due: Fri 23:59, for the MWF class.
Bring hardcopy either Friday or Monday.
All functions should have at least two check-expects.
-
Write my-filter, which takes in a list of numbers and
a function of type number → boolean,
and returns a list of numbers.
(Some test cases are provided for you;
do include a signature for my-function;
this includes giving the input/output types of the function it takes in.)
(check-expect (my-filter even? (list 3 9 8 -2 1 0 1 0))
(list 8 -2 0 0))
(check-expect (my-filter negative? (list 3 9 8 -2 1 0 1 0))
(list -2))
(check-expect (my-filter (lambda (n) (or (negative? n) (zero? n))) (list 3 9 8 -2 1 0 1 0))
(list -2 0 0))
|
[If your function returns the numbers in the reverse order from above,
and you have a good reason for that, then that's okay if you can justify it.]
Write this using only cond, if, cons
— not using the built-in filter !-)
-
Write a function which takes in a list of real numbers and two real numbers a,b,
and returns all elements in the list which are in the half-open interval [a,b)
(that is, numbers x in the range a ≤ x < b).
Your function should call my-filter1, and use lambda.
Hint: although this function takes in three inputs,
it will pass a different function to my-filter;
how many arguments does that function have?
-
(0pts) Reading: 3.1, 3.2, 3.3
-
Chpt.3: Review Question #1 [define syntax, semantics];
- Problem Set #11 [which strings are derived from a grammar].
For the strings that are derivable, give a left-most derivation (using “→” as in the book).
-
Deriving lists, with a grammar:
Suppose we had the following grammar rule for a javascript function,
“JsFunc”:
JsFunc → function JsIdent( JsIdents ) {
JsBody
}
|
-
Define rule(s) for the nonterminal JsBody,
which can be 0 or more statements.
Presume that you already have rules for a nonterminal
“JsStmt”
(an individual statement; note that statements already
include semicolons, so your rules shouldn't add any additional ones).
-
Define rule(s) rules for the nonterminal JsIdents2
which is 0 or more comma-separated identifiers.
Presume that you already have rules for a nonterminal
“JsIdent” (an single identifier).
You may need to include a second “helper” nonterminal.
-
Once you have your grammar,
give a leftmost derivation of
x, y, z from JsIdents.
Give your grammar rules only using nonterminals, terminals3, and →,
but no list-shorthand like * or ….
- Chpt.3, #5 [write a BNF for boolean expressions in Java]
For this problem, assume that you already have grammar rules for
Java numeric expressions
(“NumExpr”, probably similar to the book's Fig. 3.4),
and that the only operators you want to handle are
&&,||,!,==
and the numeric predicates >, >=, and ==.
(You do not need to worry about making a grammar that
enforces precedence, although you are welcome to.)
-
Write count-bigs-v2,
which is like count-bigs:
-
Write it in Java,
using a while-loop,
and updating an accumulator (“so-far”) variable,
and updating the list by using java.util.List#subList.
(Similar to sum_v2 in the class notes.)
-
Write it as a tail-recursive function in racket
(similar to sum-v2 in the class notes.)
Between the two versions, use the same name for any variables/functions
that correspond, up to idiomatic spelling
(e.g. in the notes' sum_v2, the Java variable sumSoFar corresponded
to the Racket variable sum-so-far).
-
Write reverse4,
in two versions in Racket:
-
reverse-v1,
which follows the usual
design recipe.
You'll need to create a helper-function to do this.
(That helper function will itself follow the design recipe, of course!)
(Do not use the built-in function append.)
-
as a tail-recursive function.
(Call this version reverse-v2 or such.)
-
Time5 these two versions on some long lists and explain the timing results.
(Remember the function nums-from from lecture.)
1
If you can't complete my-filter, you can instead call the built-in filter.
↩
2
In the reading, §3.3.1.4 gives a grammar for ident_list,
which generates lists of comma-separated terminals.
However, that nonterminal doesn't generate a list of zero terminals.
↩
3
You can represent the empty-string by “ε”, or just by nothing at all: “”.
↩
4Not that it matters,
but this is the book's Chpt.15, programming exercse #11. ↩
5time ↩
home—lectures—exams—hws—breeze (snow day)
radford.edu