Week 12: Notes

the '$' operator
kinds
instance declarations
defining type classes
functors

You can read about these subjects in Learn You a Haskell, chapters 6 and 8.

lecture examples

Here are some types and type classes that we defined in the lecture.

import Data.List

-- A fraction type for rational numbers.

data Frac = Frac Int Int

instance Eq Frac where
  (==) (Frac a b) (Frac c d) = a * d == b * c

instance Show Frac where
  show (Frac a b) = show a ++ "/" ++ show b

instance Ord Frac where
  Frac a b <= Frac c d = a * d <= b * c

-- A generalized fraction type where the numerator and denominator
-- can be of any integral type.

data GFrac t = GFrac t t

instance (Integral t) => Eq (GFrac t) where
  (==) (GFrac a b) (GFrac c d) = a * d == b * c

-- A type class for a set of integers.

class IntSet s where
    empty :: s
    contains :: Int -> s -> Bool
    add :: Int -> s -> s
    remove :: Int -> s -> s

-- A list of integers is an IntSet.

instance IntSet [Int] where
    empty = []
    contains = elem
    add = (:)
    remove = delete

-- A tree of integers is an IntSet.

data IntTree = Nil | Node IntTree Int IntTree
  deriving (Show)

instance IntSet IntTree where
    empty = Nil

    contains x Nil = False
    contains x (Node left y right) = case compare x y of
        EQ -> True
        LT -> contains x left
        GT -> contains y right
    
    add x Nil = Node Nil x Nil
    add x tree@(Node left y right) = case compare x y of
        EQ -> tree
        LT -> Node (add x left) y right
        GT -> Node left y (add x right)

    remove x tree = … 

-- A type class for a set of values of any type.

class Set s where
    empty :: s a
    contains :: Ord a => a -> s a -> Bool
    add :: Ord a => a -> s a -> s a
    remove :: Ord a => a -> s a -> s a

-- A list is a Set.

instance Set [] where
    empty = []
    contains = elem
    add = (:)
    remove = delete

-- A tree is a Set.

data Tree a = Nil | Node (Tree a) a (Tree a)
  deriving (Show)

instance Set Tree where
    empty = Nil
    contains x tree = …
    add x tree = … 
    remove x tree = …