ва от него, а все, что больше оказались справа. Затем мы повторяем эту процедуру на массивах поменьше,
тех, что находятся слева и справа от осевого элемента и так пока все элементы не отсортируются. В алго-
ритме очень хитрая процедура перестановки элементов, наша задача переставить элементы в массиве, то
есть не пользуясь никакими дополнительными структурами данных. Я не буду говорить как это делается,
просто выпишу код, а вы можете почитать об этом где-нибудь, в любом случае из кода будет понятно как это
происходит:
qsort :: Ord a => [a] -> [a]
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))