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

Теперь попробуем несколько абстрагироваться от строгого теоретического изложения. Концептуально, все конструкции, вводимые в этой лекции можно ввести строго, аналогично лекции 3, однако для практических целей такие подробности не требуются.

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

До сих пор мы обсуждали только функции, которые принимают некоторые конкретные типы. В общем случае это оказывается не слишком удобно. Например, стандартная функция maybe может принимать первым аргументом значения любого типа. Функции, которые работают более, чем с одним типом, называются полиморфными, а форма полиморфизма, когда не фиксируется тип параметров функций, называется параметрическим полиморфизмом.

В теории типов полиморфный тип начинается с объявления т.н. переменных типов (обычно обозначаемых маленькими латинскими буквами), идущих после символа ∀ и заканчивающихся точкой, например ∀ a b c. Далее идёт обычное определение типа, при необходимости использующее эти переменные вместо конкретных типов. Так, например, для функции maybe можно было бы записать тип

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

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

Синтаксис Haskell по умолчанию опускает объявление переменных типа. Поскольку конкретные типы начинаются с заглавной буквы, а переменные типа – с маленькой, неоднозначности не возникает:

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

Однако Haskell так же допускает явное указание, если включено расширение ExplicitForAll. Тогда вместо ∀ используется ключевое слово forall:

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

Следует отметить, что объявление полиморфных типов или типов высшего порядка, таких как Either, Maybe и прочих, использующих переменные типов в левой части объявления, невозможно без параметрического полиморфизма. Действительно, рассмотрим объявление 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, (A, B, C) – произведение типов A, B и C и т.д. В Prelude (автоматически импортируемом стандартном модуле) имеются функции fst :: (a, b) -> a и snd :: (a, b) -> b. Конструктором значений являются операторы (,), (,,) и т.д. Поддерживается синтаксис вида (x, y, z).

“Стандартный” тип-сумма в Haskell реализован в виде типа

data Either a b = Left a | Right b

Haskell так же поддерживает введение пользовательских конструкторов типов, соответственно любой тип, значение которого строится на основе нескольких других, будет типом-произведением, например:

data FullName = FullName String String

будет типом-произведением строк, а тип

data ErrorOrResult a = Error ErrorType | Result a

будет типом-суммой ErrorType и какого-то типа a.

Обработка как типов-сумм, так и типов-произведений возможна через сопоставление с шаблоном. В частности, вышеприведённый тип ErrorOrResult можно разобрать используя сопоставление с шаблоном в объявлениях, конструкцию case, в условиях шаблонов и т.п.:

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
  }

Здесь RecordType – называние типа-произведения, RecordValueConstructor – название конструктора значений этого типа, prj1 и т.д. – названия функций-проекций, SomeType1 и т.д. – названия типов, входящих в тип-произведение. Более конкретный пример, скажем, возвращаясь к примеру FullName:

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, встроенный единичный тип обозначается () и имеет значение (). Далее, пользуясь синтаксисом Haskell, мы можем на основе единичного типа и конструкторов суммы и произведения построить в принципе любой тип.

В частности, булевские значения:

newtype SimpleBoolean = SimpleBoolean (Either () ())

true :: SimpleBoolean
true = SimpleBoolean (Right ())

false :: SimpleBoolean
false = SimpleBoolean (Left ())

Натуральные числа (это построение называется числа Пеано):

newtype PeanoNatural = PeanoNatural (Either () PeanoNatural)

succ :: PeanoNatural -> PeanoNatural
succ x = PeanoNatural (Right x)

zero :: PeanoNatural
zero = PeanoNatural (Left ())

one = succ zero
two = succ one
-- etc

Рациональные (положительные) числа:

newtype PeanoRational = PeanoRational (PeanoNatural, PeanoNatural)

numenator :: PeanoRational -> PeanoNatural
numenator (PeanoRational x) = fst x

denominator :: PeanoRational -> PeanoNatural
denominator (PeanoRational x) = snd x

и так далее.

Понятно, что, скажем конструкция Пеано для чисел оказывается не слишком эффективной по сравнению, например, с двоичным представлением. Однако наличие алгебраических типов позволяет рассуждать о более сложных типах через сведение их к примитивам.

Эквивалентные записи вышеприведённых типов, использующие возможность введения пользовательских типов и записи, будут выглядеть следующим образом:

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

Такое определение для Boolean используется Haskell по умолчанию.

Классы типов

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

Так, например, определение функции maybe в стандартной библиотеке имеет следующий вид:

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

Это определение должно работать для всех типов, которые могут быть подставлены в качестве переменных a и b.

