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

Ответ 1

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

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

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

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

Итак, в то время как монада называется "Состояние", фактическое значение, обернутое монадой, - это значение, основанное на состоянии, а не фактическое значение содержащегося состояния.

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

runState (State f) = f

Итак, что это значит, когда вы определяете функцию, возвращающую значение состояния? Пусть на мгновение игнорирует тот факт, что государство является монадой, и просто посмотрите на основные типы. Сначала рассмотрим эту функцию (которая фактически ничего не делает с состоянием):

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

Если вы посмотрите на определение состояния, мы можем видеть, что здесь тип 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)

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

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, поэтому наш результат здесь будет (), кортеж нулевого элемента, который представляет "нет значения" в 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 для строки, затем удвоить значение состояния, если результат будет ложным, а затем снова проверить строку и, наконец, вернуть true, если либо проверка выполнена. У нас есть все части, которые нам нужны для этой задачи, но написать все это было бы болью. Можем ли мы создать функцию, которая автоматически объединяет две функции, каждая из которых возвращает функции, подобные состояниям? Конечно! Нам просто нужно убедиться, что в качестве аргументов требуется две вещи: функция состояния, возвращаемая первой функцией, и функция, которая принимает в качестве аргумента предыдущую функцию 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 может передавать его вместе с функциями, которые ничего не знают о трюке, который мы натягиваем на них. Кроме того, мы будем использовать 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)

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

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)

Ответ 2

Прежде всего, ваш пример слишком сложный, потому что ему не нужно хранить val в государственной монаде; только семя является постоянным состоянием. Во-вторых, я думаю, вам повезет, если вместо использования стандартной государственной монады, вы снова реализуете всю государственную монаду и ее операции со своими типами. Я думаю, вы узнаете больше об этом. Вот несколько деклараций, которые помогут вам начать:

data MyState s a = MyState (s -> (s, b))

get :: Mystate s s
put :: s -> Mystate s ()

Затем вы можете написать свои собственные соединители:

unit :: a -> Mystate s a
bind :: Mystate s a -> (a -> Mystate s b) -> Mystate s b

Наконец

data Seed = Seed Int
nextVal :: Mystate Seed Bool

Что касается вашей проблемы с десурацией, нотация do, которую вы используете, довольно сложна. Но десураринг - это механическая процедура по принципу "по очереди". Как только я смогу разобраться, ваш код должен выглядеть таким же образом (вернемся к вашим оригинальным типам и коду, с которыми я не согласен):

 nextVal = get >>= \ Random seed val ->
                      let seed' = updateSeed seed
                          val'  = even seed'
                      in  put (Random seed' val') >>= \ _ -> return val'

Чтобы сделать структуру вложенности немного яснее, я сделал большие свободы с отступом.

Ответ 3

У вас есть пара отличных ответов. То, что я делаю, работая с государственной монадой, на мой взгляд заменяет State s a на s -> (s,a) (в конце концов, это действительно то, что есть).

Затем вы получите тип привязки, который выглядит следующим образом:

(>>=) :: (s -> (s,a)) ->
         (a -> s -> (s,b)) ->
         (s -> (s,b))

и вы видите, что bind - это просто специализированный тип оператора композиции функций, например (.)

Я написал блог/учебник по государственной монаде здесь. Это, вероятно, не очень хорошо, но мне помогли немного лучше, написав его.