Изучай Haskell во имя добра! - Миран Липовача

Случай с непустым узлом чуть более интересен. Он содержит два поддерева, а также значение. В этом случае мы рекурсивно отображаем левое и правое поддеревья с помощью одной и той же функции f, используя рекурсивный вызов функции foldMap. Вспомните, что наша функция foldMap возвращает в результате одно моноидное значение. Мы также применяем нашу функцию f к значению в узле. Теперь у нас есть три моноидных значения (два из наших поддеревьев и одно – после применения f к значению в узле), и нам просто нужно соединить их. Для этой цели мы используем функцию mappend, и естественным образом левое поддерево идёт первым, затем – значение узла, а потом – правое поддерево[14].

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

Теперь, когда у нас есть экземпляр класса Foldable для нашего типа, представляющего дерево, мы получаем функции foldr и foldl даром! Рассмотрите вот это дерево:

testTree = Node 5

            (Node 3

               (Node 1 EmptyTree EmptyTree)

               (Node 6 EmptyTree EmptyTree)

            )

            (Node 9

               (Node 8 EmptyTree EmptyTree)

               (Node 10 EmptyTree EmptyTree)

            )

У него значение 5 в качестве его корня, а его левый узел содержит значение 3 со значениями 1 слева и 6 справа. Правый узел корня содержит значение 9, а затем значения 8 слева от него и 10 в самой дальней части справа. Используя экземпляр класса Foldable, мы можем производить всё те же свёртки, что и над списками:

ghci> F.foldl (+) 0 testTree

42

ghci> F.foldl (*) 1 testTree

64800

Функция foldMap полезна не только для создания новых экземпляров класса Foldable. Она также очень удобна для превращения нашей структуры в одно моноидное значение. Например, если мы хотим узнать, равно ли какое-либо из чисел нашего дерева 3, мы можем сделать следующее:

ghci> getAny $ F.foldMap (x –> Any $ x == 3) testTree

True

Здесь анонимная функция x –> Any $ x == 3 – это функция, которая принимает число и возвращает моноидное значение: значение Bool, обёрнутое в тип Any. Функция foldMap применяет эту функцию к каждому элементу нашего дерева, а затем превращает получившиеся моноиды в один моноид с помощью вызова функции mappend. Предположим, мы выполняем следующее:

ghci> getAny $ F.foldMap (x –> Any $ x > 15) testTree

False

Все узлы нашего дерева будут содержать значение Any False после того, как к ним будет применена анонимная функция. Но чтобы получить в итоге значение True, реализация функции mappend для типа Any должна принять по крайней мере одно значение True в качестве параметра. Поэтому окончательным результатом будет False, что логично, поскольку ни одно значение в нашем дереве не превышает 15.

Мы также можем легко превратить наше дерево в список, просто используя функцию foldMap с анонимной функцией x –> [x]. Сначала эта функция проецируется на наше дерево; каждый элемент становится одноэлементным списком. Действие функции mappend, которое имеет место между всеми этими одноэлементными списками, возвращает в результате один список, содержащий все элементы нашего дерева:

ghci> F.foldMap (x –> [x]) testTree

[1,3,6,5,8,9,10]

Самое классное, что все эти трюки не ограничиваются деревьями. Они применимы ко всем экземплярам класса Foldable!

13

Пригоршня монад

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

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

Совершенствуем наши аппликативные функторы

Когда мы начали с функторов, вы видели, что можно отображать разные типы данных с помощью функций, используя класс типов Functor. Введение в функторы заставило нас задаться вопросом: «Когда у нас есть функция типа a –> b и некоторый тип данных f a, как отобразить этот тип данных с помощью функции, чтобы получить значение типа f b?» Вы видели, как с помощью чего-либо отобразить Maybe a, список [a], IO a и т. д. Вы даже видели, как с помощью функции типа a –> b отобразить другие функции типа r –> a, чтобы получить функции типа r –> b. Чтобы ответить на вопрос о том, как отобразить некий тип данных с помощью функции, нам достаточно было взглянуть на тип функции fmap:

fmap :: (Functor f) => (a –> b) –> f a –> f b

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

Потом вы узнали, что возможно усовершенствование функторов, и у вас возникло ещё несколько вопросов. Что если эта функция типа a –> b уже обёрнута в значение функтора? Скажем, у нас есть Just (*3) – как применить это к значению Just 5? Или, может быть, не к Just 5, а к значению Nothing? Или, если у нас есть список [(*2),(+4)], как применить его к списку [1,2,3]? Как это вообще может работать?.. Для этого был введён класс типов Applicative:

(<*>) :: (Applicative f) => f (a –> b) –> f a –> f b

Вы также видели, что можно взять обычное значение и обернуть его в тип данных. Например, мы можем взять значение 1 и обернуть его так, чтобы оно превратилось в Just 1. Или можем превратить его в [1]. Оно могло бы даже стать действием ввода-вывода, которое ничего не делает, а просто выдаёт 1. Функция, которая за это отвечает, называется pure.

Аппликативное значение можно рассматривать как значение с добавленным контекстом – «причудливое» значение, выражаясь техническим языком. Например, буква 'a' – это просто обычная буква, тогда как значение Just 'a' обладает неким добавленным контекстом. Вместо типа Char у нас есть тип Maybe Char, который сообщает нам, что его значением может быть буква; но значением может также быть и отсутствие буквы. Класс типов Applicative позволяет нам использовать с этими значениями, имеющими контекст, обычные функции, и этот контекст сохраняется. Взгляните на пример:

ghci> (*) <$> Just 2 <*> Just 8

Just 16

ghci> (++) <$> Just "клингон" <*> Nothing

Nothing

ghci> (-) <$> [3,4] <*> [1,2,3]

[2,1,0,3,2,1]

Поэтому теперь, когда мы рассматриваем их как аппликативные значения, значения типа Maybe a представляют вычисления, которые могли окончиться неуспешно, значения типа [a] – вычисления, которые содержат несколько результатов (недетерминированные вычисления), значения типа IO a – вычисления, которые имеют побочные эффекты, и т. д.

Монады являются естественным продолжением аппликативных функторов и предоставляют решение для следующей проблемы: если у нас есть значение с контекстом типа m a, как нам применить к нему функцию, которая принимает обычное значение a и возвращает значение с контекстом? Другими словами, как нам применить функцию типа a –> m b к значению типа m a? По существу, нам нужна вот эта функция:

(>>=) :: (Monad m) => m a –> (a –> m b) –> m b

Если у нас есть причудливое значение и функция, которая принимает обычное значение, но возвращает причудливое, как нам передать это причудливое значение в данную функцию? Это является основной задачей при работе с монадами. Мы пишем m a вместо f a, потому что m означает Monad; но монады являются всего лишь аппликативными функторами, которые поддерживают операцию >>=. Функция >>= называется связыванием.

Когда у нас есть обычное значение типа a и обычная функция типа a –> b, передать значение функции легче лёгкого: мы применяем функцию к значению как обычно – вот и всё! Но когда мы имеем дело со значениями, находящимися в определённом контексте, нужно немного поразмыслить, чтобы понять, как эти причудливые значения передаются функциям и как учесть их поведение. Впрочем, вы сами убедитесь, что это так же просто, как раз, два, три.