Понятно, что если мы ничего не знаем о том, какой тип будет использован в качестве a или b, это очень сильно ограничивает реализацию: со значением полиморфного типа нельзя ничего сделать, только передать его в другую полиморфную функцию или вернуть.

Ограничения настолько сильные, что вышеприведённая реализация для maybe – единственно возможная без изменения типа, не генерирующая ошибок времени выполнения, и использующая все аргументы.

Понятно, что такие “драконовские” ограничения уместны не всегда. В связи с этим вводятся понятия классов типов и ограничений универсальной квантификации.

Класс типов (так же известный как typeclass) – это некий абстрактный интерфейс, которому должны удовлетворять все типы (конкретные и полиморфные), входящие в класс. На всякий случай подчеркнём, что классы типов не имеют прямого отношения к классам в ООП.

Классы типов являются открытым множеством, т.е. новые типы могут быть добавлены в класс “на лету”. Добавление типов в класс производится объявлением реализации интерфейса класса (экземпляра) для какого-то типа (конкретного или полиморфного). Для некоторых встроенных типов и классов реализации могут быть непрозрачными (т.е. вшитыми в среду времени выполнения и невыразимыми в коде).

Один из простейших классов типов – класс Eq, соответствующий множеству типов, для которых реализована операция сравнения. Рассмотрим его определение:

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

Из этого определения мы видим, что любой тип a, входящий в класс Eq, должен реализовывать операции проверки на равенство (==) и неравенство (/=). На самом деле, минимальное определение экземпляра включает только один из этих операторов, а второй получается отрицанием первого. Рассмотрим, для примера, как могла бы выглядеть реализация экземпляра для типа Bool:

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

На практике, реализация сравнения для Bool использует двоичное сравнение значений и является непрозрачной.

Наличие классов типов позволяет ограничивать универсальную квантификацию, требуя, чтобы какой-то из полиморфных типов принадлежал одному или нескольким классам. Такие ограничения записываются в сигнатуре функции через двойную стрелку =>. В частности, если мы, хотим написать функцию, использующую сравнение, например, функцию 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 -- рекурсивно просматриваем остаток списка

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

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

Кроме того, ограничения можно указывать и при объявлении экземпляров класса, например экземпляр Eq (Maybe a) требует наличия экземпляра Eq a:

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 )

Следует отметить, что в сложных случаях автоматический вывод может не работать. Однако, для классов Eq, Ord, Show и Read он работает практически всегда.

Кроме того, ограничение может быть объявлено при объявлении класса типа. В таком случае, все экземпляры такого класса должны так же быть экземплярами классов, указанных в ограничении. Так, в частности, класс Ord, определяющий интерфейс для сравнения (больше, меньше, etc), имеет следующее определение:

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. Любой тип в классе Ord таким образом должен быть и в классе Eq.

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

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

Позволяет отобразить любой тип в строку с помощью функции show. Прочие функции используются реже. Функция showsPrec используется в реализации show по умолчанию, и учитывает приоритет операторов, при необходимости вставляя скобки. Функция showList позволяет переопределить синтаксис для списков, в частности, используется для типа String (который является синонимом [Char]). Тип ShowS призван отразить, что showsPrec и showList возвращают не строку, а функцию, которая принимает строку и добавляет результат в начало этой строки. Этот приём позволяет записывать конкатенацию строк как композицию функций.

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

Обратная операция, чтение значения из строки, полученной через show. Отдельно следует отметить функцию

read :: Read a => String -> a

которая предоставляет простой интерфейс для чтения, используя класс Read. Следует так же отметить функции, объявленные в модуле Text.Read

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

которые, в отличие, от read, не генерируют исключение времени выполнения при некорректной входной строке.

Отдельно следует отметить, что использование функции read иногда требует явного указания типа результата. Так, например, при вызове read "4" в интерпретаторе GHCi без указания типа результата и без дополнительного контекста, интерпретатор не сможет вывести тип результата и выбросит ошибку.

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

Аналогичная проблема возникает при использовании конструкции вида show . read – такая композиция функций имеет тип String -> String и у компилятора/интерпретатора нет никакого дополнительного контекста для конкретизации типов.

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 #-}

Класс Enum соответствует классу перечислимых типов. “Перечислимость” в данном случае означает взаимно-однозначное соответствие с типом Int. Основное, что нас интересует касательно этого класса – это то, что синтаксис диапазонов-списков [1..10] работает через этот класс. succ и pred возвращают следующий/предыдущий элемент, и генерируют ошибку, если такого элемента нет. toEnum и fromEnum осуществляют преобразование из/в Int. enumFrom создаёт бесконечный возрастающий список начиная с данного, аналогично [1..]=[1,2,3,...], enumFromThen позволяет задать первых два элемента последовательности, последующие элементы будут с тем же шагом, аналогично [1,3..] = [1,3,5,7,...]. enumFromTo и enumFromThenTo позволяют ограничить список, указав максимальный элемент, аналогично [1..10]=[1,2,3,...,9,10] и [1,4..10] = [1,4,7] (отдельно отметим, что [0,5..10] = [0,5,10])

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

