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

Модуль 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] эй

хо ух

["эй","хо","ух"]

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

 

МОНОИДЫ

В этой главе представлен ещё один полезный и интересный класс типов Monoid. Он существует для типов, значения которых могут быть объединены при помощи бинарной операции. Мы рассмот- рим, что именно представляют собой моноиды и что утверждают их законы. Затем рассмотрим некоторые моноиды в языке Haskell и обсудим, как они могут нам пригодиться.

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

 

Оборачивание существующего типа в новый тип

Пока что вы научились создавать свои алгеб- раические типы данных, используя ключевое слово data. Вы также увидели, как можно да- вать синонимы имеющимся типам с приме- нением ключевого слова type. В этом разделе мы рассмотрим, как создаются новые типы на основе имеющихся типов данных с использо- ванием ключевого слова newtype. И в первую очередь, конечно, поговорим о том, чем всё это может быть нам полезно.

 

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

ghci> [(+1),(*100),(*5)] <*> [1,2,3]

[2,3,4,100,200,300,5,10,15]

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

Но списки уже имеют экземпляр класса Applicative, поэтому как нам определить для списков второй экземпляр класса Applicative? Как вы узнали, для этой цели был введён тип ZipList a. Он имеет один конструктор данных ZipList, у которого только одно поле. Мы помещаем оборачиваемый нами список в это поле. Далее для типа ZipList определяется экземпляр класса Applicative, чтобы, когда нам понадобится использовать списки в качестве апплика- тивных функторов для застёгивания, мы могли просто обернуть их с помощью конструктора ZipList. Как только мы закончили, разво- рачиваем их с помощью getZipList:

ghci> getZipList $ ZipList [(+1),(*100),(*5)] <*> ZipList [1,2,3] [2,200,15]

Итак, какое отношение это имеет к ключевому слову newtype? Хорошо, подумайте, как бы мы могли написать объявление data для нашего типа ZipList a! Вот один из способов:

data ZipList a = ZipList [a]

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

 

data ZipList a = ZipList { getZipList:: [a] }

Это прекрасно смотрится и на самом деле работает очень хо- рошо. У нас было два способа сделать существующий тип экземпля- ром класса типов, поэтому мы использовали ключевое слово data, чтобы просто обернуть этот тип в другой, и сделали другой тип эк- земпляром вторым способом.

Ключевое слово newtype в языке Haskell создано специально для тех случаев, когда мы хотим просто взять один тип и обернуть его во что-либо, чтобы представить его как другой тип. В существую- щих сейчас библиотеках тип ZipList a определён вот так:

newtype ZipList a = ZipList { getZipList:: [a] }

Вместо ключевого слова data используется newtype. Теперь раз- берёмся, почему. Ну, к примеру, декларация newtype быстрее. Если вы используете ключевое слово data для оборачивания типа, появ- ляются «накладные расходы» на все эти оборачивания и разворачи- вания, когда ваша программа выполняется. Но если вы воспользо- вались ключевым словом newtype, язык Haskell знает, что вы просто применяете его для оборачивания существующего типа в новый тип (отсюда название), поскольку хотите, чтобы внутренне он остался тем же, но имел иной тип. По этой причине язык Haskell может избавиться от оборачивания и разворачивания, как только решит, какое значение какого типа.

Так почему бы всегда не использовать newtype вместо data? Ког- да вы создаёте новый тип из имеющегося типа, используя ключевое слово newtype, у вас может быть только один конструктор значения, который имеет только одно поле. Но с помощью ключевого слова data вы можете создавать типы данных, которые имеют несколько конструкторов значения, и каждый конструктор может иметь ноль или более полей:

data Profession = Fighter | Archer | Accountant data Race = Human | Elf | Orc | Goblin

data PlayerCharacter = PlayerCharacter Race Profession

При использовании ключевого слова newtype мы можем ис- пользовать ключевое слово deriving – точно так же, как мы бы де- лали это с декларацией data. Мы можем автоматически порождать

 

экземпляры для классов Eq, Ord, Enum, Bounded, Show и Read. Если мы породим экземпляр для класса типа, то оборачиваемый нами тип уже должен иметь экземпляр для данного класса типов. Это ло- гично, поскольку ключевое слово newtype всего лишь оборачивает существующий тип. Поэтому теперь мы сможем печатать и сравни- вать значения нашего нового типа, если сделаем следующее:

newtype CharList = CharList { getCharList:: [Char] } deriving (Eq, Show)

Давайте попробуем:

ghci> CharList "Вот что мы покажем!"

CharList {getCharList = "Вот что мы покажем!"} ghci> CharList "бенни" == CharList "бенни"

True

ghci> CharList "бенни" == CharList "устрицы" False

В данном конкретном случае использования ключевого слова

newtype конструктор данных имеет следующий тип:

CharList:: [Char] –> CharList

Он берёт значение типа [Char] и возвращает значение типа CharList. Из предыдущих примеров, где мы использовали конс- труктор данных CharList, видно, что действительно так оно и есть. И наоборот, функция getCharList, которая была автоматически сге- нерирована за нас (потому как мы использовали синтаксис записей с именованными полями в нашей декларации newtype), имеет сле- дующий тип:

getCharList:: CharList –> [Char]

Она берёт значение типа CharList и преобразует его в значение типа [Char]. Вы можете воспринимать это как оборачивание и раз- ворачивание, но также можете рассматривать это как преобразова- ние значений из одного типа в другой.