Монада состояния, последовательности случайных чисел и монадический код
https://stackoverflow.com/questions/1956518
-
21-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я пытаюсь понять монаду состояния, и с этой целью я хотел написать монадический код, который генерировал бы последовательность случайных чисел с использованием линейного конгруэнтного генератора (возможно, не очень хорошо, но мое намерение - просто изучить монаду состояния, а не создавать хорошую библиотеку RNG).
Генератор как раз такой (я хочу сгенерировать последовательность Bools для простоты):
type Seed = Int
random :: Seed -> (Bool, Seed)
random seed = let (a, c, m) = (1664525, 1013904223, 2^32) -- some params for the LCG
seed' = (a*seed + c) `mod` m
in (even seed', seed') -- return True/False if seed' is even/odd
Не беспокойтесь о числах, это всего лишь правило обновления для начального числа, которое (согласно Числовым рецептам) должно генерировать псевдослучайную последовательность Ints.Теперь, если я хочу последовательно генерировать случайные числа, я бы сделал:
rand3Bools :: Seed -> ([Bool], Seed)
rand3Bools seed0 = let (b1, seed1) = random seed0
(b2, seed2) = random seed1
(b3, seed3) = random seed2
in ([b1,b2,b3], seed3)
Хорошо, итак, я мог бы избежать этого шаблона, используя монаду состояния:
import Control.Monad.State
data Random {seed :: Seed, value :: Bool}
nextVal = do
Random seed val <- get
let seed' = updateSeed seed
val' = even seed'
put (Random seed' val')
return val'
updateSeed seed = let (a,b,m) = (1664525, 1013904223, 2^32) in (a*seed + c) `mod` m
И , наконец ,:
getNRandSt n = replicateM n nextVal
getNRand :: Int -> Seed -> [Bool]
getNRand n seed = evalState (getNRandStates n) (Random seed True)
Хорошо, это работает нормально и дайте мне список из n псевдослучайных Bools для каждого заданного семени.Но...
Я могу прочитать, что я сделал (в основном на основе этого примера: http://www.haskell.org/pipermail/beginners/2008-September/000275.html ) и копируйте его, чтобы делать другие вещи.Но я не думаю, что смогу понять, что на самом деле происходит за нотацией do и монадическими функциями (такими как replicateM).
Кто-нибудь может помочь мне с некоторыми из этих сомнений?
1 - Я пытался отключить функцию nextVal, чтобы понять, что она делает, но у меня не получилось.Я могу предположить, что он извлекает текущее состояние, обновляет его, а затем передает состояние вперед для следующего вычисления, но это просто основано на чтении этого do-sugar, как если бы это был английский.
Как мне действительно преобразовать эту функцию в исходную >>= и возвращать функции шаг за шагом?
2 - Я не мог понять, что именно put и get функции выполняют.Я могу догадаться, что они "упаковывают" и "распаковывают" государство.Но механика, стоящая за добавлением сахара, все еще неуловима для меня.
Что ж, любые другие общие замечания по поводу этого кода очень приветствуются.Иногда я соглашался с Haskell, что могу создать работающий код и делать то, что я ожидаю от него, но я не могу "следовать оценке", как я привык делать с императивными программами.
Решение
Монада состояния на первый взгляд действительно выглядит несколько сбивающей с толку;давайте поступим так, как предложил Норман Рэмси, и рассмотрим, как реализовать с нуля.Внимание, это довольно долго!
Во-первых, состояние имеет два параметра типа:тип самого содержащиеся данные о состоянии и тип самого конечный результат вычисления.Мы будем использовать stateData и result соответственно, как переменные типа для них здесь.Это имеет смысл, если вы подумаете об этом;определяющей характеристикой вычисления, основанного на состоянии, является то, что оно изменяет состояние при создании выходных данных.
Менее очевидным является то, что конструктор типа принимает функция из состояния в измененное состояние и результат, вот так:
newtype State stateData result = State (stateData -> (result, stateData))
Таким образом, в то время как монада называется "State", фактическое значение, заключенное в монаду, является значением вычисление, основанное на состоянии, а не фактическое значение содержащегося состояния.
Имея это в виду, мы не должны удивляться, обнаружив, что функция runState используемый для выполнения вычисления в монаде состояния на самом деле является не чем иным, как средством доступа для самой обернутой функции, и может быть определен следующим образом:
runState (State f) = f
Итак, что это значит, когда вы определяете функцию, которая возвращает значение состояния?Давайте на мгновение проигнорируем тот факт, что State - это монада, и просто посмотрим на базовые типы.Сначала рассмотрим эту функцию (которая на самом деле ничего не делает с состоянием).:
len2State :: String -> State Int Bool
len2State s = return ((length s) == 2)
Если вы посмотрите на определение государства, мы можем увидеть, что здесь stateData тип - это Int, и в result тип - это Bool, таким образом , функция , обернутая конструктором данных , должна иметь тип Int -> (Bool, Int).Теперь представьте себе версию без состояния len2State--очевидно, что это было бы типа String -> Bool.Итак, как бы вы преобразовали такую функцию в функцию, возвращающую значение, которое помещается в оболочку состояния?
Ну, очевидно, преобразованная функция должна будет принять второй параметр, an 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), потому что это то, что нужно нашей оболочке состояния.Перезапись значения состояния на самом деле не имеет разумного result значение вне вычисления состояния, так что наш результат здесь будет просто (), кортеж с нулевым элементом, который представляет "no value" в 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 для строки затем удвойте значение состояния, если результат равен false, затем проверьте строку еще раз и, наконец, верните 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 могут передавать их функциям, которые ничего не знают о трюке, который мы с ними применяем.Кроме того, мы будем использовать лямбды, чтобы принять результат предыдущих функций и присвоить им временные имена.Хорошо, давайте сделаем так, чтобы это произошло:
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, и держит нас подальше от них, поэтому ни одна из наших замечательных функций, которые мы создали, не поможет нам в реальной работе.Или они это сделают?Шокирующим образом оказывается, что монада реального состояния предоставляет все те же функции, но под разными именами:
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)
Или, все засахаренные с эквивалентным обозначением do:
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)
Другие советы
Прежде всего, ваш пример чрезмерно сложен, потому что в нем не нужно хранить 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'
Чтобы сделать структуру вложенности немного понятнее, я позволил себе значительные вольности с отступами.
У вас есть пара отличных ответов.То, что я делаю при работе с государственной монадой, на мой взгляд, заменяет State s a с s -> (s,a) (в конце концов, так оно и есть на самом деле).
Затем вы получаете тип для привязки, который выглядит следующим образом:
(>>=) :: (s -> (s,a)) ->
(a -> s -> (s,b)) ->
(s -> (s,b))
и вы видите, что bind - это просто специализированный вид оператора композиции функций, например (.)
Я написал блог / учебное пособие по государственной монаде здесь.Возможно, это не особенно хорошо, но написав это, я немного улучшил восприятие вещей.
