Параметрический полиморфизм. Алгебраические типы. Классы типов.

Параметрический полиморфизм

maybe : ∀ a b. b -> (a -> b) -> Maybe a -> b

Такие типы называются в теории типов “универсально квантифицированными”. Это название происходит из логики, где ∀ называется квантором всеобщности или квантором универсальности.

Синтаксис Haskell по умолчанию опускает объявление переменных типа:

maybe :: b -> (a -> b) -> Maybe a -> b

Но допускает явное указание, если включено расширение ExplicitForAll:

maybe :: forall a b. b -> (a -> b) -> Maybe a -> b

Рассмотрим объявление Maybe:

data Maybe a = Just a | Nothing

Теперь рассмотрим тип конструктора Just:

Just :: a -> Maybe a

Этот тип является полиморфным:

Just :: forall a. a -> Maybe a

Невозможен без параметрического полиморфизма.

Типизация чистых λ-термов:

tru = λ x y. x
tru : ∀ a b. a -> b -> a

Алгебраические типы

Алгебраическими типами называются типы, поддерживающие “алгебраические” операции, а именно “сложение” и “умножение”.

Более формально, мы вводим бинарные конструкторы × и +, и определяем операции проекции:

fst : A × B -> A
snd : A × B -> B

и операцию case:

case x of
  left l -> v1
  right r -> v2

где x : A + B, l : A, r : B и v1 : T, v2 : T.

В рамках синтаксиса Haskell:

тип-произведение – пары (A, B), кортежи (A, B, C) и т.д.

Проекции

fst :: (a, b) -> a
snd :: (a, b) -> b

Конструкторы значений: (,), (,,) и т.д. Поддерживается синтаксис вида (x, y, z).

тип-сумма:

data Either a b = Left a | Right b

Haskell поддерживает пользовательские типы. Они могут быть типами-произведениями или типами-суммами, например:

data FullName = FullName String String
data ErrorOrResult a = Error ErrorType | Result a

Работа с такими типами через сопоставление с шаблоном. Например:

explicitError :: ErrorOrResult a -> a
explicitError (Error err) = error (show err)
explicitError (Result x) = x

или

explicitError :: ErrorOrResult a -> a
explicitError x = case x of
  Error err -> error (show err)
  Result y -> y

или

explicitError :: ErrorOrResult a -> a
explicitError x
  | Error err <- x = error (show err)
  | Result y <- x = y

Записи

Для облегчения работы с типами-произведениями – записи. Вводят тип-произведение вместе с проекциями. В случае Haskell:

data RecordType = RecordValueConstructor {
    prj1 :: SomeType1
  , prj2 :: SomeType2
  -- etc
  }

Более конкретный пример:

data FullName = FullName {
    fullNameFirstName :: String -- имя
  , fullNameFamilyName :: String -- фамилия
  }

Создаёт объявления:

data FullName = FullName String String
fullNameFirstName :: FullName -> String
fullNameFamilyName :: FullName -> String

Специальный синтаксис для значений:

someFullName = FullName {
    fullNameFirstName = "Иван"
  , fullNameFamilyName = "Петров"
  }

Эквивалентно:

someFullName = FullName "Иван" "Петров"

Единичный тип

Сила алгебраических типов становится более явной, если ввести единичный тип. Это тип, который имеет ровно одно значение.

В теории типов – unit : Unit.

В Haskell – () :: ().

На основе единичного типа и конструкторов суммы и произведения можно построить в принципе любой тип.

data Boolean = False | True
data PeanoNatural = Zero | Succ PeanoNatural
data PeanoRational = PeanoRational {
    numenator :: PeanoNatural
  , denominator :: PeanoNatural
  }

Классы типов

При параметрическом полиморфизме, определение функции остаётся одинаковым для всех типов.

Например:

maybe :: b -> (a -> b) -> Maybe a -> b
maybe n _ Nothing  = n
maybe _ f (Just x) = f x

Класс типов (так же известный как typeclass) – некий абстрактный интерфейс, которому должны удовлетворять все типы (конкретные и полиморфные), входящие в класс.

Классы типов – открытое множество, новые типы могут быть добавлены в класс “на лету”.

Добавление типов в класс производится объявлением реализации интерфейса класса (экземпляра) для какого-то типа (конкретного или полиморфного).

Класс Eq

Один из простейших классов типов.

Соответствует множеству типов, для которых реализована операция сравнения.

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

Так могла бы выглядеть реализация экземпляра для типа Bool:

instance Eq Bool where
  (==) True True = True
  (==) False False = True
  (==) _ _ = False
  (/=) x y = not (x == y) -- это может быть выведено автоматически

Классы типов ограничивают универсальную квантификацию. Например, функция lookup:

lookup :: (Eq a) => a -> [(a,b)] -> Maybe b
lookup _ [] = Nothing -- в пустом списке нет значений
lookup key ((x,y):xys) -- в непустом списке, берём первую пару
    | key == x -- если искомый ключ равен первому элементу пары
    = Just y -- возвращаем второй элемент пары (обёрнутый в Just)
    | otherwise -- в противном случае
    = lookup key xys -- рекурсивно просматриваем остаток списка

(реализация из стандартной библиотеки)

Можно указывать несколько ограничений через запятую.

Ограничения при объявлении экземпляров класса:

instance (Eq a) => Eq (Maybe a) where
  (==) (Just x) (Just y) = x == y -- если оба аргумента -- Just, сравнить значения без Just
  (==) Nothing Nothing = True -- если оба аргумента Nothing, то они равны
  (==) _ _ = False -- в противном случае, не равны

На практике, подобные определения компилятор GHC способен вывести самостоятельно. Для этого при объявлении типа используется директива deriving:

data Maybe a = Nothing | Just a
  deriving ( Eq, Ord )

Ограничение при объявлении класса типа:

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

Любой тип в классе Ord таким образом должен быть и в классе Eq.

Класс Ord

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

Минимальное определение: либо (<=), либо compare.

Другие распространённые классы

Show

Любой тип в строку

class Show a where
  showsPrec :: Int -> a -> ShowS
  show :: a -> String
  showList :: [a] -> ShowS
  {-# MINIMAL showsPrec | show #-}
type ShowS = String -> String

Read

Чтение значения из строки, полученной через show.

class Read a where
  readsPrec :: Int -> ReadS a
  readList :: ReadS [a]
  {-# MINIMAL readsPrec #-}

Для удобства:

read :: Read a => String -> a

Безопасные варианты (модуль Text.Read):

readMaybe :: Read a => String -> Maybe a
readEither :: Read a => String -> Either String a

Использование функции read иногда требует явного указания типа результата:

Prelude> read "4"
*** Exception: Prelude.read: no parse
Prelude> read "4" :: Int
4

Аналогичная проблема — show . read – имеет тип String -> String, недостаточно контекста для выбора экземпляров Read и Show.

Enum

Перечислимые типы

class Enum a where
  succ :: a -> a
  pred :: a -> a
  toEnum :: Int -> a
  fromEnum :: a -> Int
  enumFrom :: a -> [a]
  enumFromThen :: a -> a -> [a]
  enumFromTo :: a -> a -> [a]
  enumFromThenTo :: a -> a -> a -> [a]
  {-# MINIMAL toEnum, fromEnum #-}
[x..] = enumFrom x
[x,y..] = enumFromThen x y
[x..y] = enumFromTo x y
[x,y..z] = enumFromThenTo x y z

Bounded

Ограниченные типы

class Bounded a where
  minBound :: a
  maxBound :: a

Num

Численные типы

class Num a where
  (+) :: a -> a -> a
  (-) :: a -> a -> a
  (*) :: a -> a -> a
  negate :: a -> a
  abs :: a -> a
  signum :: a -> a
  fromInteger :: Integer -> a

Другие интересные численные классы: Real, Integral, Fractional, Floating, RealFrac и RealFloat. Краткий обзор в конспектах лекций.

Semigroup и Monoid

Полугруппы

class Semigroup a where
  (<>) :: a -> a -> a

Моноиды

class Semigroup a => Monoid a where
  mempty :: a
mconcat = foldr (<>) mempty

Типовый пример моноида – список.

instance Semigroup [a] where
  (<>) = (++)
instance Monoid [a] where
  mempty = []

Монады и функторы

Одна из основополагающих концепций в чистых ФЯП – монады.

Понятие из теории категорий.

С практической точки зрения, монада – это класс типов.

Функтор

Начнём с понятия функтора.

class Functor (f :: * -> *) where
  fmap :: (a -> b) -> f a -> f b
  (<$) :: a -> f b -> f a
-- списки
fmap f (xs :: [a]) = map f xs
-- Maybe a = Nothing | Just a
fmap f (Just x) = Just (f x)
fmap f Nothing = Nothing
-- Either a b = Left a | Right b
fmap f (Right x) = Right (f x)
fmap f (Left x) = Left x
--- списки
1 <$ [x,y,z] == [1,1,1]
1 <$ [] == []
-- Maybe a = Nothing | Just a
1 <$ Just x == Just 1
1 <$ Nothing == Nothing
-- etc

Формально,

a <$ x = fmap (const a) x

Все экземпляры класса Functor должны удовлетворять законам функтора:

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

Дополнительно вводится

(<$>) = fmap

символизирует применение функции “под функтором”.

Аппликативный функтор

class Functor f => Applicative (f :: * -> *) where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b

Любой экземпляр Applicative должен соблюдать следующие законы:

pure id <*> v == v
pure (.) <*> u <*> v <*> w == u <*> (v <*> w)
pure f <*> pure x == pure (f x)
u <*> pure y = pure ($ y) <*> u

Следствие – согласованность с функтором:

fmap f x = pure f <*> x

Пример:

(*) <$> [1,2,3] <*> [1,100,1000]
[(1*), (2*), (3*)] <*> [1,100,1000]
[1*1, 1*100, 1*1000, 2*1, 2*100, 2*1000, 3*1, 3*100, 3*1000]
[1,100,1000,2,200,2000,3,300,3000]

Дополнительно определяются функции

liftA2 f x y = f <$> x <*> y
u *> v = (id <$ u) <*> v
u <* v = liftA2 const u v

(<*>) можно определить через liftA2:

f <*> x = liftA2 id f x

Аналогично:

id f x = (id f) x = f x

Монады

class Applicative m => Monad (m :: * -> *) where
  (>>=) :: m a -> (a -> m b) -> m b
  (>>) :: m a -> m b -> m b
  return :: a -> m a

В основном интересует оператор (>>=) (“рыбий хвост”, чаще просто оператор связывания), прочие – из Applicative.

(>>) = (*>)
return = pure

Использование связывания:

(someComputation :: m a) >>= \x -> (otherComputation x :: m b)

do-нотация – сахар для монад:

do
  x <- someComputation :: m a
  otherComputation x :: m b

Эквивалентно

(someComputation :: m a)
>>= \x -> (otherComputation x :: m b)

Самая часто встречающаяся монада – IO.

getLine :: IO String

Дополнительные материалы

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

  1. Функторы, аппликативные функторы и монады в картинках (habr.com): https://habr.com/ru/post/183150/
  2. Зачем нужны все эти функторы и монады? (habr.com): https://habr.com/ru/post/212955/

Foldable и Traversable

class Foldable (t :: * -> *) where
  fold :: Monoid m => t m -> m
  foldMap :: Monoid m => (a -> m) -> t a -> m
  foldr :: (a -> b -> b) -> b -> t a -> b
  foldr' :: (a -> b -> b) -> b -> t a -> b
  foldl :: (b -> a -> b) -> b -> t a -> b
  foldl' :: (b -> a -> b) -> b -> t a -> b
  foldr1 :: (a -> a -> a) -> t a -> a
  foldl1 :: (a -> a -> a) -> t a -> a
  toList :: t a -> [a]
  null :: t a -> Bool
  length :: t a -> Int
  elem :: Eq a => a -> t a -> Bool
  maximum :: Ord a => t a -> a
  minimum :: Ord a => t a -> a
  sum :: Num a => t a -> a
  product :: Num a => t a -> a
  {-# MINIMAL foldMap | foldr #-}

Определён в Data.Foldable. Основные экземпляры – списки, Maybe, Either a и (,) a

Traversable

class (Functor t, Foldable t) => Traversable (t :: * -> *) where
  traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
  sequenceA :: Applicative f => t (f a) -> f (t a)
  mapM :: Monad m => (a -> m b) -> t a -> m (t b)
  sequence :: Monad m => t (m a) -> m (t a)
  {-# MINIMAL traverse | sequenceA #-}

Пара примеров:

Prelude> sequenceA [Just 1, Just 2]
Just [1,2]
Prelude> sequenceA [Just 1, Just 2, Nothing]
Nothing
Prelude> sequenceA (Just [1, 2])
[Just 1,Just 2]
Prelude> sequenceA Nothing
Nothing