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

А что, если нужно применить функцию с двумя аргументами к значениям из двух списков? Программист C++ напишет функцию с двумя аргументами или лямбду и передаст её выбранному алгоритму обхода. В Haskell операция $\mathtt{(+)}$ каррирована: получив один аргумент, она возвращает функцию, которая ожидает второй. Если отобразить $\mathtt{(+)}$ по первому списку, мы получим не суммы, а список частично применённых функций: $\mathtt{fmap\;(+)\;[1,2,3]}$ имеет тип $\mathtt{Num\;a}$ $\Rightarrow \mathtt{[a \to a]}$. Иными словами, функции оказались внутри контекста списка.

Обычный $\mathtt{Functor}$ умеет применять функцию $\mathtt{a \to b}$ к значениям в $\mathtt{f\;a}$, но не умеет применять функции из $\mathtt{f\;(a \to b)}$ к значениям из другого $\mathtt{f\;a}$. Для этого нужен более сильный класс типов — $\mathtt{Applicative}$ с оператором $(\mathbin{\mathtt{<*>}})$.

Класс $\mathtt{Applicative}$ расширяет $\mathtt{Functor}$ двумя операциями:

class Functor f => Applicative f where
  pure  :: a -> f a                  -- завернуть обычное значение
  (<*>) :: f (a -> b) -> f a -> f b  -- применить функцию из контекста

В этом объявлении $\mathtt{f}$ — конструктор типа рода $\mathtt{* \to *}$. Операция $\mathtt{pure}$ помещает обычное значение в контекст, а $(\mathbin{\mathtt{<*>}})$ применяет функцию в контексте к значению в том же контексте. Конкретную семантику этих операций задаёт каждый экземпляр. Для списка и $\mathtt{Maybe}$ стандартные экземпляры устроены так:

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

instance Applicative Maybe where
  pure = Just
  Nothing <*> _ = Nothing
  Just g  <*> x = fmap g x

Just (+3) <*> Just 2   -- Just 5

Важное для аппликативных функторов понятие — лифтинг: обычную функцию нескольких аргументов «поднимают» в контекст, чтобы она принимала аргументы в контекстах и возвращала результат в том же контексте. $\mathtt{liftA2}$ поднимает функцию с двумя аргументами, а $\mathtt{liftA3}$ — функцию с тремя аргументами:

liftA2 (+)
  (Just 2)
  (Just 3)
-- Just 5

liftA3 (\x y z -> x + y + z)
  (Just 1)
  (Just 2)
  (Just 3)
-- Just 6

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

pure id <*> v == v                             -- тождество

pure g <*> pure x == pure (g x)                -- гомоморфизм (отображение, сохраняющее структуру)
u <*> pure y == pure ($ y) <*> u               -- обмен
pure (.) <*> u <*> v <*> w == u <*> (v <*> w)  -- композиция

Законы гарантируют, что $\mathtt{pure}$ не добавляет лишнего эффекта, применение в контексте согласовано с обычным применением функций, а изменение группировки цепочки $(\mathbin{\mathtt{<*>}})$ не меняет результата. При этом они не разрешают произвольно переставлять эффекты: порядок может оставаться существенным.

Парочка примеров со списками, пожалуй:

-- каждая функция применяется к каждому значению
[(+1), (*2)] <*> [10, 20]
-- [11, 21, 20, 40]

-- частично применённое сложение: также все сочетания
(+) <$> [1, 2] <*> [10, 20]
-- [11, 21, 12, 22]