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