Миран Липовача - Изучай 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!

Когда мы впервые заговорили о функторах в главе 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позволяет нам использовать с этими значениями, имеющими контекст, обычные функции, и этот контекст сохраняется. Взгляните на пример: