CMSC 22300 Final Exam (in class)
6/8/2012, Ryerson 276

Instructions: This is an "open book" exam, meaning that you can use
your class notes, my lecture notes, and the two course textbooks. Make
your answers as neat, clear, and concise as possible so as to not
annoy the grader (i.e. me)!

--------------------
1. [10] Type checking

   curry :: ((a,b) -> c) -> (a -> b -> c)
   uncurry :: (a -> b -> c) -> ((a,b) -> c)

For the functions f and g defined below, give the type of the
function or explain why the definition does not type check.

   (a) f = curry uncurry
   (b) g = uncurry curry

I've given these in definitions in Haskell.  What would 
be different for SML?


2. [10] What is the type of g at the point where we are about to type
check the body of the let expression in this definition:

  fun f x =
      let fun g (y,z) = (x y, z x)
       in (g(3, (fn u => u 1)), g(2, fn v => hd(v 0)))
      end

You will express the type of G in terms of type unification
variables occurring in the type of x at that point in the typing of
the definition of f.


3. [10] Define an SML function

   revrev : 'a list list -> 'a list list

that maps a list of lists to a reversed list of reversed
elements. E.g.

   revrev [[1,2], [3], [4,5,6]] ==> [[6,5,4], [3], [2,1]]

Give two definitions as "one-liners", not using a direct
recursive definition, but using the built-in list reversal
function rev in conjunction with standard list functionals
fold(l/r) and map.


4. [15] Translate the following Haskell function into SML.

   f :: [Int] -> [Int] -> [(Int,Int)]
   f x y = [(a,2*b) | a <- x, b <- y, a < b-1]


5. [20] Let us represent playing cards using the following datatypes.

data Suit = Club | Diamond | Hearts | Spades
  deriving (Show, Eq, Ord, Enum)

data Rank = R2 | R3 | R4 | R5 | R6 | R7 | R8 | R9 | R10
          | Jack | Queen | King | Ace
  deriving (Show, Eq, Ord, Enum)

data Card = Card Suit Rank
  deriving (Eq, Ord)

where the Enum class allows us to use segment notations like
[Diamond .. Spades].

class (Ord a) => Enum a where
  toEnum         :: Int -> a
  fromEnum       :: a -> Int
  enumFrom       :: a -> [a]            -- [n .. ]
  enumFromThen   :: a -> a -> [a]       -- [n,m .. ]
  enumFromTo     :: a -> a -> [a]       -- [n .. m]
  enumFromThenTo :: a -> a -> a-> [a]   -- [n,p .. m]

Thus the notation [n .. m] is shorthand for (enumFromTo n m).

(a) Write an instance declaration for Card as an instance of class
    Show.

(b) Write a list comprehension that produces a full deck of 52 cards
    (of type [Card]).

(c) Define another list comprehension containing all distinct possible
    pairs of cards and call it "allPairs". Each of 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.
    Hint: Use the fact that Card is an instance of Ord, and generate
    only pairs where the first card is less than the second in the Card
    ordering.

(d) Define a function 

      sameColor :: (Card, Card) -> Bool

    such that sameColor (c1,c2) is true iff c1 and c2 are of the same
    color (black or red).  Use this to define a list of all card
    pairs where the cards are of the same color.


6. [5] [Lazy evaluation]
If the following definitions and expressions are evaluated in Haskell,
what happens (i.e. when does the infinite recursive bomb, f(), "blow up")?
Explain your answer.

  f () = f ()
  x = [f(), 2, 3]
  y = head x
  z = y + 1
  s = show (z + 2)
  length s


7. [15] [Monad Laws]
Prove that the List monad satisfies the three monad laws:

  1. return x >>= f    ==  f x
  2. mv >>= return     ==  mv
  3. (mv >>= f) >>= g  ==  mv >>= (\x -> (f x >>= g))

where the list monad is defined by:

  instance Monad [] where
    xs >>= f = concat (map f xs)
    return x = [x]
    fail s = []


8. [15] Complete the following definition for a functor implementing
insertion sort.

functor ISort(X: ORD)
   : sig type t
	 val sort : t list -> t list
     end where type t = X.t  =
struct
  type t = X.t 

  (* insert : t * t list -> t list
   * assume 2nd argument is in ascending order wrt X.compare *)
  fun insert (x, []) = [x]
    | insert (x, y::ys) = ...

  (* sort : t list -> t list *)
  fun sort xs = ...

end

structure IntOrd = struct type t = int val compare = Int.compare end

structure IntInsertSort = ISort(IntOrd)
val m = IntInsertSort.sort [2,8,5,3,1]

We could go on to implement another functor MSort with the same
interface (parameter and result signatures), but implementing the
merge sort algorithm, giving an alternative way to sort int lists:

structure IntMergeSort = MSort(IntOrd).
val n = IntMergeSort.sort [2,8,5,3,1]

Discuss whether in Haskell we could overload the sort operation using
type classes (class Sort?) so that different instances of the type
class implemented different sorting algorithms, like insertion sort
and merge sort.