Курс "Программирование на Haskell"

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

Как вы помните, функторы обычно рассматриваются либо как контейнеры, либо как контексты вычислений. Функция fmap применяет заданную функцию к каждому элементу контейнера, не меняя саму структуру контейнера, либо к значению в контексте, не меняя самого контекста. Но функция fmap принимает в качестве параметра функцию от одного аргумента. Что делать, если нам захочется, например, сложить два числа, уже находящихся в контейнере/контексте? Мы, конечно, можем применить функцию fmap к операции (+):

fmap (+) (Just 1) :: (Num t) => Maybe (t -> t)
fmap (+) [1, 2, 3] :: (Num t) => [t -> t]
fmap (+) (Node 1 Leaf (Node 2 (Node 3 Leaf Leaf) Leaf)) :: (Num t) => Tree (t -> t)
fmap (+) (\e -> 5) :: (Num t) => e -> (t -> t)
fmap (+) (1, "some log") :: (Num t) => (t -> t, String)

Теперь мы получили функцию в контейнере/контексте и, чтобы применить эту функцию ко второму аргументу (также находящемуся в контейнере), нам необходимо каким-то образом достать функцию из контейнера/контекста. Если мы знаем структуру контейнера, мы можем это сделать. Например:

-- ap - сокращение от слова apply
ap :: Maybe (a -> b) -> Maybe a -> Maybe b
(Just f) `ap` (Just x) = Just (f x)
_ `ap` _ = Nothing

ap (fmap (+) (Just 1)) (Just 2) == Just 3
((+) `fmap` (Just 1)) `ap` (Just 2) == Just 3

Естественным продолжением класса Functor является класс Applicative (аппликативный функтор), определенный в модуле Control.Applicative:

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

Заметьте, что тип операции (<*>) обобщает тип функции ap, которую мы ввели выше для функтора Maybe. Именно эта операция позволяет применять функции в контексте. Функция pure добавляет еще одну возможность: поместить чистое значение в «чистый» контекст.

Обратите внимание на тип операции (<*>). Он схож с типом операции применения функции (операция «пробел»). Последняя может быть также записана при помощи операции ($):

($) :: (a -> b) -> a -> b
f $ x = f x

Отличие операции ($) от операции «пробел» заключается в обратном приоритете: если у операции «пробел» самый высокий приоритет, то у операции ($) — наоборот, самый низкий. Так вот:

(<*>) :: f (a -> b) -> f a -> f b
($)   ::   (a -> b) ->   a ->   b

Заметим, что функции эти практически идентичны. Различие в том, что операция (<*>) может, помимо применения функции, также каким-то образом обработать контекст. Рассмотрим несколько примеров:

instance Applicative Maybe where
    pure = Just
    (Just f) <*> (Just x) = Just $ f x
    _ <*> _ = Nothing

instance Applicative [] where
    pure x = [x]
    fs <*> xs = [ f x | f <- fs, x <- xs ]

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

Законы

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

-- Помещение тождественной функции в «чистый» контекст и применение к аргументу
-- в контексте не меняет ни значение, ни контекст.
pure id <*> x == x

-- Применение чистой функции к чистому аргументу в контексте «по умолчанию» должно
-- быть эквивалентно применению функции, а затем помещению результата в контекст.
pure f <*> pure x == pure (f x)

-- При применении функции u с побочными эффектами к чистому аргументу y порядок
-- вычисления функции и аргумента неважен.
u <*> pure y == pure ($ y) <*> u

-- Некоторый аналог композиции для аппликативных функторов.
u <*> (v <*> w) == pure (.) <*> u <*> v <*> w

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

Также существует закон, связывающий функтор с аппликативным функтором:

fmap f x = pure f <*> x

Этот закон говорит о том, что применение fmap эквивалентно помещению функции f в контекст при помощи pure, а затем применение ее к x при помощи (<*>). Модуль Control.Applicative также экспортирует операцию (<$>), как синоним для функции fmap. Таким образом, закон может быть переписан в следующем виде:

