CSE 505, Autumn 1996

D. Notkin

Homework #2
Assigned: 10/4/96

Due: 10/11/96

This assignment is intended to get everybody writing some fairly basic programs in the functional paradigm and thinking about the issues in this paradigm. The programming will be in ML (several of the problems are due in large part to Gary Leavens); we'll send information to the mailing list about where to find the compiler, etc. For all functions you write, use auxiliary functions if you want. You may work in pairs, turning in a single assignment with both names, receiving a single, shared grade. Assignments are due (preferably electronically) by the beginning of class on the due date; just email them to the TA in some reasonable format, or drop them off in the TA's mailbox (for non-electronic submissions or parts thereof). This assignment is worth 10% of the quarter's assignments (which in turn are worth 50% of the total grade).

  1. (10 points) Write a function tails that returns a list of lists consisting of the list, and its tails. Examples:

    tails [] = []
    tails [1,2,3] = [[1,2,3],[2,3],[3],[]]
  2. (10 points) Write a function deleteSecond that takes an item and a list and returns a list just like the argument list, but with the second occurrence of the item (if any) removed. Examples:

    deleteSecond 1 [1,2,3,2,1,3,2,1] = [1,2,3,2,2,3,2,1]
    deleteSecond 4 [1,2,3,2,1,3,2,1] = [1,2,3,2,1,3,2,1]
    deleteSecond 3 [1,2,3] = [1,2,3]
  3. (10 points) Write a function notRepeating that takes a list and returns a list leaving only the elements that aren't repeating. Examples:

    notRepeating [1,2,3,2,1,3,2,1] = []
    notRepeating [1,2,3,3,2,4] = [4]
    notRepeating [1,2,3,3,4] = [1,2,4]
  4. (10 points) Write a function onlyRepeating that takes a list and returns a list leaving only the elements that do repeat. Examples:

    onlyRepeating [1,2,3,2,1,3,2,1] = [1,2,3]
    onlyRepeating [1,2,3,3,2,4] = [1,2,3]
    onlyRepeating [1,2,3,3,4] = [3]
    onlyRepeating [1,2,3,4,5] = []
  5. (10 points) Write a function countOccur that takes a list and returns a count of the number of repeated occurrences. Examples:

    countOccur [1,2,3,2,1,3,2,1] = [(3,1),(3,2),(3,3)]
    countOccur [3.5,3.5,9.5] = [(3.5,2),(9.5,1)]
  6. (10 points) Write a function composeList that takes a list of functions and returns a function that is their composition. Examples:

    composeList [] [1,2,3] = [1,2,3]
    composeList [tail,tail,tail] [1,2,3,4,5] = [4,5]
    composeList [(fn x=>x+1),(fn x=>x+2)] 4 = 7

    composeList []     is the identity function.

  7. (10 points) Consider the ML functions:

    fun twice f x = f (f x);
    fun succ x = x + 1;

    If you execute

    twice twice twice succ 0

    ML returns the answer 16.

    Give the clearest answer you can about why this answer is returned. This is one of those problems (that for most people) starts out obvious, becomes hard and confusing, and only ends up obvious again after some serious thinking.
  8. (10 points) In Harper's "Introduction to Standard ML", the answer to Exercise 2.5.5 (p. 26) is, "It reverses the elements in a list." The function definition on p. 27 also reverses a list. The following LISP program (written in a pretty standard LISP notation, a bit different from McCarthy's 1960 notation) reverses a list as well:

    (defun reverse (l) (rev nil l))
    (defun rev (out in)
    (cond ((null in) out)
    (t (rev (cons (car in) out) (cdr in))))))

    Compare and contrast these definitions of reverse, covering (at least) efficiency and the use of auxiliary functions and pattern matching.
  9. (10 points) Translate Backus's examples 11.3.1 (factorial) and 11.3.2 (inner product) into ML.
  10. (10 points) Carefully (but precisely) define each of the following terms: