This assignment is to be done in PLT Scheme/Racket. None of these exercises
requires define-type, so you can use HtDP languages if you
wish: most of them can be done in "Intermediate Student with
Lambda" language, but the last four exercises will require "Advanced
Student". Or you can do them all in "PLAI" language if
you prefer, using test et al instead of
check-expect et al.
You are encouraged to do this in teams of two, both students working together on each function; if you do this, turn in one homework with both names on it.
For all functions, follow the design recipe: each function must have a contract, a good collection of test cases, and a function definition.
In order to get your homeworks graded quickly, I won't actually grade every one of these problems, but rather a sample including problems of various levels of difficulty. The rest are practice. If there's one that you want to make sure I look at, call my attention to it when you turn in the homework.
Within each heading, the problems are arranged more or less in increasing order of difficulty. If one of them really stumps you, try going on to a different heading, and then come back to this problem.
See Dr. Krishnamurthi's tutorial exercises on higher-order functions (and their solutions). Note that when the tutorial refers to "exercises 11-15", it's referring to these (and their solutions).
Since the solutions to these are posted on the Web, I sha'n't grade them, but they're good exercises to see how well you understand higher-order functions.
Rewrite the substitute function of homework 2 using filter,
map, or foldr.
Rewrite the winner function of homework 2 using filter,
map, or foldr.
Develop a function subsets which takes in a list
(of strings, numbers, symbols, it doesn't matter) and produces a list
of lists: all the possible subsets of the given list (with the
elements in the same order they were in the given list). You may
assume that the given list has no duplicate elements.
For example,
(check-expect (subsets '(a b c)) '((a b c) (a b) (a c) (a) (b c) (b) (c) ()))Hint: You don't have to use higher-order functions for this, but it might help.
Develop a function
scramble which takes in a list (of strings, numbers,
symbols, it doesn't matter) and produces a list of those same items in
all possible orders. You may assume that the given list has no
duplicate elements. For example,
(check-expect (scramble '(a b c)) '((a b c) (b a c) (b c a) (a c b) (c a b) (c b a)))Hint: You don't have to use higher-order functions for this, but it might help.
local and lambdaDevelop a function count-if which counts how many
elements of a list meet a particular criterion (which is provided as a
parameter).
Use count-if to develop a function
count-evens which takes in a list of numbers and tells
how many of them are even.
Use count-if to develop a function
count-multiples which takes in an integer and a list of
integers and tells how many of the list elements are multiples of the
integer.
Develop a function do-twice which takes in a
function with contract "X -> X" and returns a function with the same
contract which applies the given function twice. In other words,
((do-twice f) x) = (f (f x)). For example,
(define add2 (do-twice add1)) (check-expect (add2 3) 5)What does
(do-twice sqr) do?
Generalize do-twice
to a function iterate that takes in a natural number and
a function with contract "X -> X", and returns a function with the
same contract which applies the given function that number of times.
In other words, ((iterate 5 f) x) = (f (f (f (f (f x))))).
What should (iterate 3 sqr) do? What about
(iterate 3 (iterate 3 sqr))?
What about (iterate 3 do-twice)?
Develop a function named ask-list
which takes in a string (the "prompt") and returns a list of objects
constructed from user input. It should display the prompt, wait for
user input, and use the result as the first element of the list, then
display the prompt again, wait for user input, and use the result as the
second element of the list, and so on. When the user types the symbol
quit, it should stop; the quit should
not appear in the
resulting list. Example:
> (ask-list "Next item? ") Next item? 7 Next item? hello Next item? "this is a string" Next item? quit (list 7 hello "this is a string")Hint: Since you don't know what kind of thing the user typed in (number, string, symbol, etc.), you'll need to compare it with
'quit by using
eqv? or equal?, which do an
equality test on any types of objects.
Develop a function named next that
takes no arguments, but each time you call it, it returns how many
times it has been called. Example:
> (next) 1 > (next) 2 > (next) 3Hint: You can do this with a global variable, but it would be "neater" if you could hide the variable so nobody else can change it. Think about
local....
Develop a function named
next-color
that takes no arguments, but each time you call it, it returns the next
element in the list (list "red" "orange" "yellow" "green" "blue"
"violet"). If you call it more than six times, it returns
false.
Hint: same as for next.
Develop a function named
make-lister that takes in a list, and returns a function
like next-color: it takes no arguments, but each time you
call it, it returns the next element in the list that was given to
make-lister. If you run out of list elements, it returns
false. It should be possible to have several lists going
at once:
> (define next-bird (make-lister '("robin" "bluejay" "crow")))
> (define next-class (make-lister '("cs 270" "cs 271" "math 243")))
> (next-bird)
"robin"
> (next-class)
"cs 270"
> (next-class)
"cs 271"
> (next-bird)
"bluejay"
> (next-bird)
"crow"
> (next-bird)
false
> (next-class)
"math 243"
Hint: You can't do this one with a global
variable, so figure out how to do without a global variable in the
previous problems first.
Develop a function named
make-cyclic-lister that takes in a list, and returns a function
like next-color. The difference is that when this one gets to
the end of the list, it starts over from the beginning rather than returning
false.