пугайтесь это всё ещё Haskell, для понимания этого примера загляните в раздел “сахар для монад” главы~17.
module Loop where
import Control.Monad
import Data.STRef
import Control.Monad.ST
forLoop ::
i -> (i -> Bool) -> (i -> i) -> (i -> s -> s) -> s -> s
forLoop i0 pred next update s0 = runST $ do
refI <- newSTRef i0
refS <- newSTRef s0
iter refI refS
readSTRef refS
where iter refI refS = do
i <- readSTRef refI
s <- readSTRef refS
when (pred i) $ do
writeSTRef refI $ next i
writeSTRef refS $ update i s
iter refI refS
Впрочем код выше можно понять если читать его как обычный императивный код. Выражения do-блока
выполняются последовательно, одно за другим. Сначала мы инициализируем два изменяемых значения, для
счётчика цикла и для состояния. Затем в функции iter мы читаем значения и выполняем проверку предиката
pred. Функция when – это стандартная функция из модуля Control.Monad. Она проверяет предикат, и если
он возвращает True выполняет серию действий, в которых мы записываем обновлённые значения. Обратите
внимание на то, что связка when-do это не специальная конструкция языка. Как было сказано when – это
просто функция, но она ожидает одно действие, а мы хотим выполнить сразу несколько. Следующее за ней
do начинает блок действий (границы блока определяются по отступам), который будет интерпретироваться
как одно действие. В настоящем императивном цикле в обновлении и предикате счётчика может участвовать
переменная результата, но это считается признаком дурного стиля, поэтому наши функции определены на
типе счётчика. Решим типичную задачу, посчитаем числа от одного до десяти:
*Loop> forLoop 1 (<=10) succ (+) 0
55
Посчитаем факториал:
*Loop> forLoop 1 (<=10) succ (*) 1
3628800
*Loop> forLoop 1 (<=100) succ (*) 1
9332621544394415268169923885626670049071596826
4381621468592963895217599993229915608941463976
1565182862536979208272237582511852109168640000
00000000000000000000
Теперь напишем while-цикл:
120 | Глава 7: Функторы и монады: примеры
Result s;
while (pred(s))
update(s);
return s;
В этом цикле участвует один предикат и одна функция обновления результата, мы обновляем результат
до тех пор пока предикат не станет ложным.
whileLoop :: (s -> Bool) -> (s -> s) -> s -> s
whileLoop pred update s0 = runST $ do
ref <- newSTRef s0
iter ref
readSTRef ref
where iter ref = do
s <- readSTRef ref
when (pred s) $ do
writeSTRef ref $ update s
iter ref
Посчитаем сумму чисел через while-цикл:
*Loop> whileLoop ((> 0) . fst) ((n, s) -> (pred n, n + s)) (10, 0)
(0,55)
Первый элемент пары играет роль счётчика, а во втором мы накапливаем результат.
Быстрая сортировка
Реализуем императивный алгоритм быстрой сортировки. Алгоритм быстрой сортировки хорош не только
тем, что он работает очень быстро, но и минимальным расходом памяти. Сортировка проводится в самом
массиве, с помощью обмена элементов местами. Но для этого нам понадобятся изменяемые массивы. Этот
тип определён в модуле Data.Array.ST. В Haskell есть несколько типов изменяемых массивов (как впрочем и
неизменяемых), это связано с различными нюансами размещения элементов в массивах, о которых мы пока
умолчим. Для предостваления общего интерфейса к различным массивам был определён класс:
class (HasBounds a, Monad m) => MArray a e m where
newArray
:: Ix i => (i, i) -> e -> m (a i e)
newArray_ :: Ix i => (i, i) -> m (a i e)
MArray – это сокращение от mutable (изменяемый) array. Метод newArray создёт массив типа a, который
завёрнут в тип-монаду m. Первый аргумент указывает на диапазон значений индексов массива, а вторым
аргументом передаётся элемент, который будет записан во все ячейки массива. Вторая функция записывает
в массив элемент undefined.
Посмотрим на вспомогательные классы:
class Ord a => Ix a where
range :: (a, a) -> [a]
index :: (a, a) -> a -> Int
inRange :: (a, a) -> a -> Bool
rangeSize :: (a, a) -> Int
class HasBounds a where
bounds :: Ix i => a i e -> (i, i)
Класс Ix описывает тип индекса из непрерывного диапазона значений. Наверняка по имени функции
и типу вы догадаетесь о назначении методов (можете свериться с интерпретатором на типах Int или (Int,
Int)). Класс HasBounds обозначает массивы размер, которых фиксирован. Но вернёмся к массивам. Мы можем
не только выделять память под массив, но и читать элементы и обновлять их:
readArray
:: (MArray a e m, Ix i) => a i e -> i -> m e
writeArray :: (MArray a e m, Ix i) => a i e -> i -> e -> m ()
В случае ST-ссылок у нас была функция runST. Она возвращала значение из памяти, но что будет возвра-
щать аналогичная функция для массива? Посмотрим на неё:
Монада изменяемых значений ST | 121
freeze :: (Ix i, MArray a e m, IArray b e) => a i e -> m (b i e)
Возможно за всеми классами схожесть с функцией runST прослеживается не так чётко. Новый класс
IArray обозначает неизменяемые (immutable) массивы. Функцией freeze мы превращаем изменяемый мас-
сив в неизменяемый, но завёрнутый в специальный тип-монаду. В нашем случае этим типом будет ST. В
модуле Data.Array.ST определена специальная версия этой функции:
runSTArray :: Ix i => (forall s . ST s (STArray s i e)) -> Array i e
Здесь Array – это обычный неизменяемый массив. Он живёт в модуле Data.Array мы можем строить
массивы из списков значений, преобразовывать их разными способами, превращать в обратно в списки и
многое другое. Об о всём этом можно узнать из документации к модулю. Обратите на появление слова
forall и в этой функции. Оно несёт тот же смысл, что и в функции runST.
Для тренировки напишем функцию, которая меняет местами два элемента массива:
module Qsort where
import Data.STRef
import Control.Monad.ST
import Data.Array
import Data.Array.ST
import Data.Array.MArray
swapElems :: Ix i => i -> i -> STArray s i e -> ST s ()
swapElems i j arr = do
vi <- readArray arr i
vj <- readArray arr j
writeArray arr i vj
writeArray arr j vi
Протестируем на небольшом массиве:
test :: Int -> Int -> [a] -> [a]
test i j xs = elems $ runSTArray $ do
arr <- newListArray (0, length xs — 1) xs
swapElems i j arr
return arr
Тир функции test ничем не выдаёт её содержание. Вроде функция как функция:
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]
