Прогулки с тайпклассами Haskell: аппликативные функторы
Как мы уже выяснили, функторы позволяют втягивать “обычную” функцию в некоторый вычислительный контекст, превращая её в функцию над контекстами:
> :t (* 3)
(* 3) :: Num a => a -> a
> :t fmap (* 3)
fmap (* 3) :: (Functor f, Num b) => f b -> f b
В этом примере (* 3) – это функция “утроения” (функция от одного числа, отсюда и a -> a). Функция fmap (* 3) тогда есть “функция утроения содержимого некоторого
контейнера (функтора)”. Конкретизируем пример на списковый функтор []:
-- число в контексте списка ("недетерминированного результата", т.е. принимающее несколько значений одновременно)
nums :: Num a => [a]
nums = [10, 20, 30]
-- функция над числом в контексте списка (т.е. функции)
funs :: Num a => [a -> a]
funs = [(* 3), (+1), (-) 2]
Для некоторого функтора f и каких-то типов a и b мы имеем f a и f (a -> b).
Как же нам применить функцию-в-контексте к значению-в-контексте и получить результат-в-контексте? Средств тайпкласса Functor уже не хватает, чтобы применить
f (a -> b) к f a и получить f b. Хотелось-бы уметь применять функции к аргументам в f-мире, тем самым получая возможность выстраивать цепочку вычислений
(компьютерную программу) внутри окружения (нужного вычислительного контекста).
-- всё просто, когда ты в безконтекстном мире
> sqrt 36
6.0
-- но как быть в f-мире? Всё это работать не будет...
> [sqrt] [36]
> (Just sqrt) (Just 36)
> ...
Очевидно, мы не можем так просто взять и написать некий общий код для применения функции к аргументу внутри какого-то там абстрактного функтора. Ведь такой код должен будет знать, как деконструировать функтор, чтобы вытащить “чистую” функцию и её “чистый” аргумент, а также, наоборот, как конструировать функтор с результатом данного применения (аппликации).
Applicative⌗
Крутейший тайпкласс Applicative наделяет функторы такой возможностью. Аппликативные функторы являются уточнением функтора, поэтому любой экземпляр Applicative – это
также и Functor (но не наоборот). Определение аппликативного функтора:
class Functor f => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
Сигнатура <*> точь в точь совпадает с тем, чего мы пытались получить в нашем f-мире в примере выше!
> [sqrt] <*> [36]
[6.0]
> Just sqrt <*> Just 36
Just 6.0
> Just (+) <*> Just 36 <*> Just 14
Just 50
Блгодаря повсеместному каррированию, мы можем свободно применять функции от нескольких аргументов внутри аппликативного контекста, главное, чтобы совпадали все типы входов/выходов. Аппликативное окружение, таким образом, как-бы эволюционирует, меняется при “протаскивании” каррированием вычисления через контекст с каждым новым вызовом <*>.
Например, для некоторого аппликативного функтора a:
# псевдокод
a (t1 -> t2 -> ... -> tm -> tn) <*> a t1 <*> a t2 <*> ... <*> a tm == a tn
a (t1 -> t2 -> ... -> tn) <*> a t1 == a (t2 -> ... -> tn)
a (t2 -> ... -> tn) <*> a t2 == a (t3 -> ... -> tn)
a (t3 -> ... -> tn) <*> a t3 == a (t4 -> ... -> tn)
# и так далее
Вернёмся к определению аппликативного функтора. Функция pure помещает “чистое” значение в контекст и тем самым в некоторой степени напоминает fmap.
Идея здесь в том, что pure втягивает значение в некий аппликативный контекст по-умолчанию, в (пока ещё) свободный от будущих эффектов контейнер.
> Just (+) <*> Just 36 <*> Just 14
Just 50
> pure (+) <*> Just 36 <*> Just 14
Just 50
Нетрудно заметить, что аппликативные функторы связаны с функторами следующим уравнением:
fmap g x = pure g <*> x
Применение g к содержимому контейнера x для Functor идиоматически то же самое, что помещение g в аппликативный контейнер по-умолчанию и затем применение функции
внутри данного аппликативного контейнера. Используя инфиксный синоним для fmap можно переписать уравнение так:
g <$> x = pure g <*> x
Упражнения⌗
1. Implement an instance of Applicative for Maybe.⌗
Напомню интерфейс Applicative:
class Functor f => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
Это просто. Я определяю тип MyMaybe, делаю его сначала функтором, а затем и аппликативным функтором. Аппликативный контекст обламывается, и втянутая функция не выолняется,
когда в контексте находится значение MyNothing:
data MyMaybe a = MyJust a | MyNothing
instance Functor MyMaybe where
fmap f MyNothing = MyNothing
fmap f (MyJust a) = MyJust (f a)
instance Applicative MyMaybe where
pure a = MyJust a
(<*>) (MyJust f) (MyJust a) = MyJust (f a)
(<*>) _ _ = MyNothing
Протестируем на функции, суммирующей четыре числа:
> -- sum4 :: Int -> Int -> Int -> Int -> Int
> let sum4 a b c d = sum [a, b, c, d]
>
> pure sum4 <*> MyJust 36 <*> MyJust 14 <*> MyJust 20 <*> MyJust 30
MyJust 100
> pure sum4 <*> MyJust 36 <*> MyJust 14 <*> MyNothing <*> MyJust 30
MyNothing
> pure sum4 <*> MyNothing <*> MyJust 14 <*> MyJust 20 <*> MyJust 30
MyNothing
Вследствии повсеместного каррирования в Haskell, sum4 действует на аппликативный контекст MyMaybe, обновляя этот контекст после каждой аппликации (после каждого <*>).
Мы видим, как наш контекст эволюционирует, доходя до последнего, четвёртого аргумента. Мы видим также, как аппликакции прекращаются когда <*> натыкается на MyNothing,
и контекст посреди вычисления вдруг становится постоянным (принимает значение MyNothing), протаскивая “ничего” до самого конца.
Мы в самом деле можем думать об аппликативном контексте, как о некоторой упорядоченной последовательности аппликаций. Например, мы можем оборвать вычисление суммы четырёх чисел посредине и попробовать два различных “продолжения” прерванному аппликативному контексту:
> let part1 = pure sum4 <*> MyJust 36 <*> MyJust 14
> part1 <*> MyJust 20 <*> MyJust 30
MyJust 100
> part1 <*> MyNothing <*> MyJust 30
MyNothing
2.Determine the correct definition of pure for the ZipList instance of Applicative—there is only one implementation that satisfies the law relating pure and (<*>).⌗
Определение ZipList дано такое:
newtype ZipList a = ZipList { getZipList :: [a] }
instance Applicative ZipList where
pure = undefined -- наше упражнение!
(ZipList gs) <*> (ZipList xs) = ZipList (zipWith ($) gs xs)
Прежде чем написать pure для Applicative ZipList, посмотрим как работает аппликация с функцией zipWith внутри такого контекста:
> ZipList [(+), (+)] <*> ZipList [1,2,3] <*> ZipList [10,20,30]
ZipList {getZipList = [11,22]}
> ZipList [(+), (*), (-), (+)] <*> ZipList [1,2,3] <*> ZipList [10,20,30]
ZipList {getZipList = [11,40,-27]}
То есть аппликация просто позиционно “сшивает” список функций с их параметрами, используя обычную операцию применения функций ($) к аргументам. Для каждой функции из
списков аргументов снимается по штуке, поэтому функций должно быть столько, сколько всего элементов в кратчайшем списке аргументов.
Элегантное решение с функцией repeat, которая повторяет свой параметр до бесконечности:
instance Applicative ZipList where
pure = ZipList . repeat
-- ...
Мы втягиваем в аппликативный контекст бесконечное количество функций, поэтому наш функтор будет работать со списками аргументов любой длины.
Аппликативные функторы⌗
Некоторые аппликативные функторы из Prelude Haskell:
instance Applicative (Either e) -- Defined in ‘Data.Either’
instance Applicative [] -- Defined in ‘GHC.Base’
instance Applicative Maybe -- Defined in ‘GHC.Base’
instance Applicative IO -- Defined in ‘GHC.Base’
instance Applicative ((->) a) -- Defined in ‘GHC.Base’
instance Monoid a => Applicative ((,) a) -- Defined in ‘GHC.Base’
Applicative [] реализует аппликацию не “сшиванием”, как ZipList выше, а последовательным применением функции к каждому из входов и сбором результатов:
> [(+), (*)] <*> [1,2] <*> [100,1000]
[101,1001,102,1002,100,1000,200,2000]
То есть поддерживает интуицию списка как аппликативного контекста недетерминированного выбора – мы получаем все возможные результаты одновременно.
Но мне больше всего нравится последний аппликативный функтор. Это – пара, первый элемент которой представляет собой некоторой моноид (алгебраическую структуру с
ассоциативной бинарной операцией и нейтральным элементом относительно неё). Моноидальные типы в Haskell представлены тайпклассом Monoid:
class Monoid a where
-- нейтральный элемент операции mappend
mempty :: a
-- собственно, сама бинарная операция (т.н. сложение, конкатенация и т.п.)
mappend :: a -> a -> a
Одна из возможных интуиций, связанных с этим довольно общим объектом, – это некий магазин (обойма), некий аккумулятор или разрастающаяся цепочка (строка), звенья
которой лепятся друг к другу бинарной операцией mappend^[Разумеется, структура замкнута относительно введённой в ней операции: оба элемента принадлежат множеству-носителю,
как и их “сумма”. Этот факт из алгебры в Haskell соответствует одинаковым типам в сигнатуре mappend, а также тому факту, что конструкторы значений a не выводят
за границы типа.]. Например, Monoid [] реализует mappend обычной конкатенацией списков, нейтральным элементом выступает пустой список (склеивание с пустым списком не
меняет исходного списка).
Вернёмся к нашему прекрасному аппликативному функтору. Чтобы понять его смысл, надо понять его <*>. Вот моя реализация:
instance Monoid a => Applicative ((,) a) where
pure x (a, _) = (mempty a, x)
(<*>) (a, f) (a', x) = (a `mappend` a', f x)
Данный аппликативный контекст умеет производить вычисления, параллельно накапливая результат в некой моноидальной структуре (первый элемент пары). Например, в списке:
> pure sum4 <*> (["add one"], 1) <*> (["add two"], 2) <*> (["add three"], 3) <*> (["add ten"], 10)
(["add one","add two","add three","add ten"],16)
Таким образом можно аккумулировать, например, логи происходящего внутри контекста: промежуточные результаты вычислений, шаги, ошибки, стек вызова и т.п. Реализация умеет
деконструировать текущий (f (a -> b)) и следующий (f a) элементы в аппликативной цепочке, поэтому можно контролировать процесс вычисления, исходя из его истории (эволюции аппликативного окружения).