6.1 Type classes
The basic idea of type classes is simple enough. Consider equality, for example. In Haskell we may write

Class Eq a where
  (==) :: a -> a -> Bool
  (/=) :: a -> a -> Bool

instance Eq Int where
  i1 == i2 = eqInt i1 i2
  i1 /= i2 = not (i1 == i2)

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

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

The type signature for member uses a form of bounded quantification: it declares that member has type a->[a]->Bool, for any type a that is an instance of the class Eq. A class declaration specifies the methods of the class (just two in this case, namely (==) and (/=)) and their types. A type is made into an instance of the class using an instance declaration, which provides an implementation for each of the class’s methods, at the appropriate instance type.
A particularly attractive feature of type classes is that they can be translated into so-called “dictionary-passing style”, by a type-directed transformation. Here is the translation of the above code:

data Eq a = MkEq (a->a->Bool) (a->a->Bool)
eq (MkEq e _) = e
ne (MkEq _ n) = n

dEqInt :: Eq Int
dEqInt =  MkEq eqInt (not . eqInt)

dEqList :: Eq a -> Eq [a]
dEqList (MkEq e _) =  MkEq el (not . el)
    where el []     []     = True
          el (x:xs) (y:ys) = x `e` y && xs `el` ys

member :: Eq a -> a -> [a] -> Bool
member d x [] = False
member d x (y:ys) | eq d x y  = True
                  | otherwise = member d x ys

The class declaration translates to a data type declaration, which declares a dictionary for Eq; that is, a record of its methods. The functions eq and ne select the equality and inequality method from this diction-ary. The member function takes a dictionary parameter of type Eq a, corresponding to the Eq a constraint in its original type, and performs the membership test by extracting the equality method from this dictionary using eq. Finally, an instance declaration translates to a function that takes some dictionaries and returns a more complicated one. For example, dEqList takes a dictionary for Eq a and returns a dictionary for Eq [a].

6.1 Классы типов
Основная идея классов типов достаточно проста. Рассмотрим, например, равенство. В Хаскелле мы можем написать:

Class Eq a where
  (==) :: a -> a -> Bool
  (/=) :: a -> a -> Bool

instance Eq Int where
  i1 == i2 = eqInt i1 i2
  i1 /= i2 = not (i1 == i2)

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

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

Сигнатура типа для member использует форму ограниченного квантора: она объявляет, что member имеет тип a->[a]->Bool, для любого типа a, являющегося экземпляром класса Eq. Объявление class определяет методы этого класса (в данном случае два метода, а именно (==) и (/=)) и их типы. Тип становится экземпляром класса с помощью объявления instance, которое обеспечивает реализацию каждого метода класса, подходящую для типа экземпляра.
Особенно привлекательным свойством классов типов является возможность их трансляции в так называемый “dictionary-passing style” через типо-ориентированное преобразование (type-directed transformation). Вот трансляция предыдущего кода:

data Eq a = MkEq (a->a->Bool) (a->a->Bool)
eq (MkEq e _) = e
ne (MkEq _ n) = n

dEqInt :: Eq Int
dEqInt =  MkEq eqInt (not . eqInt)

dEqList :: Eq a -> Eq [a]
dEqList (MkEq e _) =  MkEq el (not . el)
    where el []     []     = True
          el (x:xs) (y:ys) = x `e` y && xs `el` ys

member :: Eq a -> a -> [a] -> Bool
member d x [] = False
member d x (y:ys) | eq d x y  = True
                  | otherwise = member d x ys

Объявление class переводится в объявление типа data, которое объявляет словарь (dictionary) для Eq, то есть запись (record) из его методов. Функции-селекторы eq и ne выбирают методы равенства и неравенства из этого словаря. Функция member принимает параметр-словарь типа Eq a, соответствующий ограничению Eq a своего исходного типа, и выполняет проверку на членство (значения в списке), выделяя метод равенства из этого словаря с помощью eq. Наконец, объявления instance транслируются в функции, принимающие некоторый словарь и возвращающие более сложный словарь. Например, dEqList принимает словарь для Eq a, а возвращает словарь для Eq [a].

Eq2> member dEqInt 2 [3,5,2]
True
Eq2> member dEqInt 2 [3,5,7]
False
Eq2> member (dEqList dEqInt) [3,5] [[4],[1,2,3],[3,5]]
True
Eq2> member (dEqList dEqInt) [3,5] [[4],[1,2,3],[3,8]]
False

D>data Eq a = MkEq (a->a->Bool) (a->a->Bool)
D>eq (MkEq e _) = e
D>ne (MkEq _ n) = n

D>dEqInt :: Eq Int
D>dEqInt =  MkEq eqInt (not . eqInt)
D>dEqList :: Eq a -> Eq [a]
D>dEqList (MkEq e _) =  MkEq el (not . el)
D>    where el []     []     = True
D>          el (x:xs) (y:ys) = x `e` y && xs `el` ys

D>member :: Eq a -> a -> [a] -> Bool
D>member d x [] = False
D>member d x (y:ys) | eq d x y  = True
D>                  | otherwise = member d x ys
D>

(curry (not . uncurry eqInt))

-- f(g(x y))
(.##) :: (a -> b) -> (c -> d -> a) -> c -> d -> b
(.##) =  (.) . (.) 
-- можно было бы и так
-- (.##) f g = curry (f . uncurry g)
-- но это недостаточно point-free :)

(not .## eqInt)