Учебник по Haskell

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).

Само по себе явление обновления значения является побочным эффектом. Оно ломает представление о

статичности мира, у нас появляются фазы: до обновления и после обновления. Но представьте, что обнов-

ление происходит локально, мы постоянно меняем только одно значение, при этом за время обновления ни

одна другая переменная не может пользоваться промежуточными значениями и обновления происходят с

помощью чистых функций. Представьте функцию, которая принимает значение, выделяет внутри себя па-

мять, и при построении результата начинает обновлять значение внутри этой памяти (с помощью чистых

функций) и считать что-то ещё полезное на основе этих обновлений, как только вычисления закончатся, па-

мять стирается, и возвращается значение. Будет ли такая функция чистой? Интуиция подсказывает, что да.

Это было доказано, но для реализации этого требуется небольшой трюк на уровне типов. Получается, что

не смотря на то, что функция содержит побочные эффекты, она является чистой, поскольку все побочные

эффекты локальны, они происходят только внутри вызова функции и только в самой функции.

Для симуляции обновления значения в Haskell нам нужно решить две проблемы. Как упорядочить обнов-

ление значения? И как локализовать его? В императивных языках порядок вычисления выражений строго

связан с порядком следования выражений, на примитивном уровне, грубо упрощая, можно сказать, что вы-