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)
Первый элемент пары играет роль счётчика, а во втором мы накапливаем результат.
Быстрая сортировка
Реализуем императивный алгоритм быстрой сортировки. Алгоритм быстрой сортировки хорош не только
тем, что он работает очень быстро, но и минимальным расходом памяти. Сортировка проводится в самом
массиве, с помощью обмена элементов местами. Но для этого нам понадобятся изменяемые массивы. Этот