Класс типов, имеющих верхнюю и нижнюю границы. В частности, это все типы-перечисления вроде Bool, все типы машинных целых (Int, Word), и т.д.

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
  {-# MINIMAL (+), (*), abs, signum, fromInteger, (negate | (-)) #-}

Класс, включающий все численные типы. Отдельно отметим, что Word входит в класс Num, но операция negate вычисляет комплементарное положительное число (т.е. x + negate x == 0, но negate x > 0). Функция signum работает как математическая функция “сигнум”, возвращает 1 если аргумент положительный, -1, если он отрицательный, 0 если аргумент равен 0. Функция fromInteger позволяет преобразовать значение Integer в любой численный тип.

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

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

Класс полугрупп. Полугруппа – понятие из теории множеств. На правах напоминания, полугруппа – это множество с определённой на нём ассоциативной бинарной операцией. В данном случае “ассоциативной бинарной операцией” является <>. Собственно, для большинства типов, для которых можно определить какую-то одну типовую бинарную операцию, определён экземпляр Semigroup. Обычно это конкатенация, но возможны варианты.

class Semigroup a => Monoid a where
  mempty :: a

Класс моноидов. Моноид это полугруппа с нейтральным элементом. Здесь роль нейтрального элемента играет mempty. Дополнительно определяется функция mconcat, которая производит свёртку списка моноидов mconcat = foldr (<>) mempty.

Типовый пример моноида – список. Для списков, (<>) – это конкатенация, а нейтральный элемент – это пустой список [].

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

Одной из основополагающих концепций в чистых функциональных языках является понятие монады. Это понятие из теории категорий, но мы ограничимся практическим рассмотрением. С практической точки зрения, монада – это класс типов. Чтобы их ввести, для начала надо рассмотреть понятие функтора.

Функтор

С точки зрения Haskell, класс Functor определяется как

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

Это может выглядеть несколько непонятно, поэтому разберём построчно. Первая строчка определяет класс функтора для типов, имеющих вид * -> *. Это означает, что функторами являются не конечные типы, а полиморфные типы одного параметра, такие как, например Maybe.

Во второй строчке определяется функция fmap, принимающая функцию a -> b, и аргумент типа f a и возвращающая аргумент типа f b. fmap по сути применяет первый аргумент “под” функтором f. Конкретная реализация зависит от конкретного функтора. Но в частности, список является функтором, и для списков fmap = map. Другой пример функторов – Maybe, и fmap применяется к значению в Just (если есть). Третий пример – Either a (первый аргумент фиксирован), тогда fmap применяет функцию к значениям типа Right:

-- списки
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 <$ Nothing == Nothing
1 <$ [] == []
-- etc

но

1 <$ Just x == Just 1
1 <$ [x,y,z] == [1,1,1]
-- etc

Формально,

a <$ x = fmap (const a) x

Функтор сам по себе является достаточно мощной абстрактной концепцией. В принципе, о функторе можно думать как о некоем абстрактном контейнере для значений типа. Аналогии со списком позволяют построить неплохую интуицию. Однако следует отметить, что функтор не всегда является простым контейнером – часто этот “контейнер” может неявно тащить за собой огромный контекст дополнительной информации.

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

-- закон идентичности
fmap id  ≡  id
-- закон композиции
fmap (f . g)  ≡  fmap f . fmap g

Первый закон говорит нам, что применение “под функтором” функции идентичности не должно ничего менять. Второй, что применение композиции функций есть композиция применений функций, т.е. применение двух функций “сразу” должно иметь такой же результат, как применение функций “по очереди”.

Дополнительно вводится оператор (<$>), являющийся синонимом fmap и по сути символизирующий применение функции “под функтором”.

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

Второй класс, который нам нужно рассмотреть – класс аппликативных функторов. В Haskell он реализован в виде

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

Т.е. это функтор, у которого определены ещё две функции, pure, берущую “чистое” значение и оборачивающую его в функтор, и оператор (<*>), реализующий применение функции под функтором к значению под функтором.

Оператор (<*>) по сути позволяет применять функции произвольного числа аргументов к значениям под функтором.

Любой экземпляр 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,100,1000,2,200,2000,3,300,3000]

