Учебник по Haskell

тивного состояния s из типа Mutable, но в случае типа Mem, этот параметр продолжает своё путешествие по

программе в типе значения v :: Mem s a. По типу v компилятор может сказать, что существует такое s,

для которого значение v имеет смысл (правильно типизировано). Но оно не любое! Функцию purge с трю-

ком интересует не некоторый тип, а все возможные типы s, поэтому пример не пройдёт проверку типов.

Компилятор будет следить за “чистотой” наших обновлений.

При таком подходе остаётся вопрос: откуда мы возьмём начальное значение, ведь теперь у нас нет типа

FakeState? В Haskell специально для этого типа было сделано исключение. Мы возьмём его из воздуха. Это

чисто фиктивный параметр, нам главное, что он скрыт от пользователя, и он нигде не может им воспользо-

ваться. Поскольку у нас нет конструктора Mutable мы никогда не сможем добраться до внутренней функции

типа State и извлечь состояние. Состояние скрыто за интерфейсом класса Monad и отбрасывается в функции

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: Функторы и монады: примеры