(typeclass.txt)

Type Classes in Haskell

Terms: type class, instance of a type class

Examples (from standard Prelude):

---------------------------------------------------------------------- 
class  Eq a  where  
    (==), (/=) :: a -> a -> Bool  
 
        -- Minimal complete definition:  
        --      (==) or (/=)  
    x /= y     =  not (x == y)  
    x == y     =  not (x /= y)
----------------------------------------------------------------------


Notes:

  1. Class decl specifies an interface of operations (or, more
     generally, values) that are associated with "instances" of the
     type class.

  2. Default relative implementations mean not all of the interface
     specs have to be implemted when declaring an instance. Here only
     one of "--" or "/=" need to be implemented for an instance (if
     the default relative implementation of the other is what you want)


---------------------------------------------------------------------- 
class  (Eq a) => Ord a  where  
    compare              :: a -> a -> Ordering  
    (<), (<=), (>=), (>) :: a -> a -> Bool  
    max, min             :: a -> a -> a  
 
        -- Minimal complete definition:  
        --      (<=) or compare  
        -- Using compare can be more efficient for complex types.  
    compare x y  
         | x == y    =  EQ  
         | x <= y    =  LT  
         | otherwise =  GT  
 
    x <= y           =  compare x y /= GT  
    x <  y           =  compare x y == LT  
    x >= y           =  compare x y /= LT  
    x >  y           =  compare x y == GT
----------------------------------------------------------------------

Notes:

  1. The Ord class is dependent on the Eq class. It is called a
     "derived" class. Before you can declare an instance of Ord for a
     type T, you have to have an instance of Eq for T.  So any type
     for which an Ord instance exists also has an Eq instance, so you
     can test equality as well as ordering.

  2. Note that the default relative implementation of compare uses == for
     the type a.  Similarly, the default implementation of < and > depend
     on ==.  Is this the only reason that (Eq a) is required?

  3. A class declaration claims exclusive use of the variables used to 
     name its "members" (e.g. Eq has exclusive use of "==").  No other
     class can use the same member names.

  4. The member names of a class are called "overloaded" variables, although
     they can't be overloaded in the sense of being used in multiple classes.
     The are overloaded in the sense that there potentially multiple
     implementations (bindings) of the names, one per instance of the class.

----------------------------------------------------------------------
foo.hs
----------------------------------------------------------------------
class Foo a where
   foo :: a -> Bool

class Bar a where
   foo :: Int -> a
----------------------------------------------------------------------

ghci> :l foo
[1 of 1] Compiling Main             ( foo.hs, interpreted )

