kingpin 9 июл 2011 в 07:37

Изучай Хаскель ради добра! Аппликативные функторы

37 мин

10K

Совсем недавно издательство No Starch Press подготовило и выпустило печатное издание замечательного учебника Learn You a Haskell for Great Good! (онлайн-версия), написанного Miran Lipovača.

Я хочу представить вам самый актуальный перевод главы 11 Аппликативные функторы, оригиналом для которого послужило именно издание от No Starch Press, адаптированное для печати.

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

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

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

Мы говорили о классах типов, которые определяют операции для проверки того, равны ли два элемента, и сравнения двух элементов по размещению их в каком-то порядке. Это очень абстрактные и элегантные поведения, хотя мы не думаем о них как о чем-то очень особенном, поскольку мы имели с ними дело большую часть нашей жизни. В главе 7 были введены функторы, которые являются типами, чьи значения можно отобразить. Это пример полезного и все ещё довольно абстрактного свойства, которое могут описать классы типов. В этой главе мы ближе познакомимся с функторами, а также — с немного более сильными и более полезными версиями функторов, которые имеют название аппликативные функторы.

Функторы возвращаются

Как вы узнали из главы 7, функторы — это сущности, которые можно отобразить, как, например, списки, значения Maybe, и деревья. В Хаскеле они описываются классом типов Functor, содержащим только один метод класса типов: fmap. fmap имеет тип fmap :: (a -> b) -> f a -> f b, который говорит, «Дайте мне функцию, которая принимает a и возвращает b и коробку, содержащую a (или несколько a) внутри, и я верну коробку с b (или несколькими b) внутри.» Она применяет функцию к элементу внутри коробки.

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

Если мы хотим сделать конструктор типа экземпляром Functor, он должен иметь вид * -> *, что значит, что он принимает ровно один конкретный тип в качестве параметра типа. Например, Maybe может быть сделан экземпляром, так как он получает один параметр типа для произведения конкретного типа, как, например, Maybe Int или Maybe String. Если конструктор типа принимает два параметра, как Either, мы должны частично применять конструктор типа до тех пор, пока он не будет принимать только один параметр. Поэтому мы не можем написать Functor Either where, но мы можем написать Functor (Either a) where. Затем если бы мы вообразили, что fmap предназначена только для работы с Either a, она имела бы следующее описание типа:

fmap :: (b -> c) -> Either a b -> Either a c

Как вы видите, часть Either a фиксирована, потому что Either a принимает только один параметр типа.

Действия ввода-вывода в качестве функторов

К настоящему моменту вы изучили, каким образом многие типы (если быть точным, конструкторы типов) являются экземплярами Functor: [] и Maybe, Either a, а также тип Tree, который мы создали в главе 7. Вы видели, как вы можете отображать их с помощью функций ради добра. Теперь давайте взглянем на экземпляр IO.

Если какое-то значение имеет, скажем, тип IO String, это означает, что оно является действием ввода-вывода, которое выйдет в реальный мир и получит какую-то строку для нас, которую оно затем вернет в качестве результата. Мы можем использовать <- в синтаксисе do для привязывания этого результата к имени. В главе 8 мы говорили о том, как действия ввода-вывода похожи на коробки с маленькими ножками, которые выходят наружу и получают для нас какое-то значение из внешнего мира. Мы можем посмотреть, что они принесли, но после просмотра нам необходимо обернуть значение обратно в IO. Рассматривая эту аналогию коробок на ножках, вы можете понять, каким образом IO действует как функтор.

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

instance Functor IO where
    fmap f action = do
    result <- action
    return (f result)

Результатом отображения действия ввода-вывод с помощью чего-либо будет действие ввода-вывода, так что мы сразу же используем синтаксис do для склеивания двух действий и создания одного нового. В реализации для fmap мы создаем новое действие ввода-вывода, которое сначала выполняет первоначальное действие ввода-вывода, давая результату имя result. Затем мы выполняем return (f result). Вспомните, что return — это функция, создающая действие ввода-вывода, которое ничего не делает, а только возвращает что-либо в качестве своего результата.

Действие, которое производит блок do, будет всегда возвращать результирующее значение своего последнего действия. Вот почему мы используем return, чтобы создать действие ввода-вывода, которое в действительности ничего не делает, а просто возвращает f result в качестве результата нового действия ввода-вывода. Взгляните на этот кусок кода:

main = do line <- getLine
    let line' = reverse line
    putStrLn $ "You said " ++ line' ++ " backwards!"
    putStrLn $ "Yes, you really said" ++ line' ++ " backwards!

У пользователя запрашивается строка, и мы отдаем ее обратно пользователю, но в перевернутом виде. А вот как можно переписать это с использованием fmap:

main = do line <- fmap reverse getLine
    putStrLn $ "You said " ++ line ++ " backwards!"
    putStrLn $ "Yes, you really said" ++ line ++ " backwards!"

Так же, как мы можем отобразить Just "blah" с помощью fmap reverse, получая Just "halb", мы можем отобразить getLine с помощью fmap reverse. getLine — это действие ввода-вывода, которое имеет тип IO String и отображение его с помощью reverse дает нам действие ввода-вывода, которое выйдет в реальный мир и получит строку, а затем применит reverse к своему результату. Таким же образом, как мы можем применить функцию к тому, что находится внутри коробки Maybe, мы можем применить функцию к тому, что находится внутри коробки IO, но она должна выйти в реальный мир, чтобы получить что-либо. Затем, когда мы привязываем результат к имени, используя <-, имя будет отражать результат, к которому уже применена reverse.

Операция ввода-вывода fmap (++"!") getLine ведет себя в точности как getLine, за исключением того, что к ее результату всегда добавляется "!" в конец!

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

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


import Data.Char
import Data.List
    
main = do line <- fmap (intersperse '-' . reverse . map toUpper) getLine
    putStrLn line

Вот что произойдет, если мы запустим этот код и введем hello there:

$ runhaskell fmapping_io
hello there
E-R-E-H-T- -O-L-L-E-H

Функция intersperse '-' . reverse . map toUpper берет строку, отображает ее с помощью toUpper, применяет reverse к этому результату, а затем применяет к этому результату intersperse '-'. Это является более красивым способом записи следующего кода:

(\xs -> intersperse '-' (reverse (map toUpper xs)))

Функции в качестве функторов

Другим экземпляром Functor, с которым мы все время имели дело, является (->) r. Стойте! Что, черт возьми, означает (->) r? Тип функции r -> a может быть переписан в виде (->) r a, так же как мы можем записать 2 + 3 в виде (+) 2 3. Когда мы воспринимаем его как (->) r a, мы видим (->) немного в другом свете. Это просто конструктор типа, который принимает два параметра типа, как это делает Either.