f <$> x = pure f <*> x

Упражнения

6.1. ★ Третий закон аппликативных функторов в принципе мог быть записан другим образом, если мы заменим чистое значение значением с побочным эффектом, а функцию с побочным эффектом — чистой функцией. Докажите, используя вышеописанные закон следующее:

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

Реализации аппликативных функторов

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

data ZipList a = ZipList [a]

instance Functor ZipList where
    fmap f (ZipList xs) = ZipList $ fmap f xs

instance Applicative ZipList where
    pure x = undefined -- реализуйте сами, учитывая законы для аппликативных функторов
    (ZipList fs) <*> (ZipList xs) = ZipList $ zipWith ($) fs xs

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

Упражнения

6.2. Напишите реализацию класса Applicative для следующих структур:

data Error e a = Err e | Ok a
data Log a = Log a String
data Reader r a = Reader (r -> a)

6.3. ★ Напишите реализацию класса Applicative для структуры ZipTree по аналогии с ZipList.

Монады

Скорее всего, если вы слышали о Haskell до этого курса, вы встречали понятие "монада". При этом вы наверняка раньше не слышали ни о функторах, ни о стрелках. Для этого может быть несколько объяснений:

• Haskell выделяет монады тем, что операции ввода/вывода в языке реализованы в виде специальной монады;
• Haskell также предоставляет синтаксический сахар для работы с монадами (do-нотация);
• класс Monad исторически используется гораздо дольше, чем Applicative или Arrow;
• чем больше появляется туториалов, объясняющих, что такое монады, тем больше люди думают, что это что-то сложное; и тем больше появляется новых туториалов, которые пишут люди, которые «поняли» монады (см. статью Monad turorial fallacy).

Но независимо от всего этого, монада в Haskell — всего лишь еще один класс типов. Рассмотрим его описание:

class Monad m where
    return :: a -> m a
    (>>=) :: m a -> (a -> m b) -> mb
    (>>) :: m a -> m b -> m b
    m >> n = m >>= \_ -> n

    fail :: String -> m a

Функция return по типу очень напоминает функцию pure из класса Applicative. И, в действительности, return и есть pure, хоть и с не самым удачным названием (return в Haskell совсем не то же, что return в обычных императивных языках вроде C или Java). С математической точки зрения, любая монада является аппликативным функтором (но не наоборот). Но по историческим причинам,в описании класса это не указано.

Как следует из определения, операция (>>) является частным случаем операции (>>=). Заметьте, что, хотя _ >> n = n было бы корректной реализацией с точки зрения типов, это было бы совсем неверно по смыслу: операция (>>) игнорирует результат вычисления m, но не побочные эффекты!

Функция fail осталась в классе по историческим причинам, хотя никакого отношения к монадам реально не имеет. Подробнее остановимся на ней ниже.

В действительности, единственной интересной операцией в классе Monad является (>>=). Но, прежде чем обсуждать абстрактное значение этой операции, давайте рассмотрим несколько примеров монад.

Монада Identity

Самым простым случаем монады является монада Identity:

data Identity a = Identity a

-- реализуйте самостоятельно, следуйте за типами
instance Monad Identity where
    return = undefined
    Identity x >>= f = undefined

Монада Maybe

Следующей по сложности является монада Maybe:

instance Monad Maybe where
    return = Just
    (Just x) >>= f = f x
    Nothing >>= _ = Nothing

Действительно, просто следуя типам, мы можем вывести эту реализацию операции (>>=): если первое вычисление (Just x), то у нас есть к чему применить функцию f; иначе — мы не можем использовать функцию f и вынуждены вернуть Nothing.

Теперь у нас может появиться некоторая интуиция насчет монады: если мы связываем вычисления при помощи (>>=), то, как только одно из вычислений «падает», вся связка тут же завершается. Это происходит потому, что Nothing >>= f = Nothing, независимо от того, чем является f.

Монада []

Реализация класса Monad для списка очень похожа на реализацию класса Applicative.

