Week 12: Notes

These notes include some of the types and functions we discussed in the lecture.

fractions

Here is a Haskell datatype for representing rational numbers:

data Frac = Frac Int Int   -- numerator, denominator

instance Eq Frac where
  (Frac num1 denom1) == (Frac num2 denom2) =
    num1 * denom2 == num2 * denom1

instance Ord Frac where
  compare (Frac num1 denom1) (Frac num2 denom2) =
    compare (num1 * denom2) (num2 * denom1)

instance Show Frac where
  show (Frac num denom) = (show num) ++ "/" ++ (show denom)

generalized fractions

We can generalize our fraction type so that it can use an arbitrary type (e.g. Integer) in the numerator and denominator. With this generalized type, we must add class constraints to our instance declarations:

data GFrac t = GFrac t t   -- numerator, denominator

instance (Eq t, Num t) => Eq (GFrac t) where
  (GFrac num1 denom1) == (GFrac num2 denom2) =
    num1 * denom2 == num2 * denom1

instance (Ord t, Num t) => Ord (GFrac t) where
  compare (GFrac num1 denom1) (GFrac num2 denom2) =
    compare (num1 * denom2) (num2 * denom1)

instance (Show t) => Show (GFrac t) where
  show (GFrac num denom) = (show num) ++ "/" ++ (show denom)

integer queues

Here is a type class representing a functional queue of integers:

class IntQueue q where
  isEmpty :: q -> Bool
  enqueue :: Int -> q -> q
  dequeue :: q -> (Int, q)

Here's a datatype that implements a queue using a list of integers.

newtype LIQueue = LIQueue [Int]

instance IntQueue LIQueue where
  isEmpty (LIQueue q) = null q
  enqueue i (LIQueue q) = LIQueue (q ++ [i])
  dequeue (LIQueue (x : xs)) = (x, LIQueue xs)

Of course this is inefficient: adding N elements to a queue can take O(N²). At the end of the lecture, we sketched how to implement a more efficient functional queue using a pair of lists. We will implement this idea in the Thursday tutorial.