Но вспомните, что конструктор типа должен принимать в точности один параметр типа, чтобы его можно было сделать экземпляром Functor. Вот почему мы не можем сделать (->) экземпляром Functor; однако, если частично применить его до (->) r, это не составляет каких-либо проблем. Если бы синтаксис позволял частично применять конструкторы типов с помощью секций (как мы можем применить +, выполнив (2+), что аналогично (+) 2), вы могли бы записать (->) r как (r->).

Каким образом функции являются функторами? Хорошо, давайте взглянем на реализацию, которая находится в Control.Monad.Instances.

instance Functor ((->) r) where
    fmap f g = (\x -> f (g x))

Давайте сначала подумаем над типом fmap:

fmap :: (a -> b) -> f a -> f b

Далее, давайте мысленно заменим каждую f, которая является ролью, что играет наш экземпляр функтора, на (->) r. Это позволить нам понять, как fmap должна вести себя в случае этого конкретного экземпляра. Вот результат:

fmap :: (a -> b) -> ((->) r a) -> ((->) r b)

Теперь мы можем записать типы (->) r a и (->) r b в инфиксном виде, т. е.
r -> a и r -> b, как мы обычно поступаем с функциями:

fmap :: (a -> b) -> (r -> a) -> (r -> b)

Хорошо. Отображение одной функции с помощью другой функции должно произвести функцию, так же как отображение Maybe с помощью функции должно произвести Maybe, а отображение списка с помощью функции должно произвести список. О чем говорит нам предыдущий тип? Мы видим, что он берет функцию из a в b и функцию из r в a и возвращает функцию из r в b. Напоминает ли это вам что-нибудь? Да, композицию функций! Мы присоединяем выход r -> a ко входу a -> b, чтобы получить функцию r -> b, чем в точности и является композиция функций. Вот еще один способ записи этого экземпляра:

instance Functor ((->) r) where
    fmap = (.)

Этот код делает явным, что применение fmap к функциям — это просто композиция функций. В скрипте импортируйте Control.Monad.Instances, поскольку это модуль, где определен данный экземпляр, а затем загрузите скрипт и попробуйте поиграть с отображением функций:

ghci> :t fmap (*3) (+100)
fmap (*3) (+100) :: (Num a) => a -> a
ghci> fmap (*3) (+100) 1
303
ghci> (*3) `fmap` (+100) $ 1
303
ghci> (*3) . (+100) $ 1
303
ghci> fmap (show . (*3)) (*100) 1
"300"

Мы можем вызывать fmap как инфиксную функцию, чтобы сходство с . было явным. Во второй строке ввода мы отображаем (+100) с помощью (*3), что дает функцию, которая примет ввод, применит к нему (+100), а затем применит к этому результату (*3). Затем мы применяем эту функцию к 1.

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

Тот факт, что fmap является композицией функций при применении к функциям, не является на данный момент слишком полезным, но, по крайней мере, он очень интересен. Это также немного меняет наше сознание и позволяет нам увидеть, как сущности, которые действуют скорее как вычисления, чем как коробки (IO и (->) r), могут быть функторами. Отображение вычисления с помощью функции возвращает тот же самый тип вычисления, но результат этого вычисления изменен функцией.

lifter

Перед тем как перейти к законам, которым должна следовать fmap, давайте еще раз задумаемся о типе fmap:

fmap :: (a -> b) -> f a -> f b

Введение в каррированные функции в главе 5 началось с утверждения, что все функции в Хаскеле в действительности принимают один параметр. Функция a -> b -> c на самом деле берет только один параметр типа a, а затем возвращает функцию b -> c, которая принимает один параметр и возвращает c. Вот почему вызов функции с недостаточным количеством параметров (ее частичное применение) возвращает нам обратно функцию, принимающую несколько параметров, которые мы пропустили (если мы опять воспринимаем функции так, как если они принимают несколько параметров). Поэтому a -> b -> c можно записать в виде a -> (b -> c), чтобы сделать каррирование более очевидным.

В том же духе, если мы запишем fmap :: (a -> b) -> (f a -> f b), мы можем воспринимать fmap не как функцию, которая принимает одну функцию и значение функтора и возвращает значение функтора, но как функцию, которая принимает функцию и возвращает новую функцию, которая такая же, как и прежняя, за исключением того, что она принимает значение функтора в качестве параметра и возвращает значение функтора в качестве результата. Она принимает функцию a -> b и возвращает функцию f a -> f b. Это называется «лифтинг функции». Давайте поиграем с этой идеей, используя команду :t в GHCi:

ghci> :t fmap (*2)
fmap (*2) :: (Num a, Functor f) => f a -> f a
ghci> :t fmap (replicate 3)
fmap (replicate 3) :: (Functor f) => f a -> f [a]

Выражение fmap (*2) — это функция, которая получает функтор f над числами и возвращает функтор над числами. Этим функтором может быть список, значение Maybe, Either String, или что-то другое. Выражение fmap (replicate 3) получит функтор над любым типом и вернет функтор над списком элементов этого типа. Это становится еще очевиднее, если мы частично применим, скажем, fmap (++"!"), а затем привяжем ее к имени в GHCi.

Вы можете воспринимать fmap двумя способами:

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

Обе точки зрения верны.

Тип fmap (replicate 3) :: (Functor f) => f a -> f [a] означает, что функция будет работать с любым функтором. Что именно она будет делать, зависит от функтора. Если мы применим fmap (replicate 3) к списку, будет выбрана реализация fmap для списка, т. е. просто map. Если мы применим ее к Maybe a, то она применит replicate 3 к значению внутри Just. Если это значение равно Nothing, то оно останется равным Nothing. Вот несколько примеров:

ghci> fmap (replicate 3) [1,2,3,4]
[[1,1,1],[2,2,2],[3,3,3],[4,4,4]]
ghci> fmap (replicate 3) (Just 4)
Just [4,4,4]
ghci> fmap (replicate 3) (Right "blah")
Right ["blah","blah","blah"]
ghci> fmap (replicate 3) Nothing
Nothing
ghci> fmap (replicate 3) (Left "foo")
Left "foo"

Законы функторов

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

Закон 1

Первый закон функторов гласит, что если мы применяем функцию id к значению функтора, то значение функтора, которое мы получим, должно быть таким же, как первоначальное значение функтора. В немного более формальной это значит, что fmap id = id. По существу, это говорит, что если мы применим fmap id к значению функтора, это должно быть то же самое, что и просто применение id к значению. Вспомните, что id — это функция тождества, которая просто возвращает свой параметр неизменным. Она также может быть записана в виде \x -> x. Если воспринимать значение функтора как что-то, что может быть отображено, то закон fmap id = id выглядит довольно тривиально и очевидно.

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

ghci> fmap id (Just 3)
Just 3
ghci> id (Just 3)
Just 3
ghci> fmap id [1..5]
[1,2,3,4,5]
ghci> id [1..5]
[1,2,3,4,5]
ghci> fmap id []
[]
ghci> fmap id Nothing
Nothing

Если посмотреть на реализацию fmap, например, для Maybe, мы можем понять, почему выполняется первый закон функторов:

instance Functor Maybe where
    fmap f (Just x) = Just (f x)
    fmap f Nothing = Nothing

Мы представляем, что id играет роль параметраf в этой реализации. Нам видно, что если мы применяем fmap id к Just x, то результатом будет Just (id x), и поскольку id просто возвращает свой параметр, мы можем сделать вывод, что Just (id x) равно Just x. Поэтому теперь нам известно, что если мы применим id к значению Maybe, созданному с помощью конструктора значений Just, обратно мы получаем то же самое значение.

Видеть, что применение id к Nothing возвращает то же самое значение, тривиально. Поэтому из этих двух равенств в реализации fmap нам видно, что закон fmap id = id соблюдается.

Закон 2

Второй закон говорит, что композиция двух функций и последующее применение результирующей функции к функтору должно давать такой же результат, что и применение первой функции к функтору, а затем применение другой функции. В формальной записи это значит, что fmap (f . g) = fmap f . fmap g. Или если записать по-другому, то для любого значения функтора x должно выполняться следующее: fmap (f . g) x = fmap f (fmap g x).

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

Мы можем выяснить, как второй закон выполняется по отношению к некоторому типу, посмотрев на реализацию fmap для этого типа, а затем использовав метод, который мы применяли, чтобы проверить, подчиняется ли Maybe первому закону. Итак, чтобы проверить, как второй закон функторов выполняется для Maybe, если мы применим fmap (f . g) к Nothing, мы получаем Nothing, потому что применение любой функции к Nothing дает Nothing. Если мы выполним fmap f (fmap g Nothing), мы получим Nothing по тем же причинам.

Довольно просто увидеть, как второй закон выполняется для Maybe, когда значение равно Nothing. Но что, если это значение Just? Ладно, если мы выполним fmap (f . g) (Just x), из реализации нам видно, что это реализовано как Just ((f . g) x), что аналогично Just (f (g x)). Если мы выполним fmap f (fmap g (Just x)), из реализации нам видно, что fmap g (Just x) это Just (g x). Следовательно, fmap f (fmap g (Just x)) равно fmap f (Just (g x)), а из реализации нам видно, что это равно Just (f (g x)).

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

Нарушение закона

Давайте посмотрим на патологичный пример конструктора типов, который является экземпляром класса типов Functor, но не является функтором, потому что он не выполняет законы. Скажем, что у нас есть следующий тип:

data CMaybe a = CNothing | CJust Int a deriving (Show)

C здесь обозначает счетчик. Это тип данных, который во многом похож на Maybe a, только часть Just содержит два поля вместо одного. Первое поле в конструкторе значений CJust всегда будет иметь тип Int, и оно будет своего рода счётчиком. А второе поле имеет тип a, который берется из параметра типа, и его тип будет зависеть от конкретного типа, который мы выберем для CMaybe a. Давайте поиграем с нашим новым типом:

ghci> CNothing
CNothing
ghci> CJust 0 "haha"
CJust 0 "haha"
ghci> :t CNothing
CNothing :: CMaybe a
ghci> :t CJust 0 "haha"
CJust 0 "haha" :: CMaybe [Char]
ghci> CJust 100 [1,2,3]
CJust 100 [1,2,3]

Если мы используем конструктор CNothing, в нём нет полей. Если мы используем конструктор CJust, первое поле является целым числом, а второе — может быть любого типа. Давайте сделаем этот тип экземпляром Functor, так чтобы каждый раз, когда мы используем fmap, функция применялась ко второму полю, а первое поле увеличивалось на 1.

instance Functor CMaybe where
    fmap f CNothing = CNothing
    fmap f (CJust counter x) = CJust (counter+1) (f x)

Это отчасти похоже на реализацию экземпляра для Maybe, только когда мы применяем fmap к значению, которое не представляет пустую коробку (значение CJust), мы не просто применяем функцию к содержимому, мы также увеличиваем счетчик на 1. Пока вроде всё круто. Мы даже можем немного поиграть с этим:

ghci> fmap (++"ha") (CJust 0 "ho")
CJust 1 "hoha"
ghci> fmap (++"he") (fmap (++"ha") (CJust 0 "ho"))
CJust 2 "hohahe"
ghci> fmap (++"blah") CNothing
CNothing

Подчиняется ли этот тип законам функторов? Для того, чтобы увидеть, что что-то не подчиняется закону, достаточно найти всего один контрпример.

ghci> fmap id (CJust 0 "haha")
CJust 1 "haha"
ghci> id (CJust 0 "haha")
CJust 0 "haha"

Как гласит первый закон функторов, если мы отобразим значение функтора с помощью id, это должно быть то же самое, что и просто вызов id с тем же значением функтора. Наш пример показывает, что это не относится к нашему функтору CMaybe. Хотя он и является частью класса типов Functor, он не подчиняется данному закону функторов и, следовательно, не является функтором.

Поскольку CMaybe не является функтором, хотя он и притворяется таковым, использование его в качестве функтора может привести к неисправному коду. Когда мы используем функтор, не должно иметь значения, производим ли мы сначала композицию нескольких функций, а затем с ее помощью отображаем значение функтора, или же мы просто отображаем значение функтора последовательно с помощью каждой функции. Но при использовании CMaybe это имеет значение, так как он следит, сколько раз его отобразили. Не круто! Если мы хотим, чтобы CMaybe подчинялся законам функторов, мы должны сделать так, чтобы поле Int не изменялось, когда мы используем fmap.

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

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

Использование аппликативных функторов

В этом разделе мы рассмотрим аппликативные функторы, которые являются расширенными функторами.

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

Если у нас есть Just 3 и мы выполняем fmap (*) (Just 3), что мы получим? Из реализации экземпляра Maybe для Functor мы знаем, что если это значение Just, функция будет применена к значению внутри Just. Следовательно выполнение fmap (*) (Just 3) вернет Just ((*) 3), что может быть так же записано в виде Just (3 *), если мы используем секции. Интересно! Мы получаем функцию, обернутую в Just!

Вот еще несколько функций внутри значений функторов:

