CPSC425 Spring 2008
HW 9: More Higher Order Functions

  1. Do Exercises 6 and 7 in Chapter 7 of Webber.

  2. Rewrite your quicksort function from Exercise 7.7 above so that a) it is curried, and b) it takes the function before the list (so you are reversing the order of the parameters). The type of your new function should be ('a * 'a -> bool) -> 'a list -> 'a list. You can either rewrite your old quicksort function making a few small changes, or write a new quicksort function that calls your old one.

  3. Use your curried quicksort function to define the following functions in the same way that sortBackward is defined in section 9.4.
    1. sortBackward: int list -> int list (yes, this is just what is in 9.4). Takes an integer list and returns the list sorted into descending order.
      Example: sortBackward [3,1,4,2] => [4,3,2,1]
    2. sortForward: int list -> int list. Takes an integer list and returns the list sorted into ascending order.
      Example: sortForward [3,1,4,2] => [1,2,3,4]
    3. sortStrings: string list -> string list. Takes a list of strings and returns a list containing the same strings sorted from shortest to longest. If two strings are the same length, they can appear in either order in the result. Note that < applied directly to strings sorts them alphabetically, not by length.
      Example: sortStrings ["abcd", "bb", "ab", "bcd", "b"] => ["b","bb","ab","bcd","abcd"] OR ["b","ab","bb","bcd","abcd"]