Монада состояния, последовательности случайных чисел и одноместного кода

Сначала State monad выглядит немного запутанным; давайте сделаем так, как предложил Норман Рэмзи, и посмотрим, как реализовать это с нуля. Внимание, это довольно долго!

Во-первых, State имеет два типа параметров: тип содержащих данные состояния и тип конечного результата вычисления . Здесь в качестве переменных типа мы будем использовать stateData и result соответственно. Это имеет смысл, если задуматься; определяющей характеристикой вычисления на основе состояния является то, что оно модифицирует состояние, производя результат.

Менее очевидно, что конструктор типов принимает функцию из состояния в измененное состояние и приводит к следующему результату:

newtype State stateData result = State (stateData -> (result, stateData))

Таким образом, в то время как монад называется "State", действительное значение, обернутое монадом, является значением вычисления, основанного на состоянии , а не действительным значением содержащегося в нем состояния.

Помня об этом, мы не должны удивляться, что функция runState, используемая для выполнения вычисления в State monad, на самом деле является не более чем аксессуаром для самой обернутой функции, и может быть определена следующим образом:

runState (State f) = f

Так что же это значит, когда вы определяете функцию, которая возвращает значение State? Давайте на мгновение проигнорируем тот факт, что State - это monad, и просто посмотрим на типы, лежащие в основе. Сначала рассмотрим эту функцию (которая на самом деле ничего не делает со статусом):

len2State :: String -> State Int Bool
len2State s = return ((length s) == 2)

Если посмотреть на определение State, то мы увидим, что здесь типом stateData является Int, а типом result является Bool, так что функция, обёрнутая конструктором данных, должна иметь тип Int -> (Bool, Int). Теперь представьте себе версию len2State--очевидно, что она должна иметь тип String -> Bool. Итак, как бы вы пошли на преобразование такой функции в функцию, возвращающую значение, которое помещается в обертку состояния?

Ну, очевидно, что преобразованная функция должна будет принять второй параметр, Int, представляющий значение состояния. Она также должна вернуть значение состояния, другое Int. Так как мы на самом деле ничего не делаем с состоянием в этой функции, давайте просто сделаем очевидное - пропустим эту int прямо насквозь. Вот функция в форме состояния, определенная в терминах версии без состояний:

len2 :: String -> Bool
len2 s = ((length s) == 2)

len2State :: String -> (Int -> (Bool, Int))
len2State s i = (len2' s, i)

Но это глупо и излишне. Давайте обобщим преобразование так, что мы сможем передать значение результата и превратить что угодно в State-like функцию.

convert :: Bool -> (Int -> (Bool, Int))
convert r d = (r, d)

len2 s = ((length s) == 2)

len2State :: String -> (Int -> (Bool, Int))
len2State s = convert (len2 s)

А что, если нам нужна функция, которая изменяет состояние? Очевидно, что мы не можем построить такую функцию с помощью convert, так как мы написали это для передачи состояния. Оставим это простым и напишем функцию, которая перезапишет состояние новым значением. Какой тип будет нужен? Ему понадобится Int для нового значения состояния, и, конечно же, нужно будет вернуть функцию stateData -> (result, stateData), потому что это то, что нужно нашей обертке State. Перезапись значения состояния на самом деле не имеет разумного значения result вне вычисления State, так что наш результат здесь будет просто (), кортеж с нулевым элементом, который представляет "нет значения" в Хаскелле.

overwriteState :: Int -> (Int -> ((), Int))
overwriteState newState _ = ((), newState)

Это было просто! Теперь давайте на самом деле сделаем что-нибудь с этими данными состояния. Перепишем сверху len2State во что-нибудь более разумное: сравним длину строки со значением текущего состояния.

lenState :: String -> (Int -> (Bool, Int))
lenState s i = ((length s) == i, i)

Можем ли мы обобщить это в преобразователь и функцию без состояния, как мы делали это раньше? Не так просто. Наша функция len должна будет воспринимать состояние как аргумент, но мы не хотим, чтобы оно "знало" о состоянии. Неловко, действительно. Однако, мы можем написать быструю вспомогательную функцию, которая будет обрабатывать все за нас: мы дадим ей функцию, которая должна использовать значение состояния, и она передаст значение, а затем упакует все обратно в функцию в форме состояния, оставляя len ничего мудрее.

useState :: (Int -> Bool) -> Int -> (Bool, Int)
useState f d = (f d, d)

len :: String -> Int -> Bool
len s i = (length s) == i

lenState :: String -> (Int -> (Bool, Int))
lenState s = useState (len s)

Итак, хитрый момент - что, если мы захотим связать эти функции вместе? Допустим, мы хотим использовать lenState на строке, затем удвоить значение состояния, если результат ложный, а затем снова проверить строку, и, наконец, вернуть правду, если любой из них проверил. У нас есть все части, которые нам нужны для этой задачи, но выписывать все это было бы больно. Можем ли мы создать функцию, которая автоматически связывает воедино две функции, каждая из которых возвращает функции, похожие на функции состояния? Конечно! Нам просто нужно убедиться, что в качестве аргументов она принимает две вещи: функцию состояния, возвращаемую первой функцией, и функцию, которая принимает в качестве аргумента предыдущую функцию типа result. Посмотрим, как это получится:

chainStates :: (Int -> (result1, Int)) -> (result1 -> (Int -> (result2, Int))) -> (Int -> (result2, Int))
chainStates prev f d = let (r, d') = prev d
                       in f r d'

Все, что мы делаем, это применяем первую функцию состояния к некоторым данным состояния, затем применяем вторую функцию к результату и к измененным данным состояния. Просто, правда?

Теперь интересная часть: Между chainStates и convert, мы должны быть почти в состоянии превратить любую комбинацию функций без состояний в функцию, поддерживающую состояние! Единственное, что нам сейчас нужно, это замена useState, которая возвращает данные о состоянии как результат, так что цепные государства могут передавать их функциям, которые ничего не знают о трюке, который мы на них натягиваем. Также, мы будем использовать lambdas, чтобы принять результат от предыдущих функций и дать им временные имена. Хорошо, давайте сделаем так:

extractState :: Int -> (Int, Int)
extractState d = (d, d)

chained :: String -> (Int -> (Bool, Int))
chained str = chainStates  extractState         $ \state1 ->
              let check1 = (len str state1) in
              chainStates (overwriteState (
                  if check1 
                  then state1 
                  else state1 * 2))             $ \ _ ->
              chainStates  extractState         $ \state2 ->
              let check2 = (len str state2) in
              convert (check1 || check2)

И попробуем:

> chained "abcd" 2
(True, 4)
> chained "abcd" 3
(False, 6)
> chained "abcd" 4
(True, 4)
> chained "abcdef" 5
(False, 10)

Конечно, мы не можем забыть, что State на самом деле является монадой, которая обволакивает функции, похожие на State, и держит нас подальше от них, так что ни одна из наших изящных функций, которые мы создали, не поможет нам с реальной вещью. Или помогут? В шокирующем повороте получается, что реальный State monad предоставляет все одинаковые функции, под разными названиями:

runState (State s) = s
return r = State (convert r)
(>>=) s f = State (\d -> let (r, d') = (runState s) d in
                         runState (f r) d')
get = State extractState
put d = State (overwriteState d)

Обратите внимание, что >>= почти идентично chainStates, но не было хорошего способа определить его с помощью chainStates. Итак, чтобы подвести итог, можно переписать последний пример, используя real State:

chained str = get                               >>= \state1 ->
              let check1 = (len str state1) in
              put (if check1 
                  then state1 else state1 * 2)  >>= \ _ ->
              get                               >>= \state2 ->
              let check2 = (len str state2) in
              return (check1 || check2)

Или, все засахаренные эквивалентом do notation:

chained str = do
        state1 <- get
        let check1 = len str state1
        _ <- put (if check1 then state1 else state1 * 2)
        state2 <- get
        let check2 = (len str state2)
        return (check1 || check2)