Стандартные классы типов. Объявления классов типов.

Некоторые стандартные классы типов обсуждались в лекции 4. В рамках данной практической работы, нас интересует как можно объявить пользовательские типы экземплярами стандартных классов.

Напомним, стандартные классы типов включают:

  • Eq
  • Ord
  • Show
  • Read
  • Enum
  • Bounded
  • Semigroup
  • Monoid
  • Functor
  • Applicative
  • Monad
  • Foldable
  • Traversable

а также числовые классы:

  • Num
  • Integral
  • Fractional
  • Floating
  • RealFrac
  • RealFloat

Сразу оговоримся, что по стандарту Haskell2010, компилятор должен быть способен автоматически вывести для любого пользовательского типа экземпляры классов Eq, Ord, Show, Read, и класса Enum для перечислений (т.е. типов, все конструкторы значений которых не имеют аргументов) и Bounded для перечислений и типов, имеющих единственный конструктор значений. Для производных типов, все типы аргументов конструкторов значений должны быть экземплярами соответствующих классов.

Например, для пользовательского типа

data IntVector2D = Vector2D {
    intVec2DX :: Int
  , intVec2DY :: Int
  } deriving Bounded

возможно вывести экземпляр Bounded, поскольку он имеет единственный конструктор и оба аргумента конструктора значений (Int и Int) имеют экземпляр Bounded.

Это же определение уже не сработает:

data PersonWithAge = PersonWithAge {
    personName :: String
  , personAge :: Word
  } deriving Bounded

поскольку для первого аргумента конструктора значений (String) нет экземпляра Bounded.

Интересно отметить, что для полиморфных типов, выведение экземпляров откладывается до момента использования, т.е. скажем

data Vector2D a = Vector2D {
    intVec2DX :: a
  , intVec2DY :: a
  } deriving Bounded

будет работать для любого типа a, но для некоторых из них, не будет выведен экземпляр Bounded:

data Vector2D a = Vector2D {
    vec2DX :: a
  , vec2DY :: a
  } deriving (Bounded, Show)

myFunc :: Vector2D String
myFunc = Vector2D "a" "b"

myFunc2 :: Vector2D Word
myFunc2 = minBound

Это полностью рабочий код, однако такое определение уже будет некорректным:

myFunc :: Vector2D String
myFunc = minBound

сообщение компилятора:

• No instance for (Bounded [Char]) arising from a use of ‘minBound’
• In the expression: minBound
  In an equation for ‘myFunc3’: myFunc3 = minBound

Он сообщает, что для String (напомним, type String = [Char]) нет экземпляра Bounded, поэтому использование minBound для типа Vector2D String некорректно.

Класс Eq

Класс Eq относится к автоматически выводимым классам, но полезно написать пару экземпляров самостоятельно.

Рассмотрим следующий тип-перечисление:

data DayOfWeek = Mon | Tue | Wed | Thu | Fri | Sat | Sun

Теперь попробуем написать экземпляр класса Eq. Минимальное мы должны определить либо оператор (==), либо (/=). В данном случае более простой первый вариант.

instance Eq DayOfWeek where
  Mon == Mon = True
  Tue == Tue = True
  Wed == Wed = True
  Thu == Thu = True
  Fri == Fri = True
  Sat == Sat = True
  Sun == Sun = True
  _   == _   = False

Здесь мы используем сопоставление с шаблоном, чтобы определить какие значения равны, затем используем шаблон “всё равно” _ для описания всех остальных вариантов. Важно не забывать про последний случай, _ == _ = False, поскольку если его не определить, функция будет частично определена и вернёт ошибку при вызове с неопределённой комбинацией аргументов.

Рассмотрим теперь тип

data PersonWithAge = PersonWithAge {
    personName :: String
  , personAge :: Word
  }

Равенство для него будет описываться равенством входящих в него значений.

instance Eq PersonWithAge where
  x == y = personName x == personName y
        && personAge x == personAge y

Такое определение несколько многословно, можно переписать его несколько короче, используя функцию on из Data.Function

on :: (b -> b -> c) -> (a -> b) -> a -> a -> c

Как можно понять из сигнатуры, on принимает бинарную функцию над каким-то типом b и проекцию из a в b и возвращает бинарную функцию над a. Определение on можно было бы записать как

on binOp prj x y = binOp (prj x) (prj y)

Тогда экземпляр можно переписать в виде

import Data.Function -- здесь определена ф-я on
instance Eq PersonWithAge where
  x == y = ((==) `on` personName) x y
        && ((==) `on` personAge) x y

Если дополнительно воспользоваться тем, что функции являются экземплярами Applicative, то можно записать ещё короче

import Data.Function -- здесь определена ф-я on
import Control.Applicative -- здесь определена ф-я liftA2
instance Eq PersonWithAge where
  (==) = (liftA2 . liftA2) (&&)
      ((==) `on` personName)
      ((==) `on` personAge)

но конечно последний вариант может быть сложнее для восприятия.

Напишем теперь класс Eq для полиморфного типа

data Vector2D a = Vector2D {
    vec2DX :: a
  , vec2DY :: a
  }

Чтобы сравнивать значения этого типа на равенство, мы должны иметь возможность сравнивать значения типа a (параметра) на равенство. Поэтому мы должны указать это ограничение при определении экземпляра:

instance (Eq a) => Eq (Vector2D a) where
  a == b = vec2DX a == vec2DX b
        && vec2DY a == vec2DY b

Это определение тоже можно упростить до

instance (Eq a) => Eq (Vector2D a) where
  (==) = (liftA2 . liftA2) (&&)
        ((==) `on` vec2DX)
        ((==) `on` vec2DY)

Класс Ord

Теперь напишем определения экземпляров Ord для тех же типов. Напомним, что Ord является подклассом Eq, т.е. для любого экземпляра Ord должен быть экземпляр Eq.

Будем исходить из следующих определений:

data DayOfWeek
  = Mon | Tue | Wed | Thu | Fri | Sat | Sun deriving (Eq)
data PersonWithAge = PersonWithAge {
    personName :: String
  , personAge :: Word
  } deriving (Eq)
data Vector2D a = Vector2D {
    vec2DX :: a
  , vec2DY :: a
  } deriving (Eq)

(вместо deriving (Eq) можно использовать экземпляры, определённые в прошлом разделе)

Минимальное определение для Ord требует определить либо оператор (<=), либо функцию compare.

instance Ord DayOfWeek where
  compare x y | x == y = EQ -- Если аргументы равны, то они равны
  compare Tue Mon = GT -- Tue больше, чем Mon
  compare Wed Mon = GT -- Wed больше, чем Mon
  compare Wed Tue = GT -- и Tue
  compare Thu Mon = GT -- Thu больше, чем Mon
  compare Thu Tue = GT -- ,Tue
  compare Thu Wed = GT -- и Wed
  compare Fri Sat = LT -- Fri меньше, чем Sat
  compare Fri Sun = LT -- и Sun
  compare Fri _   = GT -- Но больше чем всё остальное (кроме Fri)
  compare Sat Sun = LT -- Sat меньше, чем Sun
  compare Sat _   = GT -- Но больше, чем всё остальное
  -- Мы перечислили все случаи, когда первый аргумент больше второго.
  compare _   _   = LT -- У оставшихся комбинаций первый аргумент меньше второго

Достаточно многословно. Можно написать это чуть-чуть короче, пользуясь списками и функцией elem:

instance Ord DayOfWeek where
  compare x y | x == y = EQ -- Если аргументы равны, то они равны
  compare Mon _   = LT -- Mon меньше всего кроме себя
  compare Tue Mon = LT
  compare Tue _   = GT
  compare Wed x | x `elem` [Mon, Tue] = GT
                | otherwise = LT
  compare Thu x | x `elem` [Fri, Sat, Sun] = LT
  compare Fri x | x `elem` [Sat, Sun] = LT
  compare Sat Sun = LT
  compare Sat _   = GT
  compare Sun _   = GT
  compare _   _   = GT -- нерассмотренные случаи -- это
  -- compare Thu x, где x не [Fri, Sat, Sun]
  -- compare Fri x, где x не [Sat, Sun]

В данном случае конечно проще доверить вывод экземпляра компилятору.

instance Ord PersonWithAge where
  compare a b
    | personName a /= personName b
    = compare (personName a) (personName b)
    | otherwise
    = compare (personAge a) (personAge b)

Здесь мы исходим из лексикографического сравнения, т.е. значения упорядочены сначала по personName, затем, если personName равны, то по personAge.

Отметим, что определение, аналогичное Eq здесь подходит плохо:

instance Ord PersonWithAge where
  a <= b
    = personName a <= personName b
    && personAge a <= personAge b

Действительно, при таком определении мы получаем частичный порядок: если сравнить, например, PersonWithAge "a" 4 и PersonWithAge "b" 3, то мы получим

PersonWithAge "a" 4 <= PersonWithAge "b" 3 = False
PersonWithAge "b" 3 <= PersonWithAge "a" 4 = False

Такое определение, понятно, не совсем согласуется с обычным (хотя допустимо)

Хорошая новость в том, что у типа Ordering есть экземпляр Semigroup, соответствующий лексикографическому порядку:

instance Semigroup Ordering where
    LT <> _ = LT
    EQ <> y = y
    GT <> _ = GT

Используя этот факт, лексикографическое сравнение можно переписать в виде

instance Ord PersonWithAge where
  compare a b =
       compare (personName a) (personName b)
    <> compare (personAge a) (personAge b)

И это легко обобщается на записи с большим числом полей. Опять же, можно использовать трюк с функцией on и liftA2:

instance Ord PersonWithAge where
  compare = (liftA2 . liftA2) (<>)
    (compare `on` personName)
    (compare `on` personAge)

Для удобства можно также определить оператор:

data PersonWithAgeAndAddress
   = PersonWithAgeAndAddress {
        pwaName :: String
      , pwaAge :: Word
      , pwaAddress :: String
      } deriving (Eq)

instance Ord PersonWithAgeAndAddress where
  compare = (compare `on` pwaName)
          ? (compare `on` pwaAge)
          ? (compare `on` pwaAddress)
    where
    infixr 6 ? -- так же, как и у <>
    (f1 ? f2) x y = f1 x y <> f2 x y
    -- здесь примерно эквивалентно
    -- (?) = (liftA2 . liftA2) (<>)

Аналогично можно определить лексикографическое сравнение для полиморфных типов:

instance (Ord a) => Ord (Vector2D a) where
  compare = (liftA2 . liftA2) (<>)
        (compare `on` vec2DX)
        (compare `on` vec2DY)

хотя конечно для векторов в общем случае операция сравнения не определена.

В более общем случае, обычно полагается, что экземпляры Ord удовлетворяют аксиомам частичного порядка:

  1. Тразитивность

    Если x <= y && y <= z = True, то x <= z = True

  2. Рефлексивность

    x <= x = True

  3. Антисимметрия

    Если x <= y && y <= x = True, то x == y = True

Компилятор выводит лексикографический порядок.

Классы Functor, Applicative, Monad, Foldable и Traversable

Рассмотрим классы, которые определены для конструкторов типов одного аргумента. Для этого рассмотрим рекурсивную структуру типа “двоичное дерево”:

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

Класс Functor обобщает функцию map, определённую над списками. Идея в том, чтобы применить функцию к каждому элементу какой-то абстрактной структуры, не меняя при этом саму структуру.

instance Functor Tree where
  fmap f (Leaf x) = Leaf (f x)
  fmap f (Branch a b) = Branch (fmap f a) (fmap f b)

Проверим, что выполняются законы функтора:

  1. Идентичность

    fmap id x = id x

fmap id (Leaf x) = Leaf (id x) = Leaf x
fmap id (Branch a b)
  = Branch (fmap id a) (fmap id b)
  -- по структурной индукции
  = Branch (id a) (id b)
  = Branch a b

  2. Композиция

    fmap (f . g) x = (fmap f . fmap g) x

fmap (f . g) (Leaf x)
  = Leaf ((f . g) x)
  = Leaf (f (g x))
(fmap f . fmap g) (Leaf x)
  = fmap f (Leaf (g x))
  = Leaf (f (g x))
fmap (f . g) (Branch a b)
  = Branch (fmap (f . g) a) (fmap (f . g) b)
(fmap f . fmap g) (Branch a b)
  = fmap f (Branch (fmap g a) (fmap g b))
  = Branch ((fmap f . fmap g) a) ((fmap f . fmap g) b)
  -- по структурной индукции
  = Branch (fmap (f . g) a) (fmap (f . g) b)

Класс Applicative обобщает функторы до бинарных (и n-арных) функций. Минимальное определение включает pure, “поднимающую” чистое значение в значение в структуре, и либо liftA2, применяющий бинарную операцию, либо (<*>), применяющий функции в одной структуре к значениям в другой структуре.

Есть несколько способов определить экземпляр Applicative для этой структуры. Один из них – это определить (<*>) как для списков, перебирающий все возможные комбинации:

