test :: Int -> Int -> [a] -> [a]
Посмотрим на то, как она работает:
*Qsort> test 0 3 [0,1,2,3,4]
[3,1,2,0,4]
*Qsort> test 0 4 [0,1,2,3,4]
[4,1,2,3,0]
Теперь перейдём к сортировке. Суть метода в том, что мы выбираем один элемент массива, называемый
осью (pivot) и переставляем остальные элементы массива так, чтобы все элементы меньше осевого были сле-
ва от него, а все, что больше оказались справа. Затем мы повторяем эту процедуру на массивах поменьше,
тех, что находятся слева и справа от осевого элемента и так пока все элементы не отсортируются. В алго-
ритме очень хитрая процедура перестановки элементов, наша задача переставить элементы в массиве, то
есть не пользуясь никакими дополнительными структурами данных. Я не буду говорить как это делается,
просто выпишу код, а вы можете почитать об этом где-нибудь, в любом случае из кода будет понятно как это
происходит:
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.
• Опишите в виде конечного автомата поведение амёбы. Амёба может двигаться на плоскости по четырём
направлениям. Если она чувствует свет в определённой стороне, то она ползёт туда. Если по-близости
нет света, она ползает в произвольном направлении. Амёба улавливает интенсивность света, если по
всем четырём сторонам интенсивность одинаковая, она стоит на месте и греется.
• Казалось бы, зачем нам сохранять вычисления в выражениях, почему бы нам просто не вычислить их
сразу? Если у нас есть описание выражения мы можем применить различные техники оптимизации, ко-
торые могут сокращать число вычислений. Например нам известно, что двойное отрицание не влияет