Neg a
-> un a
_
-> pure ()
where bi a b = countBiFuns’ a *> countBiFuns’ b
un
= countBiFuns’
tell :: Monoid a => a -> Writer a ()
tell a = Writer ((), a)
execWriter :: Writer msg a -> msg
execWriter (Writer (a, msg)) = msg
Первая функция countBiFuns извлекает значение из типов Writer и Sum. А вторая функция countBiFuns’
вычисляет значение.
Мы определили две вспомогательные функции tell, которая записывает сообщение в накопитель и
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, 
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).
Само по себе явление обновления значения является побочным эффектом. Оно ломает представление о
статичности мира, у нас появляются фазы: до обновления и после обновления. Но представьте, что обнов-
ление происходит локально, мы постоянно меняем только одно значение, при этом за время обновления ни
одна другая переменная не может пользоваться промежуточными значениями и обновления происходят с
помощью чистых функций. Представьте функцию, которая принимает значение, выделяет внутри себя па-
мять, и при построении результата начинает обновлять значение внутри этой памяти (с помощью чистых
функций) и считать что-то ещё полезное на основе этих обновлений, как только вычисления закончатся, па-
мять стирается, и возвращается значение. Будет ли такая функция чистой? Интуиция подсказывает, что да.
Это было доказано, но для реализации этого требуется небольшой трюк на уровне типов. Получается, что
не смотря на то, что функция содержит побочные эффекты, она является чистой, поскольку все побочные
эффекты локальны, они происходят только внутри вызова функции и только в самой функции.
Для симуляции обновления значения в Haskell нам нужно решить две проблемы. Как упорядочить обнов-
ление значения? И как локализовать его? В императивных языках порядок вычисления выражений строго
связан с порядком следования выражений, на примитивном уровне, грубо упрощая, можно сказать, что вы-
числитель читает код как ленту и выполняет выражение за выражением. В Haskell всё совсем по-другому. Мы
можем писать функции в любом порядке, также в любом порядке мы можем объявлять локальные перемен-
ные в where или let-выражениях. Компилятор определяет порядок редукции синонимов по функциональным