instance Applicative Tree where
  pure x = Leaf x
  (Branch f1 f2) <*> x = Branch (f1 <*> x) (f2 <*> x)
  (Leaf f) <*> (Branch x y) = Branch (f <$> x) (f <$> y)
  (Leaf f) <*> (Leaf x) = Leaf (f x)

Другой вариант – совмещать деревья, левые ветви к левым и правые – к правым:

instance Applicative Tree where
  pure x = Leaf x
  (Branch f1 f2) <*> (Branch x y) = Branch (f1 <*> x) (f2 <*> y)
  -- остальное так же
  (Branch f1 f2) <*> (Leaf x) = Branch (f1 <*> Leaf x) (f2 <*> Leaf x)
  (Leaf f) <*> (Branch x y) = Branch (f <$> x) (f <$> y)
  (Leaf f) <*> (Leaf x) = Leaf (f x)

Оба варианта удовлетворяют законам аппликативного функтора. Напомним, это:

  1. Идентичность

    pure id <*> v = v

  2. Композиция

    pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

  3. Гомоморфизм

    pure f <*> pure x = pure (f x)

  4. Обмен

    u <*> pure y = pure ($ y) <*> u

Напоминаем, следствие этих законов – согласованность с определением Functor:

fmap f x = pure f <*> x

Определим экземпляр Monad:

instance Monad Tree where
  (Leaf x) >>= f
    = f x
  (Branch l r) >>= f
    = Branch (l >>= f) (r >>= f)

Это, вообще говоря, единственное осмысленное определение. Кроме, собственно, основных законов монады, напомним:

  1. Левая идентичность: return a >>= k = k a
  2. Правая идентичность: m >>= return = m
  3. Ассоциативность: m >>= (\x -> k x >>= h) = (m >>= k) >>= h

есть ещё два требования, накладываемые на согласованность определения с Applicative:

  • pure = return
  • (<*>) = ap

В свою очередь ap определена как

ap :: Monad m => m (a -> b) -> m a -> m b
ap mf mx = mf >>= \f -> mx >>= \x -> return (f x)

Собственно, мы могли бы определить (<*>) как ap. Но нюанс в том, что с этим согласуется только первое наше определение Applicative, но не второе. Поэтому только первое определение Applicative может быть корректной монадой.

Определим Foldable и Traversable:

instance Foldable Tree where
  foldMap f (Leaf x) = f x
  foldMap f (Branch l r) = foldMap f l <> foldMap f r
  foldr binop acc (Leaf x) = binop x acc
  foldr binop acc (Branch l r)
    = foldr binop (foldr binop acc r) l

instance Traversable Tree where
  traverse f (Leaf x) = fmap Leaf (f x)
  traverse f (Branch l r) = liftA2 Branch (traverse f l) (traverse f r)
  sequenceA (Leaf x) = fmap Leaf x
  sequenceA (Branch l r) = Branch <$> sequenceA l <*> sequenceA r

Отдельно отметим, что достаточно новые версии GHC способны выводить экземпляры Functor, Foldable и Traversable самостоятельно в некоторых распространённых случаях. Для этого требуется включить расширения языка соответственно DeriveFunctor, DeriveFoldable и DeriveTraversable:

{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-}

data Tree a = Leaf a | Branch (Tree a) (Tree a)
    deriving (Functor, Foldable, Traversable)

Объявления классов типов

Нередко удобно объявлять пользовательские классы типов. Классы типов собственно являются формой полиморфизма, близкой по смыслу перегрузке функций. Соответственно, в случаях, когда требуется однотипно обрабатывать различные данные, удобно использовать классы типов.

Рассмотрим, например, два типа:

data PrivatePerson = PrivatePerson {
    personFirstName :: String
  , pesronLastName :: String
  , personBirthYear :: Word
  }
data Company = Company {
    companyName :: String
  , companyAddress :: String
  }

Возможно, где-то в бизнес-логике нам требуется отображать имя как физических лиц, так и юридических. Мы можем объявить класс вида

class HasName a where
  name :: a -> String

и объявить наши типы экземплярами этого класса:

instance HasName PrivatePerson where
  name p = personFirstName p <> " " <> personLastName p

instance HasName Company where
  name = companyName

и затем использовать их, например, так:

printName :: HasName a => a -> IO ()
printName x = putStrLn (name x)

Упражнения

Упражнение 1

В рассмотренном выше примере для класса Ord