Первая часть операции, (*) <$> [1,2,3], из функтора, и применяет (*) к каждому элементу списка, результатом чего является список функций вида [(1*), (2*), (3*)], где (x*) – это частично применённый бинарный оператор. Вторая часть, [(1*), (2*), (3*)] <*> [1,100,1000], “достаёт” функции (1*) и тд. из-под функтора списка, и применяет каждую из них к [1,100,1000].

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

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

liftA2 по сути работает как fmap для функций 2 аргументов (в Control.Applicative есть так же определения liftA и liftA3). Определение само по себе достаточно бессмысленное, но (<*>) можно определить через 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.

Собственно, оператор связывания принимает значение, обёрнутое в монаду, и функцию, принимающую значение “без обёртки” и возвращающую что-то в той же монаде. Результатом является тип, возвращаемый функцией.

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

Обычно в Monad реализуется только оператор (>>=), остальные берутся из Applicative:

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

В частности, такие цепочки вычислений могут моделировать императивное исполнение программ. Название return связано как раз с этим.

Идея связывания заключается в следующем: берётся некое вычисление в некой монаде m, и связывается с некоторым именем в лямбда-выражении:

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

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

do-нотация является синтаксическим сахаром для монад. Конструкция вида

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

полностью эквивалентна вышеприведённой. Любое связывание при помощи оператора (<-) в do-нотации является связыванием при помощи оператора (>>=) без do-нотации.

Самый распространённый тип, являющийся монадой – это IO.

Вообще, функции, возвращающие монады, удобно интерпретировать как функции, описывающие “рецепт” для получения значения типа внутри монады. Так, например, функция getLine :: IO String – это “рецепт” того, как получить значение типа String (со стандартного ввода).

Большинство типов монад – прозрачные, т.е. описываются в терминах Haskell. IO – непрозрачный тип, и, собственно, все вычисления в IO – не являются “чистыми”, т.е. могут иметь (и часто имеют) побочные эффекты.

Основная цель выноса всех вычислений с побочными эффектами в тип IO в том, чтобы отделить чистый функциональный код от “внешнего мира”.

Экземпляры Monad должны удовлетворять следующим законам:

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

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

-- согласованность return/pure
pure ≡ return
-- согласованность ap/(<*>)
mf <*> mx ≡ mf >>= \f -> mx >>= \x -> return (f x)

Из согласованности c Applicative также следует согласованность >>= с функтором:

fmap f mx ≡ mx >>= \x -> return (f x)

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

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

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

Foldable и Traversable

Ещё два часто встречающихся класса типов, Foldable и Traversable, относятся к типам, для которых определены операции свёртки или в более частном случае случае прохода по структуре слева-направо.

Foldable

Класс Foldable определяет различные свёртки. Этот класс определён в модуле Data.Foldable, и Prelude переэкспортирует не все методы этого класса.

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 #-}

fold комбинирует значения в структуре используя экземпляр моноида, определённый для этих значений.

foldMap позволяет применить к каждому элементу структуры функцию, возвращающую моноид, затем комбинирует значения используя экземпляр моноида.

foldr – свёртка при помощи право-ассоциативного бинарного оператора от начального значения.

foldr' – строгая в применении оператора версия foldr

foldl – свёртка при помощи лево-ассоциативного бинарного оператора от начального значения.

foldl' – строгая в применении оператора версия foldl

foldr1, foldl1 – версии foldr и foldl, начинающие работу не от начального значения, переданного аргументом, а от значения в структуре. Не могут применяться к пустым структурам.

toList – преобразование структуры в линейный список.

null – проверка структуры на пустоту.

length – возвращает число элементов в структуре

elem – проверяет, содержит ли структура данный элемент

maximum – максимальный элемент непустой структуры

minimum – минимальный элемент непустой структуры

sum – сумма элементов структуры (если элементы – числа)

product – произведение элементов структуры (если элементы – числа)

Основные стандартные экземпляры класса – списки, 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 #-}

Traversable описывает структуры типа функтора, по которым возможен обход слева-направо.

sequenceA – Вычислить каждое “действие” (аппликативный функтор) в структуре, и вернуть собранный результат. По сути, позволяет “поменять местами” внешний функтор-Traversable и внутренний аппликативный функтор. Например, преобразовать [IO a] в IO [a] или [Maybe a] в Maybe [a] (и наоборот)

traverse – к каждому элементу структуры применить функцию, возвращающую аппликативный функтор. Затем объединить функторы (выполнить действия, связанные с этими функторами) слева-направо. traverse f = sequenceA . fmap f

sequence и mapM – аналоги sequenceA и traverse для монад. На самом деле, их реализация в большинстве случаев не будет отличаться от реализаций sequenceA и traverse, хотя возможны исключения. По большому счёту, эти функции включены в класс больше по историческим причинам.

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

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