Unknown - haskell-notes

Neg _

->tell ( Any True)

Adda b ->bi a b

Mula b ->bi a b

_

->pure ()

wherebi 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 Treea

= Node

{ rootLabel ::a

-- значение метки

, subForest :: Foresta

-- ноль или несколько дочерних деревьев

}

type Foresta =[ Treea]

Интересный тип. Тип Treeопределён через Forest, а Forestопределён через Tree. По этому типу мы

видим, что каждый узел содержит некоторое значение типа a, и список дочерних деревьев.

Составим дерево:

*Exp> :m Data.Tree

Prelude Data.Tree> lett a = Nodea []

Prelude Data.Tree> letlist a = Nodea []

Prelude Data.Tree> letbi v a b = Nodev [a, b]

Prelude Data.Tree> letun v a

= Nodev [a]

Prelude Data.Tree>

Prelude Data.Tree> lettree1 =bi 10 (un 2 $un 6 $list 7) (list 5)

Prelude Data.Tree> lettree2 =bi 12 tree1 (bi 8 tree1 tree1)

116 | Глава 7: Функторы и монады: примеры

Теперь составим функцию, которая будет обходить дерево, и собирать числа из заданного диапазона:

type Diapa =(a, a)

inDiap :: Orda => Diapa -> Treea ->[a]

inDiap d =execWriter .inDiap’ d

inDiap’ :: Orda => Diapa -> Treea -> Writer[a] ()

inDiap’ d ( Nodev xs) =pick d v *>mapM_ (inDiap’ d) xs

wherepick (a, b) v

|(a <=v) &&(v <=b)

=tell [v]

|otherwise

=pure ()

Как и раньше у нас две функции, одна выполняет вычисления, другая извлекает результат из Writer. В

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

тату, а если нет пропускаем его, добавляя нейтральный элемент (в функции pure). Обратите внимание на то

как мы обрабатываем список дочерних поддервьев. Функция mapM_ является аналогом функции mapM, Она ис-

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

списка. В нашем случае это накопление результата. Посмотрим на определение этой функции:

mapM_ :: Monadm =>(a ->m b) ->

[a] ->m ()

mapM_ f =sequence_ .map f

sequence_ :: Monadm =>[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).

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

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