CMSC22300
Homework 3
Due Wednesday, April 21, 2010

In all cases you must strenuously resist the urge to google for
Haskell code, ML code, or any other code. Googling to read about
general concepts is permissible.

1. [30] Finger exercises: classic sorting algorithms.

Implement each of the following sorting algorithms in Haskell. Assume
ascending is the desired order of the output.

Your implementations should be clear and concise.

Helper functions may be helpful or necessary.

(a) selection sort

    - in selection sort, you select the minimum* of the list, and
      prepend it to the recursively sorted rest of the list

      * when sorting ascending

(b) quicksort (Hint: list comprehensions.)

(c) mergesort (Hint: take, drop, splitAt.)

These sorts should all have the type
  Ord a => [a] -> [a].

2. [40] Type classes.

Here are datatypes for rational numbers and complex numbers.

data Q = Q Integer Integer
  deriving (Show)

data C = C Float Float
  deriving (Show)

Haskell has its own rational and complex number libraries, but for the
purposes of this exercise we will pretend they don't exist.

(a) [10] Instantiate both Q and C to type class Eq by defining (==) for
    each. You will need to declare each instance like so:

      instance Eq Q where
        ... definition of (==) ...

    With respect to rationals, this is perhaps slightly harder than
    you think. Note 1/2 equals 2/4. Note further that (-1)/2 equals
    2/(-4).

(b) [25] Instantiate Q and C to the type class Num. In order to do so,
    you will need to implement the operations specified in the
    following class declaration:

      class (Eq a, Show a) => Num a where
        (+)         :: a -> a -> a
        (-)         :: a -> a -> a
	(*)         :: a -> a -> a
	negate      :: a -> a
  	abs         :: a -> a
  	signum      :: a -> a
  	fromInteger :: Integer -> a

    Notes: 1. The abs of a complex number is its modulus.

           2. signum returns -1 if its argument is negative, 0 if it's
              zero, 1 otherwise. (Note -1, 0, 1 are domain-specific!)
              For rational numbers, the implementation of this
              function is straightforward. It it is not clear what
              this function should do with complex numbers, but you
              must define signum for type C to be treated as a
              Num. Therefore use the following implementation of
              signum for C:

                signum z = error "signum undefined for C"

              This will satisfy the compiler and prevent your programs
              from passing around bogus values applying signum to Cs.

 	   3. It is possible for the user to construct a bogus
              rational value directly, like (Q 1 0). For the time
              being, so be it. When any such zero-denominator value is
              involved in an operation, however, your code should
              raise an error. With proper code factoring, this is not
              too onerous.

(c) [5] The following type class describes aggregations of lists of
    numbers, using addition and multiplication respectively.

      class Agg a where
        lsum  :: [a] -> a
	lprod :: [a] -> a
    
    Instantiate both Q and C to class Agg.

3. [50] Playing cards.

(a) Define datatypes for suits (clubs, diamonds, hearts, spades), ranks
   (two, three, ..., ace), and cards.

(b) Append "deriving (Show)" to your Suit and Rank datatypes, but not
    to Card. Instantiate Card to Show manually with a custom
    definition of show.

(c) Write a list comprehension to generate a deck of cards. Check that
    it contains exactly fifty-two cards.

    Helpful hint: Enum.

(d) Define another list comprehension containing all distinct possible
    pairs of cards and call it "allPairs". All the pairs should
    contain two different cards, and no pair should appear twice (that
    is, exactly one of the pairs (7 of Hearts, 8 of Clubs) and (8 of
    Clubs, 7 of Hearts) should be present in allPairs). Make sure this
    list is of exactly the right length. (What length is that?)

    Hint: Ord.

(e) Someone offers you a bet as follows.

      Let's select a pair of cards from the deck at random. If the
      colors match (two blacks or two reds), I pay you $1. If the
      colors differ, you pay me $1.

    Should you take this bet? Justify your answer using the playing
    card tools you wrote for this problem, and submit your
    calculations.

4. [15] Infinite structures. Define the following:

(a) the infinite list of primes.

(b) the infinite Fibonacci sequence.

(c) the Calkin-Wilf tree. The inductive definition of this tree is
    given in section 1 of "Recounting the rationals" (Calkin and Wilf,
    American Mathematical Monthly, 2000). Google the paper and read at
    least through the tree's definition. (The paper is short and sweet
    and you are invited to read the whole thing.)