CSC 270
Homework 3
Assigned 25 Sept, due 8 Oct

This assignment is to be done in PLT Scheme. 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, but it doesn't have check-expect built in.

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.

    Functions returning lists

  1. Develop a function count-down which takes in a natural number (a non-negative integer) and returns a list of the natural numbers from it down to 0, in that order. For example,

    (check-expect (count-down 5) (list 5 4 3 2 1 0))

  2. Develop a function suffixes which takes in a list (of strings, numbers, symbols, it doesn't matter) and produces a list of lists: the given list, all but the first element, all but the first two elements, and so on. For example,

    (check-expect (suffixes '(a b c)) '((a b c) (b c) (c) ()))

  3. Using higher-order functions

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

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

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

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

  8. Extra credit: 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.

  9. Writing higher-order functions; lambda

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

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

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

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

  14. 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 does (iterate 3 sqr) do? What about (iterate 3 (iterate 3 sqr))? What about (iterate 3 do-twice)?

  15. Mutation, I/O, and sequence

  16. 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 can't use symbol=? to compare it with 'quit. Look up the function eqv? in the Help Desk; it does an equality test on any type of objects.

  17. 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. Think about local....

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

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


  20. Last modified: 
    Stephen Bloch / bloch@adelphi.edu