Homework 3

Assigned Oct 6, due Oct 13

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.Develop 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) 3

**Hint:**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`

.

`local`

and `lambda`

Last modified: Wed Oct 5 21:46:42 EDT 2011 Stephen Bloch / sbloch@adelphi.edu