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

Но что если тип содержимого типа Maybeне имеет экземпляра класса Monoid? Обратите внимание: в предыдущем объявлении экземпляра единственный случай, когда мы должны полагаться на то, что содержимые являются моноидами, – это когда оба параметра функции mappendобёрнуты в конструктор Just. Когда мы не знаем, являются ли содержимые моноидами, мы не можем использовать функцию mappendмежду ними; так что же нам делать? Ну, единственное, что мы можем сделать, – это отвергнуть второе значение и оставить первое. Для этой цели существует тип First a. Вот его определение:

newtype First a = First { getFirst :: Maybe a }

deriving (Eq, Ord, Read, Show)

Мы берём тип Maybe aи оборачиваем его с помощью декларации newtype. Экземпляр класса Monoidв данном случае выглядит следующим образом:

instance Monoid (Firsta) where

mempty = First Nothing

First (Just x) `mappend` _ = First (Just x)

First Nothing `mappend` x = x

Значение mempty– это просто Nothing, обёрнутое с помощью конструктора First. Если первый параметр функции mappendявляется значением Just, мы игнорируем второй. Если первый параметр – Nothing, тогда мы возвращаем второй параметр в качестве результата независимо от того, является ли он Justили Nothing:

ghci> getFirst $ First (Just 'a') `mappend` First (Just 'b')

Just 'a'

ghci> getFirst $ First Nothing `mappend` First (Just 'b')

Just 'b'

ghci> getFirst $ First (Just 'a') `mappend` First Nothing

Just 'a'

Тип Firstполезен, когда у нас есть множество значений типа Maybeи мы хотим знать, является ли какое-либо из них значением Just. Для этого годится функция mconcat:

ghci> getFirst . mconcat . map First $ [Nothing, Just 9, Just 10]

Just 9

Если нам нужен моноид на значениях Maybe a– такой, чтобы оставался второй параметр, когда оба параметра функции mappendявляются значениями Just, то модуль Data.Monoidпредоставляет тип Last a, который работает, как и тип First a, но при объединении с помощью функции mappendи использовании функции mconcatсохраняется последнее значение, не являющееся Nothing:

ghci> getLast . mconcat . map Last $ [Nothing, Just 9, Just 10]

Just 10

ghci> getLast $ Last (Just "один") `mappend` Last (Just "два")

Just "two"

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

Поскольку существует так много структур данных, которые хорошо работают со свёртками, был введён класс типов 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]

6

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

6

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

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

11

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.