Поначалу монада состояния действительно выглядит сбивающей с толку; давайте сделаем так, как предложил Норман Рэмси, и рассмотрим, как реализовать с нуля. Предупреждение, это довольно долго!
Во-первых, State имеет два параметра типа: тип содержащихся данных состояния и тип окончательного результата вычисления. Здесь мы будем использовать stateData и result соответственно в качестве переменных типа для них. Если задуматься, это имеет смысл; Определяющая характеристика вычислений на основе состояний состоит в том, что они изменяют состояние при создании вывода.
Менее очевидно то, что конструктор типа принимает функцию из состояния в измененное состояние и результат, например:
newtype State stateData result = State (stateData -> (result, stateData))
Таким образом, хотя монада называется «Состояние», фактическое значение, заключенное в оболочку монады, - это значение вычисления на основе состояния, а не фактическое значение содержащегося в нем состояния.
Помня об этом, мы не должны удивляться, обнаружив, что функция runState, используемая для выполнения вычисления в монаде State, на самом деле является не более чем средством доступа для самой обернутой функции и может быть определена следующим образом:
runState (State f) = f
Итак, что это означает, когда вы определяете функцию, которая возвращает значение состояния? Давайте на мгновение проигнорируем тот факт, что State - это монада, и просто посмотрим на лежащие в основе типы. Сначала рассмотрим эту функцию (которая на самом деле ничего не делает с состоянием):
len2State :: String -> State Int Bool
len2State s = return ((length s) == 2)
Если вы посмотрите на определение состояния, мы увидим, что здесь тип stateData - это Int, а тип result - это Bool, поэтому функция, заключенная в конструктор данных, должна иметь тип Int -> (Bool, Int). А теперь представьте версию _12 _ без состояния - очевидно, что она будет иметь тип String -> Bool. Итак, как бы вы преобразовали такую функцию в функцию, возвращающую значение, которое помещается в оболочку State?
Что ж, очевидно, преобразованная функция должна будет принимать второй параметр, Int, представляющий значение состояния. Также необходимо вернуть значение состояния, другое Int. Поскольку на самом деле мы ничего не делаем с состоянием в этой функции, давайте просто сделаем очевидную вещь - передадим этот int прямо до конца. Вот функция в форме состояния, определенная в терминах версии без состояния:
len2 :: String -> Bool
len2 s = ((length s) == 2)
len2State :: String -> (Int -> (Bool, Int))
len2State s i = (len2' s, i)
Но это отчасти глупо и излишне. Давайте обобщим преобразование, чтобы мы могли передать значение результата и превратить что угодно в функцию, подобную состоянию.
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 вне вычисления состояния, поэтому нашим результатом здесь будет просто (), кортеж с нулевым элементом, который представляет "отсутствие значения" в Haskell.
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, который возвращает данные состояния в качестве своего результата, так что chainStates может передавать их функциям, которые ничего не знают о трюке, который мы им навязываем. Кроме того, мы будем использовать лямбды, чтобы принять результат от предыдущих функций и дать им временные имена. Хорошо, давайте сделаем это:
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 предоставляет все те же функции под разными именами:
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. Итак, чтобы подвести итог, мы можем переписать последний пример, используя реальное состояние:
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)
Или все засахаренные эквивалентной записью:
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)
person
C. A. McCann
schedule
24.12.2009