foo.hs:14:4:
    Multiple declarations of `Main.foo'
    Declared at: foo.hs:11:4
                 foo.hs:14:4
Failed, modules loaded: none.
----------------------------------------------------------------------


Example of instances:

---------------------------------------------------------------------- 
data T = A | B

instance Eq T where
   x == y = False   

instance Ord T where
   compare x y = EQ
----------------------------------------------------------------------

Notes: 
  1. Only data types can be declared as instances of a type class (and also
     primitive types, e.g. Char, Int, which are specified as a kind of data
     type in the Prelude).
  2. An instance implements the interface components (values, typically functions).
     These implementations are bundled in a "dictionary", actually a record of
     values. The dictionary for an Ord instance will have 7 components, implementing
     the specified values: compare, <, <=, >=, >, max, min.
  

A "higher-order" class instance (terminology?)

Example, lists as an instance of the Eq class.

----------------------------------------------------------------------
instance Eq a => Eq [a] where
  [] == [] = True
  x:xs == y:ys = x == y && xs == ys
  _ == _ = False
----------------------------------------------------------------------

Here the "instance" being defined is not a type constructor, but a
type expression, [a], consisting of the list tycon applied to type
variable a, where a is asserted to be an instance of Eq by the
"context" Eq a. This instance decl shows how equality of lists is
defined in terms of equality of their elements. Thus we are
effectively showing how to define equality for the list tycon (type
constructor) [].  This instance is essentially an equality functional
like List_eq defined as follows:

  List_eq : (a -> a -> Bool) -> ([a] -> [a] -> Bool)
  List_eq a_eq xs ys = case (xs,yx) of
                        ([],[]) -> True
                        (x::xs,y::ys) -> a_eq x y && List_eq a_eq xs ys
		          _ -> False

[Actially, the a_eq argument will be an Eq dictionary (a record of
implementations of == and /= for a), and List_eq will return an
Eq dictionary for [a]. I've simplified here by dealing with an
individual function in that dictionary.]

Thus the instance associated with the list constructor is a dictionary
functional mapping an Eq dictionary for the element type a to an
Eq dictionary for the compound type [a].

Here is another one for pairs (product types):

----------------------------------------------------------------------
instance (Eq a, Eq b) => Eq (a,b) where
  (x1,y1) == (x2,y2) = x1 == x2 && y1 == y2
----------------------------------------------------------------------

This can be expressed explicity by another equality functional, Pair_eq:

  Pair_eq : (a -> a -> Bool) -> (b -> b -> Bool) -> ((a,b) -> (a,b) -> Bool)
  Pair_eq a_eq b_eq (x1,y1) (x2,y2) =
     a_eq x1 x2 && b_eq y1 y2

The "type expression" being declared an instance is of one of the
following forms (where the number of type variables can vary):

   (T a b ...) -- defining an instance dictionary for n-ary tycon T
   (a,b,...)   -- defining an instance dictionary for n-ary product
   [a]         -- defining an instance dictionary for []
   (a -> b)    -- defining an instance dictionary for ->

where T is a primitive tycon or a data tycon (i.e. no synonyms (abbreviations)).

E.g.

class Eq b => Eq (Int -> b) where
  f == g = f(0) == g(0)

================================================================================ 
Wadler-Bott: "How to make ad-hod polymorphism less ad hoc", ACM POPL 1989
================================================================================

----------------------------------------------------------------------
WB: Figure 1: Definition of arithmetic operations
----------------------------------------------------------------------

class Num a where 
   (+), (*) :: a -> a -> allll
   negate   :: a -> a

instance Num Int where
  (+) = addInt   -- a presumed primitive function
  (*) = mulInt
  negate = negInt

instance Num Float where
  (+) = addFloat   -- a presumed primitive function
  (*) = mulFloat
  negate = negFloat

square :: Num a => a -> a
square x = x * x

squares :: (Num a, Num b, Num c) => (a,b,c) -> (a,b,c) 
squares (x,y,z) = (square x, square y, square z)

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

----------------------------------------------------------------------
WB: Figure 2: Translation of arithmetic operations
----------------------------------------------------------------------

-- a dictionary type for the Num class
data NumD a = NumDict (a -> a -> a) (a -> a -> a) (a -> a)

-- method selectors
add (NumDict a _ _) = a
mul (NumDict _ m _) = m
neg (NumDict _ _ n) = n

numDInt :: NumD Int
numDInt = NumDict addInt mulInt negInt

numDFloat :: NumD Float
numDFloat = NumDict addFloat mulFloat negFloat

square' :: NumD a -> a -> a
square numDa x = mul numDa x x

squares' :: (NumD a, NumD b, NumD c) -> (a,b,c) -> (a,b,c) 
squares' (NumDa, NumDb, NumDc) (x, y, z) =
  (square' numDa x, square' numDb y, square' numDc z)

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

Note the relation between types of squares and type of squares':

squares :: (Num a, Num b, Num c) => (a,b,c) -> (a,b,c)

squares' :: (NumD a, NumD b, NumD c) -> (a,b,c) -> (a,b,c)

Each class-bounded quantifier like (Num a) has been turned into:
  (i) a simple polymorphic type parameter a, and
  (ii) a dictionary value parameter (NumD a)

----------------------------------------------------------------------
WB: Figure 3: Definition of equality
----------------------------------------------------------------------

class Eq a where
  (==) :: a -> a -> Bool

instance Eq Int where
  (==) = eqInt  -- a predefined primitive

instance Eq Char where
  (==) = eqChar

member :: Eq a => [a] -> a -> Bool
member [] y = False
member (x:xs) y = (y == x) || member xs y

instance (Eq a, Eq b) => Eq (a,b) where
  (u,v) == (x,y) = (u == x) && (v == y)

instance Eq a => Eq [a] where
  [] == [] = True
  x:xs == y:ys = (x == y) && (xs == ys)
  _ == _ = False

data Set a = MkSet [a]

instance Eq a => Eq (Set a) where
  MkSet xs == MkSet ys =
     and (map (member xs) ys) && and(map (member ys) xs)

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

----------------------------------------------------------------------
WB: Figure 4: Translation of Equality
----------------------------------------------------------------------

data EqD a = EqDict (a -> a -> Bool)   -- equality dictionary

eq (EqDict e) = e                      -- dictionary selector

eqDInt :: EqD Int
eqDInt = EqDict eqInt  -- eqInt is a predifined primitive

eqDChar :: EqD Char
eqDChar = EqDict eqChar  -- eqChar is a predifined primitive

member' :: EqD a -> [a] -> a -> Bool
member' eqDa [] y = False    -- edDa not used
member' eqDa (x:xs) y = eq eqDa x y || member' eqDa xs y

eqDPair :: (EdD a, EqD b) -> EqD (a,b)
eqDPair (eqDa, eqDb) = EqDict(eqPair (eqDa, eqDb))

eqPair :: (EqD a, EqD b) -> (a,b) -> (a,b) -> Bool
eqPair (eqDa,eqDb) (x,y) (u,v) = eq eqDa x u && eq eqDb y v

eqDList :: EqD a -> EqD [a]
eqDList eqDa = EqDict (eqList eqDa)

eqList :: EqD a -> [a] -> [b] -> Bool
eqList eqDa [] [] = True
eqList eqDa (x:xs) (y:ys) = eq eqDa x y && eq (eqDList eqDa) xs ys

----------------------------------------------------------------------
Note that (eq (eqDlist eqDa)) can be simplified to (eqList eqDa).


Translations of particular function calls:

  3*4 == 12       -- == at Int, * at Int
    --->  eq eqDInt (mul numDInt 3 4) 12

  member [1,2,3] 2
    --->  member' eqDInt [1,2,3] 2

  "hello" == "goodbye"          -- == at [Char]
    ---> eq (eqDList eqDChar) "hello" "goodbye"

  [[1,2],[3]] == [[4,5,6]]      -- == at [[Int]]
    ---> eq (eqDList (eqDList eqDInt)) [[1,2],[3]] [[4,5,6]]

  [(1,True),(2,False)] == []    -- == at [(Int,Bool)]
    ---> eq (eqDList (eqDPair(eqDInt,eqDBool))) [(1,True),(2,False)] []


Another example:

memsq :: (Eq a, Num a) => [a] -> a -> Bool
memsq xs x = member xs (square x)

memsq' :: (EqD a, NumD a) -> [a] -> a -> Bool
memsq' (eqDa, numDa) xs y = member' eqDa xs (square' numDa y)

memsq [2,4,8] 2 
  --->  memsq' (eqDInt, numDInt) [2,4,8] 4


This is a pseudo definition of the list constructor from the Prelude:

data  [a]  =  [] | a : [a]  deriving (Eq, Ord)  
        -- Not legal Haskell; for illustration only

How are lists ordered?  Lexicographically:

instance Ord a => Ord [a] where
  compare [] [] = EQ
  compare [] _ = LT
  compare _ [] = GT
  compare (x:xs) (y:ys) = 
    case compare x y of
      EQ -> compare xs ys
      c -> c

Return to Set_abs.hs example -- making Set a an instance of Ord:


================================================================================ 
Constructor Classes
Mark Jones, A system of constructor classes: overloading and implicit
higher-order polymorphism, Journal of Functional Programming,
5(1):1-36, 1995.
================================================================================

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

  class  Monad m  where  
      (>>=)  :: m a -> (a -> m b) -> m b  
      (>>)   :: m a -> m b -> m b  
      return :: a -> m a  
      fail   :: String -> m a  

	  -- Minimal complete definition:  
	  --      (>>=), return  
      m >> k  =  m >>= \_ -> k  
      fail s  = error s

  sequence       :: Monad m => [m a] -> m [a]  
  sequence       =  foldr mcons (return [])  
		      where mcons p q = p >>= \x -> q >>= \y -> return (x:y)

  sequence_      :: Monad m => [m a] -> m ()  
  sequence_      =  foldr (>>) (return ())

  -- The xxxM functions take list arguments, but lift the function or  
  -- list element to a monad type  
  mapM             :: Monad m => (a -> m b) -> [a] -> m [b]  
  mapM f as        =  sequence (map f as)
----------------------------------------------------------------------

Various kinds of map functional:

Lists:

  map :: (a -> b) -> [a] -> [b]
  map f [] = []
  map f (x:xs) = f x : map f xs

Maybe (option):

  mapMaybe :: (a -> b) -> Maybe a -> Maybe b
  mapMaybe f Nothing = Nothing
  mapMaybe f (Just x) = Just (f x)

Sets:

  mapSet :: (a -> b) -> Set a -> Set b
  mapSet (MkSet m) = MkSet(map f m)

Trees:

  data Tree a = Lf a | Br (Tree a) (Tree a)
    
  mapTree :: (a -> b) -> Tree a -> Tree b
  mapTree f (Lf x) = Lf (f x)
  mapTree f (Br t1 t2) = Br (mapTree f t1) (mapTree f t2)

Try to capture as a type class

class Map m where  -- m : * 
  map :: (a -> b) -> ?1 -> ?2    -- polymorphic in a,b

It doesn't work, because there is no way to express the desired types
?1 and ?2. I.e., there is no way to express the type of map in terms
of a simple type variable representing an arbitrary class instance.


Solution: Introduce "constructor classes"
  (using "fmap" as the name of the overloaded map function
   to avoid conflict with Prelude.map?)

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

instance Functor [] where   -- [] : * -> *
  fmap f [] = []
  fmap f (x:xs) = f x : map f xs

instance Functor Maybe where   -- Maybe : * -> *
  fmap f Nothing = Nothing
  fmap f (Just x) = Just (f x)

instance Functor Tree where   -- Tree : * -> *
  fmap f (Lf x) = Lf (f x)
  fmap f (Br t1 t2) = Br (mapTree f t1) (mapTree f t2)

fmap :: Functor f => (a -> b) -> f a -> f b

So fmap now has a higher-order polymorphic type, with class
bounded quantification over the Functor class.

Question: Is there a pure form of higer-order polymorphism,
with (implicit) unconstrained quantification over arbitrary
type constructors, as in 

    ∀f : * -> *. ∀ a,b : *.  (a -> b) -> f a -> f b  ?


Here is a rather unusual instance. (Note: for this to work, you have
to set the flag -XFlexibleInstances to allow the instance constructor
to be an expression.)  (->) : * -> * -> *

instance Functor ((->) Int) where  -- (->) Int : * -> *
  fmap f g = f . g

square :: Int -> Int
square x = x * x

g :: Int -> String
g = fmap show square
g 3 ==> "9"

Here is another example where the Functor constructor is a 
partially applied binary tycon: (,) : * -> * -> *

instance Functor ((,) Int) where  -- (,) Int : * -> *
  fmap f (n,x) = (n, f x)

y :: (Int, String)
y = fmap show (2,5)
y ==> (2,"5")

But can we define the symmetric versions of these Functor instances
where the second argument of (->) (respectively (,)) are fixed and
the first arguments vary?

----------------------------------------------------------------------
Functor laws:  Any instance of the Functor constructor class
is supposed to obey the following algrebraic laws:

   fmap id = id
   fmap f . fmap g = fmap (f . g)
----------------------------------------------------------------------

Another example of a constructor class: Set
See setcc.hs.