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

Один из способов сделать для конструктора типа экземпляр класса 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, мы можем производить всё те же свёртки, что и над списками: