Свёртка на моноидах

Один из интересных способов ввести моноиды в работу заключается в том, чтобы они помогали нам определять свёртки над различными структурами данных. До сих пор мы производили свёртки только над списками, но списки – не единственная структура данных, которую можно свернуть. Мы можем определять свёртки почти над любой структурой данных. Особенно хорошо поддаются свёртке деревья.

Поскольку существует так много структур данных, которые хорошо работают со свёртками, был введён класс типов Foldable. Подобно тому как класс Functor предназначен для сущностей, которые можно отображать, класс Foldable предназначен для вещей, которые могут быть свёрнуты! Его можно найти в модуле Data.Foldable; и, поскольку он экспортирует функции, имена которых конфликтуют с именами функций из модуля Prelude, его лучше импортировать, квалифицируя (и подавать с базиликом!):

import qualified Data.Foldable as F

Чтобы сэкономить драгоценные нажатия клавиш, мы импортировали его, квалифицируя как F.

Так какие из некоторых функций определяет этот класс типов? Среди них есть функции foldr, foldl, foldr1 и foldl1. Ну и?.. Мы уже давно знакомы с ними! Что ж в этом нового? Давайте сравним типы функции foldr из модуля Foldable и одноимённой функции из модуля Prelude, чтобы узнать, чем они отличаются:

ghci> :t foldr

foldr :: (a –> b –> b) –> b –> [a] –> b

ghci> :t F.foldr

F.foldr :: (F.Foldable t) => (a –> b –> b) –> b –> t a –> b

А-а-а! Значит, в то время как функция foldr принимает список и сворачивает его, функция foldr из модуля Data.Foldable принимает любой тип, который можно свернуть, – не только списки! Как и ожидалось, обе функции foldr делают со списками одно и то же:

ghci> foldr (*) 1 [1,2,3]

ghci> F.foldr (*) 1 [1,2,3]

Другой структурой данных, поддерживающей свёртку, является Maybe, которую мы все знаем и любим!

ghci> F.foldl (+) 2 (Just 9)

ghci> F.foldr (||) False (Just True)

True

Но сворачивание значения Maybe не очень-то интересно. Оно действует просто как список с одним элементом, если это значение Just, и как пустой список, если это значение Nothing. Давайте рассмотрим чуть более сложную структуру данных.

Помните древовидную структуру данных из главы 7? Мы определили её так:

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)

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

Один из способов сделать для конструктора типа экземпляр класса Foldable состоит в том, чтобы просто напрямую реализовать для него функцию foldr. Но другой, часто более простой способ состоит в том, чтобы реализовать функцию foldMap, которая также является методом класса типов Foldable. У неё следующий тип:

foldMap :: (Monoid m, Foldable t) => (a –> m) –> t a –> m

Её первым параметром является функция, принимающая значение того типа, который содержит наша сворачиваемая структура (обозначен здесь как a), и возвращающая моноидное значение. Второй её параметр – сворачиваемая структура, содержащая значения типа a. Эта функция отображает структуру с помощью заданной функции, таким образом, производя сворачиваемую структуру, которая содержит моноидные значения. Затем, объединяя эти моноидные значения с помощью функции mappend, она сводит их все в одно моноидное значение. На данный момент функция может показаться несколько странной, но вы увидите, что её очень просто реализовать. И такой реализации достаточно, чтобы определить для нашего типа экземпляр класса Foldable! Поэтому если мы просто реализуем функцию foldMap для какого-либо типа, то получаем функции foldr и foldl для этого типа даром!

Вот как мы делаем экземпляр класса Foldable для типа:

instance F.Foldable Tree where

foldMap f EmptyTree = mempty

foldMap f (Node x l r) = F.foldMap f l `mappend`

f x `mappend`

F.foldMap f r

Если нам предоставлена функция, которая принимает элемент нашего дерева и возвращает моноидное значение, то как превратить наше целое дерево в одно моноидное значение? Когда мы использовали функцию fmap с нашим деревом, мы применяли функцию, отображая с её помощью узел, а затем рекурсивно отображали с помощью этой функции левое поддерево, а также правое поддерево. Здесь наша задача состоит не только в отображении с помощью функции, но также и в соединении значений в одно моноидное значение с использованием функции mappend. Сначала мы рассматриваем случай с пустым деревом – печальным и одиноким деревцем, у которого нет никаких значений или поддеревьев. Оно не содержит значений, которые мы можем предоставить нашей функции, создающей моноид, поэтому мы просто говорим, что если наше дерево пусто, то моноидное значение, в которое оно будет превращено, равно значению mempty.

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

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!