ghci> :t fmap (++) (Just "hey")
fmap (++) (Just "hey") :: Maybe ([Char] -> [Char])
ghci> :t fmap compare (Just 'a')
fmap compare (Just 'a') :: Maybe (Char -> Ordering)
ghci> :t fmap compare "A LIST OF CHARS"
fmap compare "A LIST OF CHARS" :: [Char -> Ordering]
ghci> :t fmap (\x y z -> x + y / z) [3,4,5,6]
fmap (\x y z -> x + y / z) [3,4,5,6] :: (Fractional a) => [a -> a -> a]

Если мы отображаем список символов с помощью compare, которая имеет тип (Ord a) => a -> a -> Ordering, мы получаем список функций типа Char -> Ordering, потому что функция compare частично применяется с помощью символов в списке. Это не список функций типа (Ord a) => a -> Ordering, так как первая примененная a имела тип Char, а потому и вторая a обязана принять решение о том, чтобы иметь тип Char.

Мы видим, как отображая значения функторов с помощью «многопараметрических» функций, мы получаем значения функторов, которые содержат внутри себя функции. Так что мы теперь можем с ними делать? Например, мы можем отображать их с помощью функций, которые принимают эти функции в качестве параметров, потому что независимо от того, что находится в значении функтора, оно будет передано функции, с помощью которой мы отображаем его, в качестве параметра.

ghci> let a = fmap (*) [1,2,3,4]
ghci> :t a
a :: [Integer -> Integer]
ghci> fmap (\f -> f 9) a
[9,18,27,36]

Но что, если у нас есть значение функтора Just (3 *) и значение функтора Just 5, и мы хотим извлечь функцию из Just (3 *) и отобразить с ее помощью Just 5? С обычными функторами у нас этого не получится, потому что они поддерживают только отображение имеющихся функторов с помощью обычных функций. Даже когда мы отображали функтор, содержащий функции, с помощью \f -> f 9, мы просто отображали его с помощью обычной функции. Но используя то, что предлагает нам fmap, мы не можем с помощью функции, которая находится внутри значения функтора, отобразить другое значение функтора. Мы могли бы произвести сопоставление конструктора Just по образцу для извлечения из него функции, а затем отобразить с ее помощью Just 5, но мы ищем более общий и абстрактный подход, работающий с функторами.

Поприветствуйте аппликативные функторы

Встречайте класс типов Applicative, находящийся в модуле Control.Applicative. Он определяет две функции: pure и <*>. Он не предоставляет реализации по умолчанию для какой-либо из этих функций, поэтому нам придется определить их обе, если мы хотим чтобы что-то стало аппликативным функтором. Этот класс определён вот так:

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

Это простое определение класса из трех строк говорит нам о многом! Первая строка начинается с определения класса Applicative, и она также вводит ограничение класса. Ограничение говорит, что если мы хотим сделать конструктор типа частью класса типов Applicative, он, прежде всего, должен принадлежать классу типов Functor. Вот почему когда нам известно, что конструктор типа принадлежит классу типов Applicative, он также принадлежит классу типов Functor, так что мы можем применять к нему fmap.

Первый метод, который он определяет, называется pure. Его объявление типа выглядит как pure :: a -> f a. f играет здесь роль нашего экземпляра аппликативного функтора. Так как Хаскель обладает очень хорошей системой типов, и так как все, что может делать функция — это получать некоторые параметры и возвращать некоторое значение, мы можем многое сказать по объявлению типа, и этот тип — не исключение.

pure должна принимать значение любого типа и возвращать аппликативное значение с этим значением внутри него. Словосочетание «внутри него», опять ссылается на нашу аналогию с коробкой, хотя мы и видели, что она не всегда выдерживает проверку. Но тип a -> f a все равно довольно нагляден. Мы берем значение и оборачиваем его в аппликативное значение, которое содержит в себе это значение в качестве результата. Более лучший способ представить себе pure — это сказать, что она берет значение и помещает его в некий контекст по умолчанию (или чистый контекст) — минимальный контекст, который по-прежнему возвращает это значение.

Функция <*> действительно интересная. У нее вот такое определение типа:

f (a -> b) -> f a -> f b

Напоминает ли оно вам что-нибудь? Оно похоже на fmap :: (a -> b) -> f a -> f b. Вы можете воспринимать функцию <*> как разновидность расширенной fmap. Тогда как fmap принимает функцию и значение функтора, и применяет функцию внутри значения функтора, <*> принимает значение функтора, который содержит в себе функцию, и другой функтор, и извлекает эту функцию из первого функтора, отображая затем второй функтор с ее помощью.

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

Давайте взглянем на реализацию экземпляра Applicative для Maybe:

instance Applicative Maybe where
    pure = Just
    Nothing <*> _ = Nothing
    (Just f) <*> something = fmap f something

Опять же, из определения класса мы видим, что f, которая играет роль аппликативного функтора, должна принимать один конкретный тип в качестве параметра, поэтому мы пишем instance Applicative Maybe where вместо instance Applicative (Maybe a) where.

Далее, у нас есть pure. Вспомните, что функция должна принять что-то и обернуть это в аппликативное значение. Мы написали pure = Just, потому что конструкторы значений вроде Just являются обычными функциями. Мы также могли бы написать pure x = Just x.

Наконец, у нас есть определение <*>. Мы не можем извлечь функцию из Nothing, потому что внутри него нет функции. Поэтому мы говорим, что если мы пробуем извлечь функцию из Nothing, результатом будет Nothing.

В определении класса Applicative есть ограничение класса Functor, что значит, что мы можем считать, что оба параметра функции <*> являются значениями функтора. Если первым аргументом является не Nothing, а Just с некоторой функцией внутри, тогда мы говорим, что с помощью этой функции мы хотим отобразить второй параметр. Этот код также заботится о случае, когда вторым аргументом является Nothing, потому что отображение Nothing с помощью любой функции, используя fmap, вернет Nothing. Итак, в случае с Maybe функция <*> извлекает функцию из значения слева, если это Just, и отображает с ее помощью значение справа. Если какой-либо из параметров является Nothing, то результатом будет Nothing.

Теперь давайте это опробуем:

ghci> Just (+3) <*> Just 9
Just 12
ghci> pure (+3) <*> Just 10
Just 13
ghci> pure (+3) <*> Just 9
Just 12
ghci> Just (++"hahah") <*> Nothing
Nothing
ghci> Nothing <*> Just "woot"
Nothing

Вы видите, что выполнение pure (+3) и Just (+3) в данном случае — это одно и то же. Используйте pure, если вы имеете дело со значениями Maybe в аппликативном контексте (используете их с <*>); в противном случае придерживайтесь использования Just.

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

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

Аппликативный стиль

При использовании класса типов Applicative мы можем поместить использование функции <*> в цепочку, что позволяет нам легко работать сразу с несколькими аппликативными значениями, а не только с одним. Взгляните, например, на это:

ghci> pure (+) <*> Just 3 <*> Just 5
Just 8
ghci> pure (+) <*> Just 3 <*> Nothing
Nothing
ghci> pure (+) <*> Nothing <*> Just 5
Nothing

Мы обернули функцию + в аппликативное значение, а затем использовали <*>, чтобы вызвать ее с двумя параметрами, оба из которых являются аппликативными значениями.

Давайте посмотрим, как это происходит, шаг за шагом. <*> левоассоциативна, что значит, что это:

pure (+) <*> Just 3 <*> Just 5

то же самое, что и вот это:

(pure (+) <*> Just 3) <*> Just 5

Сначала функция + помещается в аппликативное значение — в данном случае значение Maybe, которое содержит функцию. Итак, у нас есть pure (+), что по сути равно Just (+). Далее, происходит вызов Just (+) <*> Just 3. Его результатом является Just (3+). Это из-за частичного применения. Применение только 3 к функции + возвращает в результате функцию, которая принимает один параметр и добавляет к нему 3. Наконец, выполняется Just (3+) <*> Just 5, что в результате возвращает Just 8.

Ну разве не здорово?! Аппликативные функторы и аппликативный стиль вычисления pure f <*> x <*> y <*> ... позволяют взять функцию, которая ожидает параметры, не являющиеся аппликативными значениями, и использовать эту функцию для работы с несколькими аппликативными значениями. Функция может принимать столько параметров, сколько мы захотим, потому что она всегда частично применяется шаг за шагом между вхождениями<*>.

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

(<$>) :: (Functor f) => (a -> b) -> f a -> f b
f <$> x = fmap f x

ПРИМЕЧАНИЕ: Вспомните, что переменные типов не зависят от имен параметров или имен других значений. Здесь f в объявлении функции является переменной типа с ограничением класса, которое говорит, что любой конструктор типа, который заменяет f, должен входить в класс типов Functor. f в теле функции обозначает функцию, с помощью которой мы отображаем x. Тот факт, что мы использовали f для представления обоих вещей не означает, что они представляют одну и ту же вещь.

При использовании <$> аппликативный стиль проявляет себя во всей красе, потому что теперь если мы хотим применить функцию f к трем аппликативным значениям, мы можем просто написать f <$> x <*> y <*> z. Если бы параметры были обычными значениями, мы бы написали f x y z.

Давайте подробнее рассмотрим, как это работает. Предположим, что мы хотим соединить значения Just "johntra" и Just "volta" в одну строку, находящуюся внутри функтора Maybe. Мы можем это сделать:

ghci> (++) <$> Just "johntra" <*> Just "volta"
Just "johntravolta"

Перед тем, как мы увидим как это происходит, сравните предыдущую строку с этой:

ghci> (++) "johntra" "volta"
"johntravolta"

Чтобы использовать обычную функцию с аппликативным функторам, просто разбросайте вокруг несколько <$> и <*>, и функция будет работать с аппликативными значениями и возвращать аппликативное значение. Ну не здорово ли?

Возвращаясь к нашей (++) <$> Just "johntra" <*> Just "volta": Сначала (++), которая имеет тип (++) :: [a] -> [a] -> [a] отображает Just "johntra". Это дает в результате значение такое же, как Just ("johntra"++), и имеющее тип Maybe ([Char] -> [Char]). Заметьте, как первый параметр функции (++) был съеден и как a превратились в значения Char. А теперь выполняется выражение Just ("johntra"++) <*> Just "volta", которое извлекает функцию из Just и отображает с ее помощью Just "volta", что в результате дает Just "johntravolta". Если бы одним из двух значений было Nothing, результатом также было бы Nothing.

Списки

Списки (на самом деле конструктор типа списка, []) являются аппликативными функторами. Вот так сюрприз! А вот как [] является экземпляром Applicative:

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

Вспомните, что pure принимает значение и помещает его в контекст по умолчанию. Другими словами, она помещает его в минимальный контекст, который все еще возвращает это значение. Минимальным контекстом для списков был бы пустой список, но пустой список означает отсутствие значения, поэтому он не может содержать в себе значение, к которому мы применили pure. Вот почему pure принимает значение и помещает его в одноэлементный список. Подобным образом, минимальным контекстом для аппликативного функтора Maybe было бы Nothing, но оно означает отсутствие значения вместо самого значения, поэтому pure в реализации экземпляра для Maybe реализована как Just.

Вот pure в действии:

ghci> pure "Hey" :: [String]
["Hey"]
ghci> pure "Hey" :: Maybe String
Just "Hey"

Что насчет <*>? Если бы тип функции <*> ограничивался бы только списками, мы получили бы (<*>) :: [a -> b] -> [a] -> [b]. Данная функция реализована через генератор списка. <*> должна каким-то образом извлечь функцию из своего левого параметра, а затем отобразить с ее помощью правый параметр. Но левый список может не содержать в себе функций, содержать одну функцию, либо несколько функций, а правый список может также содержать несколько значений. Вот почему мы используем генератор списка для извлечения из обоих списков. Мы применяем каждую возможную функцию из левого списка к каждому возможному значению из правого списка. Результирующий список содержит все возможные комбинации применения функции из левого списка к значению из правого.

Мы можем использовать <*> со списками вот так:

ghci> [(*0),(+100),(^2)] <*> [1,2,3]
[0,0,0,101,102,103,1,4,9]

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

В следующем примере мы применяем две функции между двумя списками:

ghci> [(+),(*)] <*> [1,2] <*> [3,4]
[4,5,5,6,3,4,6,8]

<*> левоассоциативна, поэтому сначала выполняется [(+),(*)] <*> [1,2], результатом чего является список такой же, как [(1+),(2+),(1*),(2*)], потому что каждая функция слева применяется к каждому значению справа. Затем выполняется [(1+),(2+),(1*),(2*)] <*> [3,4], что возвращает окончательный результат.

Как здорово использовать аппликативный стиль со списками!

ghci> (++) <$> ["ha","heh","hmm"] <*> ["?","!","."]
["ha?","ha!","ha.","heh?","heh!","heh.","hmm?","hmm!","hmm."]

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

Вы можете воспринимать списки как недетерминированные вычисления. Значение вроде 100 или "what" можно рассматривать как детерминированное вычисление, которое имеет только один результат, тогда как список вроде [1,2,3] можно рассматривать как вычисление, которое не может определиться, какой результат оно желает иметь, поэтому оно возвращает нам все возможные результаты. Поэтому когда вы пишете что-то наподобие (+) <$> [1,2,3] <*> [4,5,6], вы можете рассматривать это как объединение двух недетерминированных вычислений с помощью + только для того, чтобы создать еще одно недетерминированное вычисление, которое еще меньше уверено в своем результате.