6.4. ★ Реализуйте класс Monad для списка.

Монада Reader

Как уже упомяналось выше, тип ((->) e) соответствует контексту вычислений с read-only окружением типа е.

6.5. ★ Реализуйте класс Monad для структуры Reader:

data Reader e a = Reader (e -> a)

В модуле Control.Monad.Reader приводится реализация этой структуры, реализация классов Functor, Applicative, Monad, а также реализация вспомагательных функций:

• ask :: Reader e e — запрашивает окружение;
• asks :: (e -> a) -> Reader e a — применяет к окружению заданную функцию;
• local :: (e -> e) -> Reader e a -> Reader e a — запускает вложенное вычисление с измененным контекстом.

Монада Writer

Монада Writer —это уже знакомая вам структура Log, только с произвольным типом записей лога s. Единственное требование к типу s предъявляется в виде класса типов Monoid:

class Monoid m where
    mempty :: m
    mappend :: m -> m -> m

6.6. ★ Реализуйте класс Monad для структуры Writer s:

data Writer s a = Writer a s

В модуле Control.Monad.Writer приводится реализация этой структуры, реализация классов Functor, Applicative, Monad, а также реализация вспомагательной функции:

• tell :: s -> Writer s () — записывает заданное выражение в лог.

Монада State

Монада State представляет из себя обертку над типом s -> (a, s). Интуитивно, эта монада представляет вычисления в контексте с состоянием типа s.

6.7. ★★ Реализуйте класс Monad для структуры State:

data State s a = State (s -> (a, s))

В модуле Control.Monad.State приводится реализация этой структуры, реализация классов Functor, Applicative, Monad, а также реализация вспомогательных функций:

• get :: State s s — возвращает текущее состояние.
• gets :: (s -> a) -> State s a — возвращает функцию от текущего состояния.
• put :: s -> State s () — перезаписывает состояние.
• modify :: (s -> s) -> State s () — модифицирует текущее состояние.

Монада RWS

Монада RWS r w s представляет из себя объединение монад Reader r, Writer w и State s.

6.8. ★★ Предложите реализацию структуры RWS r w s a и реализуйте класс Monad.

В модуле Control.Monad.RWS приводится реализация этой структуры, реализация классов Functor, Applicative, Monad, а также реализация вспомогательных функций.

Монада Cont

Монада Cont представляет из себя обертку над типом ((a -> r) -> r). Эта монада представляет вычисления в стиле континуаций. Несмотря на то, что в большинстве других функциональных языков программирования часто приходится использовать континуации, в Haskell зачастую можно обойтись другими абстракциями. Тип ((a -> r) -> r) может быть интерпретирован как вычисление, возвращающее значение типа a и передающая его следующему вычислению (континуации) типа (a -> r).

6.9. ★★★★ Реализуйте класс Monad для структуры Cont:

data Cont r a = Cont ((a -> r) -> r)

В модуле Control.Monad.Cont приводится реализация этой структуры, реализация классов Functor, Applicative, Monad, а также реализация вспомогательной функции:

• callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a
  Переключается на другую континуацию в контексте текущей.

Монада Cont обладает особенными свойствами, за что её называют «праматерью монад» («mother of all monads»).

Понимание монад

Еще раз взглянем на тип операции (>>=):

(>>=) :: m a -> (a -> m b) -> m b

Базовое понимание заключается в том, что эта операция комбинирует два вычисления и создает большее. Если бы второе вычисление было просто m b, то мы бы получили просто операцию (<*>) из класса Applicative и вычисления не могли бы взаимодействовать друг с другом. Но в действительности второе вычисление представлено функцией, принимающей на вход результат предыдущего вычисления и создающего следующее. Другими словами, x >>= k вычисляет x, а затем, в зависимости от результата, выбирает, какое вычисление запустить следующим.

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

