qsort xs = elems $ runSTArray $ do
arr <- newListArray (left, right) xs
qsortST left right arr
return arr
where left
= 0
122 | Глава 7: Функторы и монады: примеры
right = length xs — 1
qsortST :: Ord a => Int -> Int -> STArray s Int a -> ST s ()
qsortST left right arr = do
when (left <= right) $ do
swapArray left (div (left + right) 2) arr
vLeft <- readArray arr left
(last, _) <- forLoop (left + 1) (<= right) succ
(update vLeft) (return (left, arr))
swapArray left last arr
qsortST left (last — 1) arr
qsortST (last + 1) right arr
where update vLeft i st = do
(last, arr) <- st
vi <- readArray arr i
if (vi < vLeft)
then do
swapArray (succ last) i arr
return (succ last, arr)
else do
return (last, arr)
Это далеко не самый быстрый вариант быстрой сортировки, но самый простой. Мы просто учимся обра-
щаться с изменяемыми массивами. Протестируем:
*Qsort> qsort ”abracadabra”
”aaaaabbcdrr”
*Qsort> let x = 1000000
*Qsort> last $ qsort [x, pred x .. 0]
— двадцать лет спустя
1000000
7.6 Краткое содержание
Мы посмотрели на примерах как применяются типы State, Reader и Writer. Также мы познакомились
с монадой изменяемых значений ST. Она позволяет писать в имеративном стиле на Haskell. Мы узнали два
новых элемента пострения типов:
• Типы-обёртки, которые определяются через ключевое слово newtype.
• Записи, они являются произведением типов с именованными полями.
Также мы узнали несколько полезных типов:
• Map – хранение значений по ключу (из модуля Data.Map).
• Tree – деревья (из модуля Data.Tree).
• Array – массивы (из модуля Data.Array).
• Типы для накопления результата (из модуля Data.Monoid).
Отметим, что экземпляр класса Monad определён и для функций. Мы можем записать функцию двух ар-
гументов (a -> b -> c) как (a -> (-> ) b c). Тогда тип (-> ) b будет типом с одним параметром, как раз
то, что нужно для класса Monad. По смыслу экземпляр класса Monad для функций совпадает с экземпляром
типа Reader. Первый аргумент стрелочного типа b играет роль окружения.
7.7 Упражнения
• Напишите с помощью типа Random функцию игры в кости, два игрока бросают по очереди кости (два
кубика с шестью гранями, грани пронумерованы от 1 до 6). Они бросают кубики 10 раз выигрывает тот,
у кого в сумме выпадет больше очков. Функция принимает начальное состояние и выводит результат
игры: суммарные баллы игроков.
Краткое содержание | 123
• Напишите с помощью типа Random функцию, которая будет создавать случайные деревья заданной
глубины. Значение в узле является случайным числом от 0 до 100, также число дочерних деревьев в
каждом узле случайно, оно изменяется от 0 до 10.
• Опишите в виде конечного автомата поведение амёбы. Амёба может двигаться на плоскости по четырём
направлениям. Если она чувствует свет в определённой стороне, то она ползёт туда. Если по-близости
нет света, она ползает в произвольном направлении. Амёба улавливает интенсивность света, если по
всем четырём сторонам интенсивность одинаковая, она стоит на месте и греется.
• Казалось бы, зачем нам сохранять вычисления в выражениях, почему бы нам просто не вычислить их
сразу? Если у нас есть описание выражения мы можем применить различные техники оптимизации, ко-
торые могут сокращать число вычислений. Например нам известно, что двойное отрицание не влияет
на аргумент, мы можем выразить это так:
instance Num Exp where
negate (Neg a)
= a
negate x
= Neg x
…
…
Так мы сократили вычисления на две операции. Возможны и более сложные техники оптимизации.
Мы можем учесть ноль и единицу при сложении и умножении или дистрибутивность сложения отно-
сительно умножения.
В этом упражнении вам предлагается провести подобную оптимизацию для логических значений. У
нас есть абстрактное синтаксическое дерево:
data Log
= True
| False
| Not Log
| Or
Log Log
| And Log Log
Напишите функцию, которая оптимизирует выражение Log. Эта функция приводит Log к конъюнктив-
ной нормальной форме (КНФ). Дерево в КНФ обладает такими свойствами: все узлы с Or находятся
ближе к корню чем узлы с And и все узлы с And находятся ближе к корню чем узлы с Not. В КНФ выра-
жения имеют вид:
(True ‘And‘ Not False ‘And‘ True) ‘Or‘ True ‘Or‘ (True ‘And‘ False)
(True ‘And‘ True ‘And‘ False) ‘Or‘ True
Как бы мы не шли от корня к листу сначала нам будут встречаться только операции Or, затем только
операции And, затем только Not.
КНФ замечательна тем, что её вычисление может пройти досрочно. КНФ можно представить так:
data Or’
a = Or’
[a]
data And’ a = And’ [a]
data Not’ a = Not’
a
data Lit
= True’ | False’
type CNF = Or’ (And’ (Not’ Lit))
Сначала идёт список выражений разделённых конструктором Or (вычислять весь список не нужно, нам
нужно найти первый элемент, который вернёт True). Затем идёт список выражений, разделённых And
(опять же его не надо вычислять целиком, нам нужно найти первое выражение, которое вернёт False).
В самом конце стоят отрицания.
В нашем случае приведение к КНФ состоит из двух этапов:
– Сначала построим выражение, в котором все конструкторы Or и And стоят ближе к корню чем
конструктор Not. Для этого необходимо воспользоваться такими правилами:
— удаление двойного отрицания
Not (Not a)
==> a
— правила де Моргана
Not (And a b) ==> Or
(Not a) (Not b)
Not (Or
a b) ==> And (Not a) (Not b)
124 | Глава 7: Функторы и монады: примеры
– Делаем так чтобы все конструкторы Or были бы ближе к корню чем конструкторы And. Для этого
мы воспользуемся правилом дистрибутивности:
And a (Or b c)
==> Or (And a b) (And a c)
При этом мы будем учитывать коммутативность And и Or:
And a b
== And b a
Or
a b
== Or
b a
• Когда вы закончите определение функции:
transform :: Log -> CNF
Напишите функцию, которая будет сравнивать вычисление исходного выражения напрямую и вычис-
ление через КНФ. Эта функция будет принимать исходное значение типа Log и будет возвращать два
числа, число операций необходимых для вычисления выражения:
evalCount :: Log -> (Int, Int)
evalCount a = (evalCountLog a, evalCountCNF a)
evalCountLog :: Log -> Int
evalCountLog a = …
evalCountCNF :: Log -> Int
evalCountCNF a = …
При написании этих функций воспользуйтесь функциями-накопителями.
• В модуле Data.Monoid определён специальный тип с помощью которого можно накапливать функции.
Только функции должны быть специального типа. Они должны принимать и возвращать значения од-
ного типа. Такие функции называют эндоморфизмами.
Посмотрим на их определение:
newtype Endo a = Endo { appEndo :: a -> a }
instance Monoid (Endo a) where
mempty = Endo id
Endo f ‘mappend‘ Endo g = Endo (f . g)
В качестве нейтрального элемента выступает функция тождества, а функцией объединения значений
является функция композиции. Попробуйте переписать примеры из главы накопление чисел с помощью
этого типа.
• Реализуйте с помощью монады ST какой-нибудь алгоритм в императивном стиле. Например алгоритм
поиска корней уравнения методом деления пополам. Если функция f непрерывна и в двух точках a и b
( a < b) значения функции имеют разные знаки, то это говорит о том, что где-то на отрезке [ a, b] урав-
нение f( x) = 0 имеет решение. Мы можем найти его так. Посмотрим какой знак у значения функции в
середине отрезка. Если значение равно нулю, то нам повезло и мы нашли решение, если нет, то из двух
