Week 10: Notes

kinds
instance declarations
declaring type classes
functors

You can read about these subjects in Learn You a Haskell, chapter 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 = …

recursive value definitions

We've already seen that we can write a function to generate an infinite list of numbers:

intsFrom :: Integer -> [Integer]
intsFrom x = x : intsFrom (x + 1)

For example:

> take 10 (intsFrom 1)
[1,2,3,4,5,6,7,8,9,10]

Alternatively we may produce this list using a recursive value definition. Consider an infinite list of integers starting with 1:

[1, 2, 3, 4, 5, ...]

If we add 1 to each element of the list, we get

[2, 3, 4, 5, …]

which is the same as the tail of the original list. So we may in fact define this list as 1 followed by the result of adding 1 to each element:

ints :: [Integer]
ints = 1 : map (+1) ints