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

Функторы, аппликативные функторы и моноиды

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

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

Возвращаясь к функторам

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

Однако, вот краткое напоминание: функторы - это сущности, которые могут быть отображены друг в друга. Например - списки, объекты Maybe, деревья и т.п. В Haskell'е они описываются классом типов Functor, который содержит только один метод, fmap. Его тип fmap :: (a -> b) -> f a -> f b. Это определение говорит: дай мне функцию, которая принимает a и возвращает b и обертку содержащую a (или несколько a), и я верну обертку с b (или несколькими b) внутри. Это вроде применения функции к элементам внутри обертки.

Небольшой совет. Много раз аналогия с коробкой использовалась, чтобы дать вам представление о том, как работают функторы. Скорее всего, мы снова обратимся к ней при разговоре об аппликативных функторах и монадах. Вообще-то это неплохая начальная аналогия, но только если не принимать ее слишком буквально. Дело в том, что для некоторых функторов эта коробка настолько сплющивается, что ее не узнать. Более корректным термином для функтора был бы "вычислительный контекст". Контекст, который говорит о том, что вычисления могут вернуть результат или потерпеть неудачу (Maybe и Either a) или о том, что в вычисления вовлекаются множество величин (списки). Нечто этакое.

Если мы хотим сделать конструктор типа экземпляром Functor'а, он должен иметь вид * -> *, это означает, что он должен получать точно один конкретный тип как параметр типа. Например, Maybe может создавать экземпляры, так как он получает один параметр для создания конкретного типа, вроде Maybe Int или Maybe String. Если конструктор типа принимает два параметра, как Either, мы должны сделать частичное применение конструктора типов, пока он не будет получать только один параметр. Так что мы не можем написать Functor Either, но мы можем написать Functor (Either a); и если вообразить, что fmap только для Either a, то он бы имел тип map :: (b -> c) -> Either a b -> Either a c. Как вы видите, часть Either a фиксирована, так как Either a принимает только один параметр типа, тогда как только Either принимает два, так что fmap :: (b -> c) -> Either b -> Either действительно не имеет смысла.

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

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

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

instance Functor IO where

fmap f action = do

result <- action

return (f result)

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

Мы можем поиграться с этим, чтобы лучше понять. Это действительно довольно просто. Возьмите этот кусок кода:

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!"

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

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

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

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

import Data.Char

import Data.List

main = do line <- fmap (intersperse '-' . reverse . map toUpper) getLine

putStrLn line

$ runhaskell fmapping_io.hs

hello there

E-R-E-H-T- -O-L-L-E-H

Думаю, вы понимаете, что функция intersperse '-' . reverse . map toUpper берет строку, применяет toUpper к каждому символу, берет результат в обратном порядке и между каждым символом строки вставляет символ '-'. То же самое даст (\xs -> intersperse '-' (reverse (map toUpper xs))), но изначальный вариант еще и красив.

Другим экземпляром Functor, с которым мы все время имели дело, но не знали, что он является экземпляром Functor, является (->) r. Вы теперь, наверное, немного запутались, спрашивая "Что, черт возьми, означает (->) r?" Тип функции r -> a может быть переписан в виде (->) r a, так же как 2 + 3 может быть переписан в виде (+) 2 3. Когда мы представляем себе это как (->) r a, мы видим (->) немного в другом свете, потому что нам видно, что это просто конструктор типа, который принимает два параметра, как это делает Either. Но помните, мы сказали, что конструктор типов должен принимать в точности один параметр типа, чтобы его можно было сделать экземпляром Functor. Вот почему мы не можем сделать (->) экземпляром Functor, но если сделать частичное применение в виде (->) r, это не представляет каких-либо сложностей. Если бы синтаксис позволял частично применять конструкторы типов с помощью секций (как мы можем применить +, выполнив (2+), что аналогично (+) 2), вы могли бы записать (->) r как (r->). Каким образом функции являются функторами? Хорошо, давайте взглянем на реализацию, которая находится в Control.Monad.Instances.

Функции, которые что-то принимают и что-то возвращают, мы обычно обозначаем как a -> b. r -> a – это то же, мы только использовали другие буквы для переменных типов.

instance Functor ((->) r) where

fmap f g = (\x -> f (g x))

Если бы синтаксис позволял, это могло бы быть записано как

instance Functor (r ->) where

fmap f g = (\x -> f (g x))

Но он не позволяет, поэтому нам придётся писать в таком виде, как в первом примере.

Начнем с типа 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).

Хммм, хорошо. Проекция (mapping) одной функции на другую дает нам функцию, так же как проекция функции на Maybe должна давать Maybe, а проекция функции на список должна давать список. Так что же говорит нам тип fmap :: (a -> b) -> (r -> a) -> (r -> b)? Мы видим, что он берет функцию от a в b и функцию от r в a и выдает функцию от r в b. Ничего не напоминает? Вау! Композиция функций! Мы соединяем выход r -> a ко входу a -> b, чтоб получилась r -> b, что в точности выражение идеи композиции функций. Если взглянуть на экземпляр функтора, который мы определили выше, то видно что он просто композиция функций. Альтернативным способом записать этот экземпляр был бы:

instance Functor ((->) r) where

fmap = (.)

Эта запись делает очевидным, что использование fmap к функциям эквивалентно композиции. Выполните :m + 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 в инфиксной форме чтобы сходство с . стало очевидным. Во второй строке ввода мы отображаем (*3) над (+100) и в итоге получаем функцию, которая берет число, вызывает (+100) а затем (*3) с результатом. Мы вызываем полученную функцию с единицей.

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

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

Перед тем как перейти к правилам, которым должен следовать fmap, еще раз задумаемся о типе fmap. Его тип fmap :: (a -> b) -> f a -> f b. Мы опускаем ограничение на класс типов (Functor f) => просто для краткости, раз уж мы обсуждаем функторы, то нам понятно, что такое f. Когда мы рассматривали каррированые функции, мы отметили, что любая функция в Haskell-е ждет одного единственного параметра. Функция же a -> b -> c на самом деле берет параметр a и возвращает функцию b -> 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 или как о функции, которая принимает функцию и функтор и затем проецирует функцию на функтор, или какt о функции, которая берет функцию и поднимает эту функцию так, что она оперирует над функторами. Оба взгляда корректны и эквивалентны в Haskell.

Тип fmap (replicate 3) :: (Functor f) => f a -> f [a] означает, что функция будет работать с любым функтором. Что именно она будет делать, зависит от функцтора, с которым она будет использоваться. Если мы используем fmap (replicate 3) со списком, будет выбрана реализация fmap для списка (просто отображение). Если мы используем это с 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 должны следовать им. У Haskell нет автоматических проверок этого, так что вам нужно проверять это самостоятельно.

Первый закон функторов гласит, что если мы применяем функцию 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, мы поймем, почему первый закон функторов работает.