CSC 270 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.

Using higher-order functions

1. 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.

2. Rewrite the substitute function of homework 2 using filter, map, or foldr.

3. Rewrite the winner function of homework 2 using filter, map, or foldr.

4. 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.

5. 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.

6. Writing higher-order functions; local and lambda

7. Develop a function count-if which counts how many elements of a list meet a particular criterion (which is provided as a parameter).

8. Use count-if to develop a function count-evens which takes in a list of numbers and tells how many of them are even.

9. 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.

10. 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,

What does (do-twice sqr) do?

11. 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)?

12. Mutation, I/O, and sequence

13. 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:

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.

14. 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....

15. 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.

16. 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.

17. 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.