Можно взглянуть на монады с другой стороны. Попробуем определить (>>=) через fmap, pure и (<*>). Итак, у нас есть значение x :: m a и функция f :: a -> m b. Всё, что мы можем сделать, это применить функцию к значению. Но, конечно же, не напрямую, а при помощи функции fmap. Однако, результатом такого применения будет выражение типа m (m b). При помощи pure мы можем увеличить вложенность монад, но мы не можем схлопнуть их!

Для того, чтобы уметь это делать, нам необходимо ввести специальную функцию: join :: m (m a) -> m a. Таким образом, для определения монады достаточно определить аппликативный функтор с операцией join.

В математике, действительно, монады определяются через return, fmap и join. В Haskell используется определение через (>>=), поскольку оно зачастую более интуитивна. Тем не менее, иногда бывает удобно думать о монадах в терминах join, поскольку атомарная операция (например, для списка join == concat).

Упражнения

6.10. ★★ Реализуйте (>>=) через fmap и join. 6.11. ★★ Реализуйте join и fmap через (>>=) и return.

Вспомогательные функции

В модуле Control.Monad определено большое число полезных функций для работы с монадами. Вот некоторые из них:

-- просто реализация функции fmap для монад
liftM :: Monad m => (a -> b) -> m a -> m b

-- просто реализация функции (<*>) для монад
ap :: Monad m => m (a -> b) -> m a -> m b

-- комбинирует список вычислений в одно, возвращающее список значений
sequence :: Monad m => [m a] -> m [a]

-- повторяет заданное вычисление заданное число раз и возвращает список результатов
replicateM :: Monad m => Int -> m a -> m [a]

-- в соответствии с условием, либо вычисляет второй аргумент, либо возвращает return ().
when :: Monad m => Bool -> m () ->  m ()

-- применяет функцию к элементам списка и выполняет sequence для получившегося списка вычислений.
mapM :: Monad m => (a -> m b) -> [a] -> m [b]

-- операция (>>=) с аргументами в обратном порядке.
-- Иногда такой порядок предпочтительнее, поскольку более соответствует применению функции.
(=<<) :: Monad m => (a -> m b) -> m a -> m b

-- Некоторый аналог композиции функций с обратным порядком аргументов.
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c

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

Законы для монад

Для монад также существует несколько законов:

return a >>= k = k a
m >>= return = m
m >>= (\x -> k x >>= h) = (m >>= k) >>= h
fmap f xs = xs >>= return . f = liftM f xs

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

При помощи операции (>=>), введенной выше, можно переформулировать законы в более красивом варианте:

return >=> g = g
g >=> return = g
(g >=> h) >=> k = g >=> (h >=> k)

Теперь законы выглядят гораздно лаконичнее и понятнее! Функция return является нулевым элементом относительно ассоциативной операции (>=>). Кроме этого, существует формулировка законов при помощи fmap, return и join, но мы не будем рассматривать их.

do-нотация

Haskell предоставляет специальный синтаксический сахар для написания кода в «императивном» стиле. Суть этого синтаксиса раскрывается, если записать цепочку монадических вычислений следующим образом:

a >>= \x ->
b >>
c >>= \y ->
d

При такой записи видно, что всё вычисление состоит из четырех действий a, b, c, d, и что значение x связано с результатом вычисления a, а значение y — с результатом b. Теперь можно представить себе более удобную запись:

do { x <- a;
     b;
     y <- c;
     d
   }

Фигурные скобки и точки с запятой можно опустить, парсер будет ориентироваться на отступы в коде:

do
    x <- a
    b
    y <- c
    d

Таким образом становится понятно, что do-нотация — это лишь синтаксический сахар:

                   do e ==> e
        do { e; stmts } ==> e >> do { stmts }
   do { v <- e; stmts } ==> e >>= \v -> do { stmts }
do { let decls; stmts } ==> let decls in do { stmts }

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

test = do
    Just x <- m
    return x

Но что, если вместо Just x вычисление m вернет Nothing? Именно в этом случае и сработает «грязный хак», который добавлен в монады Haskell по историческим причинам: будет вызван метод fail.