, которая также является методом класса типов
>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 к значению в узле. Теперь у нас есть три моноидных значения (два из наших поддеревьев и одно – после применения