execWriter, которая возвращает лишь сообщение. Это стандартные для Writer функции.
Посмотрим как работает эта функция:
*Exp> countBiFuns (n 2)
0
*Exp> countBiFuns (n 2 + n 1 + 2 + 3)
3
Накопление результата | 115
Накопление логических значений
В модуле Data.Monoid определены два типа для накопления логических значений. Это типы All и Any. С
помощью типа All мы можем проверить выполняется ли некоторое свойство для всех значений. А с помощью
типа Any мы можем узнать, что существует хотя бы один элемент, для которых это свойство выполнено.
Посмотрим на определение экземпляров класса Monoid для этих типов:
newtype All = All { getAll :: Bool }
instance Monoid All where
mempty = All True
All x ‘mappend‘ All y = All (x && y)
В типе All мы накапливаем значения с помощью логического “и”. Нейтральным элементом является кон-
структор True. Итоговое значение накопителя будет равно True только в том случае, если все накапливаемые
сообщения были равны True.
В типе Any всё наоборот:
instance Monoid Any where
mempty = Any False
Any x ‘mappend‘ Any y = Any (x || y)
Посмотрим как работают эти типы. Составим функцию, которая проверяет отсутствие оператора минус
в выражении:
noNeg :: Exp -> Bool
noNeg = not . getAny . execWriter . anyNeg
anyNeg :: Exp -> Writer Any ()
anyNeg x = case x of
Neg _
-> tell (Any True)
Add a b -> bi a b
Mul a b -> bi a b
_
-> pure ()
where bi a b = anyNeg a *> anyNeg b
Функция anyNeg проверяет есть ли в выражении хотя бы один конструктор Neg. В функции noNeg мы
извлекаем результат и берём его отрицание, чтобы убедиться в том что в выражении не встретилось ни
одного конструктора Neg.
*Exp> noNeg (n 2 + n 1 + 2 + 3)
True
*Exp> noNeg (n 2 — n 1 + 2 + 3)
False
Накопление списков
Экземпляр класса Monoid определён и для списков. Предположим у нас есть дерево, в каждом узле кото-
рого находятся числа, давайте соберём все числа больше 5, но меньше 10. Деревья мы возьмём из модуля
Data.Tree:
data Tree a
= Node
{ rootLabel :: a
— значение метки
, subForest :: Forest a
— ноль или несколько дочерних деревьев
}
type Forest a = [Tree a]
Интересный тип. Тип Tree определён через Forest, а Forest определён через Tree. По этому типу мы
видим, что каждый узел содержит некоторое значение типа a, и список дочерних деревьев.
Составим дерево:
*Exp> :m Data.Tree
Prelude Data.Tree> let t a = Node a []
Prelude Data.Tree> let list a = Node a []
Prelude Data.Tree> let bi v a b = Node v [a, b]
Prelude Data.Tree> let un v a
= Node v [a]
Prelude Data.Tree>
Prelude Data.Tree> let tree1 = bi 10 (un 2 $ un 6 $ list 7) (list 5)
Prelude Data.Tree> let tree2 = bi 12 tree1 (bi 8 tree1 tree1)
116 | Глава 7: Функторы и монады: примеры
Теперь составим функцию, которая будет обходить дерево, и собирать числа из заданного диапазона:
type Diap a = (a, a)
inDiap :: Ord a => Diap a -> Tree a -> [a]
inDiap d = execWriter . inDiap’ d
inDiap’ :: Ord a => Diap a -> Tree a -> Writer [a] ()
inDiap’ d (Node v xs) = pick d v *> mapM_ (inDiap’ d) xs
where pick (a, b) v
| (a <= v) && (v <= b)
= tell [v]
| otherwise
= pure ()
Как и раньше у нас две функции, одна выполняет вычисления, другая извлекает результат из Writer. В
функции pick мы проверяем число на принадлежность интервалу, если это так мы добавляем число к резуль-
тату, а если нет пропускаем его, добавляя нейтральный элемент (в функции pure). Обратите внимание на то
как мы обрабатываем список дочерних поддервьев. Функция mapM_ является аналогом функции mapM, Она ис-
пользуется, если результат функции не важен, а важны те действия, которые происходят при преобразовании
списка. В нашем случае это накопление результата. Посмотрим на определение этой функции:
mapM_ :: Monad m => (a -> m b) ->
[a] -> m ()
mapM_ f = sequence_ . map f
sequence_ :: Monad m => [m a] -> m ()
sequence_ = foldr (>> ) (return ())
Основное отличие состоит в функции sequence_. Раньше мы собирали значения в список, а теперь отбра-
сываем их с помощью константной функции >> . В конце мы возвращаем значение единичного типа ().
Теперь сохраним в модуле Tree определение функции и вспомогательные функции создания деревьев
un, bi, и list и посмотрим как наша функция работает:
*Tree> inDiap (4, 10) tree2
[10,6,7,5,8,10,6,7,5,10,6,7,5]
*Tree> inDiap (5, 8) tree2
[6,7,5,8,6,7,5,6,7,5]
*Tree> inDiap (0, 3) tree2
[2,2,2]
7.5 Монада изменяемых значений ST
Возможно читатели, для которых “родным” является один из императивных языков, немного заскучали
по изменяемым значениям. Мы говорили, что в Haskell ничего не изменяется, мы даём всё более и более
сложные имена статическим значениям, а потом вычислитель редуцирует имена к настоящим значениям.
Но есть алгоритмы, которые очень элегантно описываются в терминах изменяемых значений. Примером
такого алгоритма может быть быстрая сортировка. Задача состоит в перестановке элементов массива так,
чтобы на выходе любой последующий элемент массива был больше предыдущего (для списков эту задачу
решают функции sort и sortBy).
Само по себе явление обновления значения является побочным эффектом. Оно ломает представление о