Использование аппликативного стиля со списками часто является хорошей заменой генераторам списков. В главе 1 мы хотели увидеть все возможные комбинации произведений [2,5,10] и [8,10,11], так что мы делали вот это:

ghci> [ x*y | x <- [2,5,10], y <- [8,10,11]]
[16,20,22,40,50,55,80,100,110]

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

ghci> (*) <$> [2,5,10] <*> [8,10,11]
[16,20,22,40,50,55,80,100,110]

Для меня такой подход более понятен, поскольку проще понять, что мы просто вызываем * между двумя недетерминированными вычислениями. Если мы захотели бы получить все возможные произведения элементов этих двух списков, больших 50, мы бы использовали следующее:

ghci> filter (>50) $ (*) <$> [2,5,10] <*> [8,10,11]
[55,80,100,110]

Легко увидеть, что вызов pure f <*> xs при использовании списков эквивалентен fmap f xs. pure f — это просто [f], а [f] <*> xs применит каждую функцию в левом списке к каждому значению в правом, но в левом списке только одна функция, потому это похоже на отображение.

IO тоже является аппликативным функтором

Другим экземпляром Applicative, с которым мы уже встречались, является IO. Вот как реализован этот экземпляр:

instance Applicative IO where
    pure = return
    a <*> b = do
    f <- a
    x <- b
    return (f x)

Поскольку суть pure состоит в помещении значения в минимальный контекст, который все еще содержит значение как результат, логично, что pure — это просто return. return создает действие ввода-вывода, которое ничего не делает. Оно просто возвращает какое-то значение в качестве своего результата, не производя никаких операций ввода-вывода вроде печати на терминал или чтения из файла.

Если бы <*> ограничивалась работой с IO, она бы имела тип (<*>) :: IO (a -> b) -> IO a -> IO b. В случае с IO она принимает действие ввода-вывода a, которое возвращает функцию, выполняет действие ввода-вывода и связывает эту функцию с f. Затем она выполняет действие ввода-вывода b и связывает его результат с x. Наконец, она применяет функцию f к x и возвращает результат этого применения в качестве результата. Чтобы это реализовать мы использовали здесь синтаксис do. (Вспомните, что суть синтаксиса do заключается в том, чтобы взять несколько действий ввода-вывода и склеить их вместе в одно действие.)

При использовании Maybe и [] мы могли бы воспринимать применение функции <*> как просто извлечение функции из ее левого параметра, а затем применение ее к правому параметру. В отношении IO извлечение остается в силе, но теперь у нас появляется понятие помещения в последовательность, поскольку мы берем два действия ввода-вывода и склеиваем их в одно. Мы должны извлечь функцию из первого действия ввода-вывода, но для того, чтобы извлечь результат из действия ввода-вывода, последнее должно быть выполнено. Рассмотрите вот это:

myAction :: IO String
myAction = do
    a <- getLine
    b <- getLine
    return $ a ++ b

Это действие ввода-вывода, которое запросит у пользователя две строки и вернет в качестве своего результата конкатенацию этих двух строк. Мы достигли это благодаря склеиванию вместе двух действий ввода-вывода getLine и return, поскольку мы хотели чтобы наше новое склеенное действие ввода-вывода содержало результат выполнения a ++ b. Еще один способ записать это состоит в использовании аппликативного стиля:

myAction :: IO String
myAction = (++) <$> getLine <*> getLine

Это то же, что мы делали ранее, когда мы создавали действие ввода-вывода, которое применяло функцию между результатами двух других действий ввода-вывода. Вспомните, что getLine — это действие ввода-вывода, которое имеет тип getLine :: IO String. Когда мы применяем <*> между двумя аппликативными значениями, результатом является аппликативное значение, так что все это имеет смысл.

Если мы вернёмся к аналогии с коробками, мы можем представить себе getLine как коробку, которая выйдет в реальный мир и принесёт нам строку. Выполнение (++) <$> getLine <*> getLine создаёт другую, бо'льшую коробку, которая посылает эти две коробки наружу для получения строк с терминала, а потом возвращает конкатенацию этих двух строк в качестве своего результата.

Выражение (++) <$> getLine <*> getLine имеет тип IO String. Это означает, что данное выражение является совершенно обычным действием ввода-вывода, как и любое другое, тоже возвращая результирующее значение, как и другие действия ввода-вывода. Вот почему мы можем выполнять подобные вещи:

main = do
    a <- (++) <$> getLine <*> getLine
    putStrLn $ "The two lines concatenated turn out to be: " ++ a

Функции в качестве аппликативных функторов

Еще одним экземпляром Applicative является (->) r или функции. Мы не часто используем функции в аппликативном стиле, но концепция тем не менее действительно интересна, поэтому давайте взглянем, как реализован экземпляр функции.

instance Applicative ((->) r) where
    pure x = (\_ -> x)
    f <*> g = \x -> f x (g x)

Когда мы оборачиваем значение в аппликативное значение с помощью pure, результат, который оно возвращает, должен быть этим значением. Минимальный контекст по умолчанию по-прежнему возвращает это значение в качестве результата. Вот почему в реализации экземпляра функции pure принимает значение и создает функцию, которая игнорирует передаваемый ей параметр и всегда возвращает это значение. Тип pure для экземпляра (->) r выглядит как pure :: a -> (r -> a).

ghci> (pure 3) "blah"
3

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

ghci> pure 3 "blah"
3

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

ghci> :t (+) <$> (+3) <*> (*100)
(+) <$> (+3) <*> (*100) :: (Num a) => a -> a
ghci> (+) <$> (+3) <*> (*100) $ 5
508

Вызов функции <*> с двумя аппликативными значениями возвращает аппликативное значение, поэтому если мы вызываем ее с двумя функциями, мы получаем функцию. Что же здесь происходит? Когда мы выполняем (+) <$> (+3) <*> (*100), мы создаем функцию, которая применит + к результатам выполнения функций (+3) и (*100) и вернет это значение. При вызове (+) <$> (+3) <*> (*100) $ 5, (+3) и (*100) сначала применяются к 5, что в результате дает 8 и 500. Затем + вызывается со значениями 8 и 500, что в результате дает 508.

Следующий код аналогичен:

ghci> (\x y z -> [x,y,z]) <$> (+3) <*> (*2) <*> (/2) $ 5
[8.0,10.0,2.5]

Мы создаем функцию, которая вызовет функцию \x y z -> [x, y, z] с окончательными результатами выполнения, возвращенными функциями (+3), (*2) и (/2). 5 передается каждой из трех функций, а затем с этими результатами вызывается \x y z -> [x, y, z].

ПРИМЕЧАНИЕ: Не так уж важно, поняли ли вы, как работает экземпляр (->) r для Applicative, так что не отчаивайтесь, если вам это не понятно сейчас. Поиграйте с аппликативным стилем и функциями, чтобы получить некоторое представление о том, как использовать функций в качестве аппликативных функторов.

Застегиваемые списки

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

Например, если мы выполним [(+3),(*2)] <*> [1,2], функция (+3) будет применена и к 1 и к 2, и функция (*2) также будет применена и к 1 и к 2, результатом чего будет список из четырех элементов: [4,5,2,4]. Однако, [(+3),(*2)] <*> [1,2] могла бы также работать таким образом, чтобы первая функция в списке слева была бы применена к первому значению в списке справа, вторая функция была бы применена ко второму значению, и т. д. Это вернуло бы список с двумя значениями: [4,4]. Вы могли бы представить его как [1 + 3, 2 * 2].

Экземпляром Applicative, с которым мы еще не встречались, является ZipList, и живет он в Control.Applicative.

Поскольку один тип не может иметь два экземпляра для одного и того же класса типов, был введен тип ZipList a, в котором имеется один конструктор (ZipList) с единственным полем (список). Вот экземпляр:

instance Applicative ZipList where
    pure x = ZipList (repeat x)
    ZipList fs <*> ZipList xs = ZipList (zipWith (\f x -> f x) fs xs)

<*> применяет первую функцию к первому значению, вторую функцию — ко второму значению, и т. д. Это делается с помощью zipWith (\f x -> f x) fs xs. Ввиду особенностей работы zipWith окончательный список будет той же длины, что и более короткий список из двух.

pure здесь также интересна. Она берет значение и помещает его в список, в котором это значение просто повторяется бесконечно. pure "haha" вернет ZipList (["haha","haha","haha".... Это могло бы сбить с толку, поскольку вы узнали, что pure должна помещать значение в минимальный контекст, который по-прежнему возвращает это значение. И вы могли бы подумать, что бесконечный список чего-либо едва ли является минимальным. Но это имеет смысл при использовании застегиваемых списков, так как значение должно производиться в каждой позиции. Это также удовлетворяет закону о том, что pure f <*> xs должно быть эквивалентно fmap f xs. Если бы вызов pure 3 просто вернул ZipList [3], вызов pure (*2) <*> ZipList [1,5,10] дал бы в результате ZipList [2], потому что длина результирующего списка из двух застегнутых списков равна длине более короткого списка из двух. Если мы застегнем конечный список с бесконечным, длина результирующего списка всегда будет равна длине конечного списка.

Так как же застегиваемые списки работают в аппликативном стиле? Давайте посмотрим. Ладно, тип ZipList a не имеет экземпляра Show, поэтому мы должны использовать функцию getZipList для извлечения сырого списка из застегиваемого списка:

ghci> getZipList $ (+) <$> ZipList [1,2,3] <*> ZipList [100,100,100]
[101,102,103]
ghci> getZipList $ (+) <$> ZipList [1,2,3] <*> ZipList [100,100..]
[101,102,103]
ghci> getZipList $ max <$> ZipList [1,2,3,4,5,3] <*> ZipList [5,3,1,2]
[5,3,3,4]
ghci> getZipList $ (,,) <$> ZipList "dog" <*> ZipList "cat" <*> ZipList "rat"
[('d','c','r'),('o','a','a'),('g','t','t')]

ПРИМЕЧАНИЕ: Функция (,,) — это то же самое, что \x y z -> (x,y,z). Также, функция (,) — это же самое, что \x y -> (x,y).

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

Аппликативные законы

Как и обычные функторы, аппликативные функторы несут с собой несколько законов. Самый главный закон состоит в том, чтобы выполнялось pure f <*> x = fmap f x. В качестве упражнения вы можете доказать выполнение этого закона для некоторых аппликативных функторов в этой главе. Ниже перечислены другие аппликативные законы:

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

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

Полезные функции для работы с аппликативными функторами

Control.Applicative определяет функцию, которая называется liftA2 и имеет следующий тип:

liftA2 :: (Applicative f) => (a -> b -> c) -> f a -> f b -> f c

Она определена вот так:

liftA2 :: (Applicative f) => (a -> b -> c) -> f a -> f b -> f c
liftA2 f a b = f <$> a <*> b

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

При использовании обыкновенных функторов мы можем просто отображать одно значение функтора с помощью функций. При использовании аппликативных функторов мы можем применять функцию между несколькими значениями функторов. Интересно также воспринимать тип этой функции в виде (a -> b -> c) -> (f a -> f b -> f c). Когда мы его воспринимаем подобным образом, мы можем сказать, что liftA2 берет обычную бинарную функцию и переводит ее в функцию, которая работает с двумя аппликативными значениями.

Есть интересная концепция: мы можем взять два аппликативных значения и объединить их в одно аппликативное значение, которое содержит в себе результаты этих двух аппликативных значений в списке. Например, у нас есть Just 3 и Just 4. Предположим, что второй функтор содержит одноэлементный список, так как это очень легко достичь:

ghci> fmap (\x -> [x]) (Just 4)
Just [4]

Хорошо, скажем, у нас есть Just 3 и Just [4]. Как нам получить Just [3,4]? Это просто:

ghci> liftA2 (:) (Just 3) (Just [4])
Just [3,4]
ghci> (:) <$> Just 3 <*> Just [4]
Just [3,4]

Вспомните, что : — это функция, которая принимает элемент и список и возвращает новый список с этим элементом в начале. Теперь, когда у нас есть Just [3,4], могли бы ли мы объединить это с Just 2, чтобы произвести Just [2,3,4]? Да, могли бы. Похоже, мы можем объединять любое количество аппликативных значений в одно аппликативное значение, которое содержит в себе список результатов этих аппликативных значений.

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

sequenceA :: (Applicative f) => [f a] -> f [a]
sequenceA [] = pure []
sequenceA (x:xs) = (:) <$> x <*> sequenceA xs

Аа, рекурсия! Прежде всего смотрим на тип. Он трансформирует список аппликативных значений в аппликативное значение со списком. После этого мы можем заложить некоторую основу для базового случая. Если мы хотим превратить пустой список в аппликативное значение со списком результатов, мы просто помещаем пустой список в контекст по умолчанию. Теперь в дело вступает рекурсия. Если у нас есть список с головой и хвостом (вспомните, x — это аппликативное значение, а xs — это список, состоящий из них), мы вызываем sequenceA с хвостом, что возвращает аппликативное значение со списком внутри него. Затем мы просто предваряем значением, содержащимся внутри аппликативного значения x, список, находящийся внутри этого аппликативного значения, вот именно!

Предположим, мы выполняем это:

sequenceA [Just 1, Just 2]

По определению это эквивалентно следующему:

(:) <$> Just 1 <*> sequenceA [Just 2]

Разбивая это далее, мы получаем:

(:) <$> Just 1 <*> ((:) <$> Just 2 <*> sequenceA [])

Мы знаем, что вызов sequenceA [] оканчивается в виде Just [], поэтому данное выражение теперь выглядит следующим образом:

(:) <$> Just 1 <*> ((:) <$> Just 2 <*> Just [])

что аналогично этому:

(:) <$> Just 1 <*> Just [2]

что равно Just [1,2]!

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

sequenceA :: (Applicative f) => [f a] -> f [a]
sequenceA = foldr (liftA2 (:)) (pure [])

Мы проходим список с конца, начиная со значением аккумулятора, равным pure []. Мы применяем liftA2 (:) между аккумулятором и последним элементом списка, что дает в результате аппликативное значение, содержащее в себе одноэлементный список. Затем мы вызываем liftA2 (:) с текущим в данный момент последним элементом и текущим аккумулятором, и т. д., до тех пор, пока у нас не останется только аккумулятор, который содержит список результатов всех аппликативных значений.

Давайте попробуем применить нашу функцию к какими-нибудь аппликативным значениям:

ghci> sequenceA [Just 3, Just 2, Just 1]
Just [3,2,1]
ghci> sequenceA [Just 3, Nothing, Just 1]
Nothing
ghci> sequenceA [(+3),(+2),(+1)] 3
[6,5,4]
ghci> sequenceA [[1,2,3],[4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]
ghci> sequenceA [[1,2,3],[4,5,6],[3,4,4],[]]
[]

При использовании со значениями Maybe, sequenceA создает значение Maybe, содержащее в себе все результаты в виде списка. Если одно из значений равно Nothing, тогда результатом тоже является Nothing. Это круто, когда у вас есть список значений Maybe, и вы заинтересованы в значениях только когда ни одно из них не равно Nothing.

При применении к функциям, sequenceA принимает список функций и возвращает функцию, которая возвращает список. В нашем примере мы создали функцию, которая приняла число в качестве параметра и применила его к каждой функции в списке, а затем вернула список результатов. sequenceA [(+3),(+2),(+1)] 3 вызовет (+3) с параметром 3, (+2) — с параметром 3, и (+1) — с параметром 3, и вернет все эти результаты в виде списка.

Выполнение (+) <$> (+3) <*> (*2) создаст функцию, которая принимает параметр, передает его и (+3) и (*2), а затем вызывает + с этими двумя результатами. В том же духе, есть смысл в том, что sequenceA [(+3),(*2)] создает функцию, которая принимает параметр и передает его всем функциям в списке. Вместо вызова + с результатами функций используется сочетание : и pure [] для накопления этих результатов в список, который является результатом этой функции.

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

ghci> map (\f -> f 7) [(>4),(<10),odd]
[True,True,True]
ghci> and $ map (\f -> f 7) [(>4),(<10),odd]
True

Вспомните, что and принимает список значений типа Bool и возвращает True, если все они равны True. Еще один способ достичь такой же результат — это применение sequenceA:

ghci> sequenceA [(>4),(<10),odd] 7
[True,True,True]
ghci> and $ sequenceA [(>4),(<10),odd] 7
True

sequenceA [(>4),(<10),odd] создает функцию, которая примет число и передаст его всем предикатам в [(>4),(<10),odd], и вернет список булевых значений. Она превращает список с типом (Num a) => [a -> Bool] в функцию с типом (Num a) => a -> [Bool]. Очень клёво, правда?

Поскольку списки однородны, все функции в списке должны быть одного и того же типа, конечно же. Вы не можете получить список вроде [ord, (+3)], потому что ord принимает символ и возвращает число, тогда как (+3) принимает число и возвращает число.

При использовании с [], sequenceA принимает список списков и возвращает список списков. На самом деле она создает списки, которые содержат все комбинации находящихся в них элементов. Для иллюстрации, вот предыдущий пример, выполненный с применением sequenceA, а затем выполненный с помощью генератора списков:

ghci> sequenceA [[1,2,3],[4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]
ghci> [[x,y] | x <- [1,2,3], y <- [4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]
ghci> sequenceA [[1,2],[3,4]]
[[1,3],[1,4],[2,3],[2,4]]
ghci> [[x,y] | x <- [1,2], y <- [3,4]]
[[1,3],[1,4],[2,3],[2,4]]
ghci> sequenceA [[1,2],[3,4],[5,6]]
[[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]
ghci> [[x,y,z] | x <- [1,2], y <- [3,4], z <- [5,6]]
[[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]

(+) <$> [1,2] <*> [4,5,6] возвращает в результате недетерминированное вычисление x + y, где x принимает каждое значение из [1,2], а y принимает каждое значение из [4,5,6]. Мы представляем это в виде списка, который содержит все возможные результаты. Аналогичным образом, когда мы выполняем sequenceA [[1,2],[3,4],[5,6]], результатом является недетерминированное вычисление [x,y,z], где x принимает каждое значение из [1,2], а y принимает каждое значение из [3,4] и т. д. Для представления результата этого недетерминированного вычисления мы используем список, где каждый элемент в списке является одним возможным списком. Вот почему результатом является список списков.

При использовании с действиями ввода-вывода, sequenceA — это то же самое, что и sequence! Она принимает список действий ввода-вывода и возвращает действие ввода-вывода, которое выполнит каждое из этих действий и в качестве своего результата будет содержать список результатов этих действий ввода-вывода. Это так, потому что чтобы превратить значение [IO a] в значение IO [a], чтобы создать действие ввода-вывода, возвращающее список результатов при выполнении, все эти действия ввода-вывода должны быть помещены в последовательность для того, чтобы затем быть выполненными одно за другим, когда потребуется результат выполнения. Вы не можете получить результат действия ввода-вывода, не выполнив его.

Давайте поместим три действия ввода-вывода getLine в последовательность:

ghci> sequenceA [getLine, getLine, getLine]
heyh
ho
woo
["heyh","ho","woo"]

В заключение, аппликативные функторы не просто интересны, но они также полезны. Они позволяют нам объединять разные вычисления — как, например, вычисления ввода-вывода, недетерминированные вычисления, вычисления, которые могли окончиться неуспешно, и т. д., — используя аппликативный стиль. Просто используя <$> и <*>, мы можем применять обычные функции, чтобы единообразно работать с любым количеством аппликативных функторов и использовать преимущества семантики каждого из них.

Переводы предыдущих глав книги, которые требуют полной переработки (структуры и содержания):

Следующей на очереди к публикации — глава Моноиды. Пока надеюсь на конструктивные комментарии по улучшению содержания. Спасибо!

Теги:

Хабы:

Haskell