purge.
Тип ST
Выше я пользовался вымышленными типами для упрощения объяснений, на самом деле в Haskell за об-
новление значений отвечает тип ST (сокращение от state transformer). Он живёт в модуле Control.Monad.ST.
Из документации видно, что у него два параметра, и нет конструкторов:
data ST s a
Это наш тип Mutable, теперь посмотрим на тип Mem. Он называется ST-ссылкой и определён в модуле
Data.STRef (сокращение от ST reference). Посмотрим на основные функции:
newSTRef
:: a -> ST s (STRef s a)
readSTRef
:: STRef s a -> ST s a
writeSTRef
:: STRef s a -> a -> ST s ()
Такие функции иногда называют смышлёными конструкторами (smart constructors) они позволяют строить
значение, но скрывают от пользователя реализацию за счёт скрытия конструкторов типа (модуль экспорти-
рует лишь имя типа STRef).
Для иллюстрации этих функций реализуем одну вспомогательную функцию из модуля Data.STRef, функ-
цию обновления значения по ссылке:
modifySTRef :: STRef s a -> (a -> a) -> ST s ()
modifySTRef ref f = writeSTRef . f =<< readSTRef ref
Мы воспользовались тем, что ST является экземпляром Monad. Также как и для State для ST определены
экземпляры классов Functor, Applicative и Monad. Какое совпадение! Посмотрим на функцию purge:
runST :: (forall s. ST s a) -> a
Монада изменяемых значений ST | 119
Императивные циклы
Реализуем for цикл из языка C:
Result s;
for (i = 0 ; i < n; i++)
update(i, s);
return s;
У нас есть стартовое значение счётчика и результата, функция обновления счётчика, предикат останова и
функция обновления результата. Мы инициализируем счётчик и затем обновляем счётчик и состояние до тех
пор пока предикат счётчика не станет ложным. Напишем чистую функцию, которая реализует этот процесс. В
этой функции мы воспользуемся специальным синтаксическим сахаром, который называется do-нотация, не
пугайтесь это всё ещё 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