data PersonWithAgeAndAddress
   = PersonWithAgeAndAddress {
        pwaName :: String
      , pwaAge :: Word
      , pwaAddress :: String
      } deriving (Eq)

instance Ord PersonWithAgeAndAddress where
  compare = (compare `on` pwaName)
          ? (compare `on` pwaAge)
          ? (compare `on` pwaAddress)
    where
    infixr 6 ? -- так же, как и у <>
    (f1 ? f2) x y = f1 x y <> f2 x y
    -- здесь примерно эквивалентно
    -- (?) = (liftA2 . liftA2) (<>)

Почему нельзя внести функцию compare в определение оператора? Например, так:

(f1 ? f2) x y = compare (f1 x) (f1 y) <> compare (f2 x) (f2 y)

Подсказка: это возможно только отчасти, иначе теряется свойство ассоциативности. Чтобы показать это, выпишите тип оператора ? с внесённой в него функцией compare и рассмотрите типы аргументов и возвращаемых значений. Сравните с типом оператора ? без функции compare.

Упражнение 1.5 (по желанию)

В рассмотренном выше примере для класса Eq

import Data.Function -- здесь определена ф-я on
import Control.Applicative -- здесь определена ф-я liftA2
instance Eq PersonWithAge where
  (==) = (liftA2 . liftA2) (&&)
      ((==) `on` personName)
      ((==) `on` personAge)

Выпишите типы всех подвыражений и проверьте, что они согласованы.

Подсказка: следует помнить, что -> – это тоже конструктор типа, записанный в виде правоассоциативного оператора, т.е. a -> b -> c это a -> (b -> c) и это (->) a ((->) b c). Частично применённый конструктор типа функции (->) a является экземпляром Applicative (а также Monad, и следовательно Functor)].

Упражнение 2

В рассмотренном выше примере для класса Applicative

instance Applicative Tree where
  pure x = Leaf x
  (Branch f1 f2) <*> (Branch x y) = Branch (f1 <*> x) (f2 <*> y)
  -- остальное так же
  (Branch f1 f2) <*> (Leaf x) = Branch (f1 <*> Leaf x) (f2 <*> Leaf x)
  (Leaf f) <*> (Branch x y) = Branch (f <$> x) (f <$> y)
  (Leaf f) <*> (Leaf x) = Leaf (f x)

Докажите, что законы аппликативного функтора действительно выполняются:

  1. Идентичность

    pure id <*> v = v

  2. Композиция

    pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

  3. Гомоморфизм

    pure f <*> pure x = pure (f x)

  4. Обмен

    u <*> pure y = pure ($ y) <*> u

Указание: Для доказательства удобно пользоваться законами функтора:

  1. Идентичность fmap id = id
  2. Композиция fmap (f . g) = (fmap f . fmap g)

или эквивалентно через оператор <$>:

  1. Идентичность id <$> x = x
  2. Композиция (f . g) <$> x = f <$> (g <$> x)

и связью функтора и апплиактивного функтора: fmap f x = pure f <*> x, или эквивалентно f <$> x = pure f <*> x.

Упражнение 3

Напишите экземпляры Functor, Applicative, Monad, Foldable и Traversable для следующих типов:

  1. data Singleton a = Singleton a
  2. data Productish a b = Productish a b
  3. data Summish a b = First a | Second b
  4. data Optional a = NoValue | HasValue a
  5. data NotQuiteList a = Value a | Layer (NotQuiteList a)
  6. data NotEmpty a = LastValue a | MidValue a (NotEmpty a)

Указание: Экземпляры Functor и пр., так же как и прочие классы типов, могут быть полиморфными, поэтому, скажем, для конструктора типа Summish можно написать экземпляр Functor, несмотря на то, что он требует двух аргументов, частично применив его: instance Functor (Summish a) where ...

В качестве шаблона рекомендуется использовать https://github.com/haskell-course-lierdakil/instances-template, там определены тесты корректности.

Упражнение 4

Рассмотрите типы

data MayHaveValue a = NoValue | HasValue a deriving (Show)
data ToBeOrNot a = NotToBe | ToBe a deriving (Show)
data HasSomething a = HasNothing | HasSomething a deriving (Show)

они могут быть преобразованы из и в стандартный тип Maybe. Объявите класс Maybeish, имеющий функции fromMaybe и toMaybe, производящие соответствующие преобразования. Напишите экземпляры этого класса для этих типов и Maybe.