CS223 Lecture 17
5/12/2010

Returning to Haskell: More on Type Classes

I. Some facts about type classes.

(1) Only datatypes (and primitive types) can have class instances
    defined: E.g. the following is illegal

    instance Eq (Int -> Int) where
       f == g = f(0) == g(0)

(2) There can only be one instance for a type at a given class.
    E.g. if you want an Int instance of class Ord, you have only
    one chance to define it. So the class Ord does not support having
    more than one way to order a type. 

    Another way of putting this is that the scope of an instance
    declaration is global, and it can't be redefined or overridden.
    This means that method names are also global.

(3) A function name can be used in only one class definition
    E.g. + is used as a function (method?) name in Num, so it can never
    be used in any other Num

(4) constructor classes: a class can be defined for type constructors

(5) Haskell type classes have almost nothing to do with classes
    in object oriented languages, despite the fact that the functions
    associated with a type class are also called "methods".

(6) Type classes don't support "abstract types".

(7) Class definitions can specify default implementations
    of "methods".

    class  Eq a  where
      (==), (/=)            :: a -> a -> Bool
      x /= y                =  not (x == y)    -- default method for /=

------------------------

* How type classes apply to type constructors (e.g. List, Tree)
Classes can be defined for type constructors (e.g. f : Type -> Type).
Instances can be defined for particular constructors of the right
arity.

    class Functor f where
      fmap  :: (a -> b) -> f a -> f b

    instance Functor [] where
      fmap = map

    instance Functor Maybe where
      fmap f Nothing = Nothing
      fmap f (Just x) = Just (f x)

    data Tree a = Leaf a | Branch (Tree a) (Tree a)

    instance Functor Tree where
      fmap f (Leaf x)       = Leaf   (f x)
      fmap f (Branch t1 t2) = Branch (fmap f t1) (fmap f t2)


------------------------

* Class extension: "Inheritance" for type classes

    class  (Eq a) => Ord a  where
      (<), (<=), (>=), (>)  :: a -> a -> Bool
      max, min              :: a -> a -> a

Ord "inherits" the methods of Eq. Ord subsumes Eq.
Ord is called a "superclass" of Eq, Eq a "subclass" of Ord.


* Multiple inheritance:

   class (Eq a, Show a) => C a where ...


* Deriving. When a new data type is defined, Haskell
can automagically (attempt to) define instances for in in certain
basic classes:

    Eq, Ord, Show, Read

Deriving only works for certain "concrete" data types, roughly
corresponding to the native "equality types" of SML (e.g. no
function types involved).

* Multi-parameter type classes

    class Eq e => Collection c e where
	 insert :: c -> e -> c
	 member :: c -> e -> Bool

    instance Eq a => Collection [a] a where
	 insert = flip (:)
	 member = flip elem


    -- alist example as a class
    -- need to set options -XFlexibleInstances -XMultiParamTypeClasses for this to work

    class Eq key => EMap key m where
      empty :: m a
      bind :: key -> a -> m a -> m a
      lookup1 :: key -> m a -> Maybe a

    data Alist k a = Alist [(k,a)]

    instance EMap Int (Alist Int) where
      empty = Alist []
      bind k a (Alist bs) = Alist((k,a):bs)
      lookup1 k (Alist []) = Nothing
      lookup1 k (Alist ((k',v):bs)) = 
	if k == k' then Just v else lookup1 k (Alist bs)


The impact of type constructor classes and multi-parameter classes
on type inference is nontrivial.  The type checking algorithm for
extended Haskell with these features (and a few other advanced
features) is far more complicated than that for SML.

----------------------------------------------------------------
Comparing type classes with SML Modules

A class declaration is similar to an ML signature. For instance

    class Eq a where
      == :: a -> a -> Bool
      /= :: a -> a -> Bool

is analagous to

    signature EQ =
    sig
      type a
      val == : a -> a -> bool
      val /= : a -> a -> bool
    end;

One difference is that a type class may specify some default
method implementations:

    class Eq a where
      == :: a -> a -> Bool
      /= :: a -> a -> Bool
      x /= y = not (x == y)

Another difference is that defining the signature EQ does
not "reserve" the variables == and /=. They can be used in
other signatures, or anywhere else one wants to define them.

Also, for a given instance of the type a, we can define as
many modules implementing EQ for a as we like:

   structure IntEq : EQ =
   struct
     type a = int
     fun == (x: int) y = (x = y)
     fun /= x y = not(== x y)
   end

   structure IntEqMod3 : EQ =
   struct
     type a = int
     fun == (x: int) y = (x - y) mod 3 = 0 
     fun /= x y = not(== x y)
   end

and IntEq.== and IntEqMod3.== can coexist and be used
in the same context.

Furthermore, it is easy to define signatures and associated
structures containing multiple tycons, and such type-rich
structures do not have any impact on the complexity of type
checking.