Монада State на примере

@serrr · Регистрация: 08.01.2013

Студворк — интернет-сервис помощи студентам

Читал статью про монады Кирпичёва, в частности, застрял на монаде State (почти не понял) и программе с её участием.

Рассмотрим, например, программу, реализующую метод Монте-Карло. Для этого ей понадобится датчик случайных чисел, обладающий состоянием. Тогда для этой программы «a» будет соответствовать типу результата – например, числу успешных экспериментов – а «s» будет представлять внутреннее состояние датчика случайных чисел. Эта программа будет использовать функцию «сгенерировать случайное число», которая будет возвращать новое случайное число и изменять состояние датчика:

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
rand :: State RndGen Int
rand = get >>= \(RndGen x) ->
       put $ RndGen ((x*1367823 + 918237) `mod` 32768) >>=
       return x
 
monteCarlo :: (Int -> Bool) -> Int -> State RndGen Int
monteCarlo experiment 0 = return 0
monteCarlo experiment n = rand >>= \r ->
                          if (experiment r) then
                              monteCarlo experiment (n-1) >>= \s ->
                              return (s+1)
                          else
                              monteCarlo experiment (n-1)

Заметим, что в коде monteCarlo нет никаких намеков на присваивания и изменение состояния – код написан в чисто функциональном стиле, и всю «подноготную» скрывает в себе монада State и функция rand.

У меня возник вопрос, как сделать этот кусок кода рабочей программой? Импортировать Control.Monad.State и System.Random, вероятно. Интерпретатор теряется в догадках, что за тип такой RndGen, откуда он происходит. И какова будет точка входа в программу?

@calabi-yau · 14.07.2013, 19:37

Сообщение от serrr

Интерпретатор теряется в догадках, что за тип такой RndGen, откуда он происходит.

Вполне возможно что это просто:

Haskell
1
newtype RndGen = RndGen Int

кроме того:

Haskell
1
put (RndGen ((x*1367823 + 918237) `mod` 32768)) >> return x

вместо:

Haskell
1
put $ RndGen ((x*1367823 + 918237) `mod` 32768) >>= return x

Добавлено через 1 минуту

Сообщение от serrr

И какова будет точка входа в программу?

функция main

@serrr · 14.07.2013, 22:59 **[ТС]**

Сообщение от calabi-yau

Вполне возможно что это просто:

Haskell
1
newtype RndGen = RndGen Int

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

Кликните здесь для просмотра всего текста

Prelude> :l ./monteCarlo.hs
[1 of 1] Compiling Main ( monteCarlo.hs, interpreted )

monteCarlo.hs:9:8:
Couldn't match type `RndGen' with `m0 Int'
When using functional dependencies to combine
MonadState s (StateT s m),
arising from the dependency `m -> s'
in the instance declaration in `Control.Monad.State.Class'
MonadState (m0 Int) (StateT RndGen Data.Functor.Identity.Identity),
arising from a use of `put' at monteCarlo.hs:9:8-10
In the expression: put
In the expression:
put $ RndGen ((x * 1367823 + 918237) `mod` 32768) >> return x

monteCarlo.hs:9:8:
Couldn't match type `()' with `Int'
Expected type: StateT RndGen Data.Functor.Identity.Identity Int
Actual type: StateT RndGen Data.Functor.Identity.Identity ()
In the expression:
put $ RndGen ((x * 1367823 + 918237) `mod` 32768) >> return x
In the second argument of `(>>=)', namely
`\ (RndGen x)
-> put $ RndGen ((x * 1367823 + 918237) `mod` 32768) >> return x'
In the expression:
get
>>=
\ (RndGen x)
-> put $ RndGen ((x * 1367823 + 918237) `mod` 32768) >> return x

monteCarlo.hs:9:14:
Couldn't match expected type `m0 a0' with actual type `RndGen'
In the return type of a call of `RndGen'
In the first argument of `(>>)', namely
`RndGen ((x * 1367823 + 918237) `mod` 32768)'
In the second argument of `($)', namely
`RndGen ((x * 1367823 + 918237) `mod` 32768) >> return x'
Failed, modules loaded: none.

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import System.Random
import Control.Monad.State
 
newtype RndGen = RndGen Int deriving (Show, Read, Eq)
 
rand :: State RndGen Int
rand = get >>= \(RndGen x) ->
       put $ RndGen ((x*1367823 + 918237) `mod` 32768) >>
       return x
 
monteCarlo :: (Int -> Bool) -> Int -> State RndGen Int
monteCarlo experiment 0 = return 0
monteCarlo experiment n = rand >>= \r ->
                          if (experiment r) then
                              monteCarlo experiment (n-1) >>= \s ->
                              return (s+1)
                          else
                              monteCarlo experiment (n-1)

Автор, ведь, намеревался пристроить нормальный такой датчик случайных чисел, а не какую-то "заглушку".
Сам генератор случайности образуется либо вручную:
random (mkStdGen x) :: (Int, StdGen),

либо

main = do
gen <- getStdGen
...
и понеслась. Как-то так. В сигнатуре rand - RndGen - тип, т.к. идет с большой буквы, а что он в реализации get и put делает?

@calabi-yau · 15.07.2013, 02:32

Сообщение от serrr

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

Приоритет функции ($) меньше чем (>>), поэтому выражение:

Haskell
1
2
put $ RndGen ((x*1367823 + 918237) `mod` 32768) >>
       return x

трактуется как:

Haskell
1
2
put (RndGen ((x*1367823 + 918237) `mod` 32768) >>
       return x)

это и есть причина ошибки. Нужно как-то так:

Haskell
1
put (RndGen ((x*1367823 + 918237) `mod` 32768)) >> return x

Автор, ведь, намеревался пристроить нормальный такой датчик случайных чисел, а не какую-то "заглушку".

Больше похоже что автор пытался не пристроить, а построить генератор сч.

В сигнатуре rand - RndGen - тип, т.к. идет с большой буквы, а что он в реализации get и put делает?

Это конструктор данных типа - конструирует конкретные значения типа, просто в нашем случае тип и его конструктор данных называются одинаково.

Добавлено через 54 минуты
Но, если нужно таки именно пристроить StdGen - есть функция random :: RandomGen g => g -> (a, g) которая фактически и есть монада состояния без прикрас, нам остается построить из нее значение типа State:

Haskell
1
2
rand :: State StdGen Int
rand = state random

функция state орпеделена в классе MonadState, ее сигнатура:

Haskell
1
state :: (s -> (a, s)) -> m a

и далее применять так:

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
rand :: State StdGen Int
rand = state random
 
monteCarlo :: (Int -> Bool) -> Int -> State StdGen Int
monteCarlo experiment 0 = return 0
monteCarlo experiment n = rand >>= \r ->
                          if (experiment r) then
                              monteCarlo experiment (n-1) >>= \s ->
                              return (s+1)
                          else
                              monteCarlo experiment (n-1)
                              
main = 
  do g <- newStdGen
     let x = evalState (rand >>= \r -> monteCarlo (r ==) 100500) g
     print x

@serrr · 15.07.2013, 16:12 **[ТС]**

хорошо, ни в случае с

Сообщение от calabi-yau

Нужно как-то так: Код Haskell1
put (RndGen ((x*1367823 + 918237) `mod` 32768)) >> return x

ни в случае с использованием функций state и random явно фатальных ошибок не возникло, только что по поводу предикатной функции experiment, которая должна иметь сигнатуру Int -> Bool, но, как пишет интерпретатор - она не используется: "Warning: Defined but not used: `experiment'"? Я так смотрю, её сигнатура есть, а реализация не описана?

@calabi-yau · 15.07.2013, 17:19

Сообщение от serrr

Я так смотрю, её сигнатура есть, а реализация не описана?

Так это просто функция-аргумент функции monteCarlo.

@serrr · 04.08.2013, 13:37 **[ТС]**

Я еще кое-что уразумел, что нужно для понимания данной монады:
1) постоянно держать перед носом её определение, припоминая про синтаксис записи из главы про создание АТД, который генерирует функции для извлечения полей:

Code
1
2
3
4
5
6
7
8
9
10
11
12
data State s a = State { runState :: s -> (a, s) }
 
runState :: State s a -> s -> (a, s)
runState (State f) = f
 
-- Функция runState просто извлекает функцию из оболочки State.
 
-- State s также является экземпляром класса MonadState, который предоставляет две дополнительные функции get/put, при помощи которых мы получаем и устанавливаем состояние:
 
put newState = state $ \_ -> ((), newState)
 
get = state $ \st -> (st, st)

2) и какой-нибудь несложный пример

Code
1
2
3
factorial :: (Integral a) => a -> a
factorial 0 = 1
factorial n = n * factorial (n - 1)

и то же самое, но с реализацией монады State:

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
import Control.Monad.State
 
fact' :: Int -> State Int Int -- тип состояния - Int, тип результата - тоже Int
fact' 0 = do
    acc <- get -- получаем накопленный результат
    return acc -- возвращаем его
fact' n = do
    acc <- get -- получаем аккумулятор
    put (acc * n) -- домножаем его на n и сохраняем
    fact' (n - 1) -- продолжаем вычисление факториала
 
fact :: Int -> Int
fact n = fst $ runState (fact' n) 1 -- начальное значение состояния - 1

Кстати, я перевёл несколько статей по монаде State из викиучебника, и надеюсь, скоро выложу.

Добавлено через 6 минут
И последнее замечание, опять из викиучебника:

Кликните здесь для просмотра всего текста

В последних (2.0.0.0 и выше) версиях пакета mtl изменилась реализация монады State , так что модуль Control.Monad.State больше не экспортирует конструктор State . Вам следует заменить, как в примерах, так и при написании вашего кода, этот конструктор функцией state :: (s -> (a, s)) -> State s a, которая делает ту же самую работу. Чтобы избежать привнесения некоторых дополнительных сложностей, мы пока будем придерживаться старой версии с конструктором. Вы ничего не пропустите вследствие этого, так как изменение реализации не повлияет на те вопросы, которые мы будем обсуждать.

@Mysterious Light · 04.08.2013, 14:13

serrr, по моей просьбе сделайте следующее:

1. Оформляйте код тегом HASKELL, а не более общим CODE.

2. Вы привели «чистую от монад» реализацию factorial. Попробуйте переписать её, используя явно аккумулятор, чтоб логика функции соответствовала логике fact'.

3. Перепишите fact' 0, не используя do-нотацию, сокращая и упрощая по-максимуму выражение, делая его более понятным.

Можете не делать этого, если не хотите.

@Nameless One · 04.08.2013, 19:35

Сообщение от serrr

Haskell
1
2
acc <- get -- получаем аккумулятор
put (acc * n) -- домножаем его на n и сохраняем

modify (* n) выглядит лучше.

Вот с пожеланием #3 Mysterious Light:

Haskell
1
2
3
4
5
6
7
import Control.Monad.State
 
fact :: Integral a => a -> a
fact n = execState (fact' n) 1
    where fact' :: Integral a => a -> State a ()
          fact' 0 = return ()  -- зачем делать состояние возвращаемым значением?
          fact' n = modify (* n) >> fact' (n - 1)

Вот еще пример с монадой State: https://www.cyberforum.ru/post4912438.html

Сообщение от serrr

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

Какие сложности?

@serrr · 04.08.2013, 23:24 **[ТС]**

Mysterious Light,
1. Учту.
2. Как первый, так и второй пример с факториалом - не мои, я их просто привёл. С аккумулятором, говорите?

Haskell
1
2
3
4
Factorial_A (N) = F (N, 1)
 
F (0, A) = A
F (N, A) = F ((N - 1), (N * A))

Это из " Душкин Р.В. Лекция 3. «Структуры данных и базисные операции – 2»: Элементы программирования. Накапливающий параметр — аккумулятор"

Nameless One,
3. Спасибо.

Какие сложности?

То была просто уточнающая цитата из викикниги про монаду State. Ведь могла возникнуть путаница: я в определении монады указал конструктор State, а уже используется функция state, которая в get и put и я их указал по-новому, а не как раньше:

Haskell
1
2
get   = State $ \s -> (s, s) 
put s = State $ \_ -> ((), s)

@serrr · 12.08.2013, 21:54 **[ТС]**

Nameless One или кто ещё может,
объясните, пожалуйста, что конкретно функция get с помощью оператора <- сбрасывает в переменную? Как это выглядит - в виде какого-то одного числа (значение результата или состояние) или кортежа?
Например, в этом примере:

Haskell
1
2
3
4
5
postincrement = do { x <- get; put (x+1); return x }
 
runState postincrement 1
 
(1,2)

или пример с вики:

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import Control.Monad  -- Или, возможно, Control.Monad.State
import System.Random
 
type GeneratorState = State StdGen
 
rollDie :: GeneratorState Int
rollDie = do generator <- get
             let (value, newGenerator) = randomR (1,6) generator
             put newGenerator
             return value
 
-- Наконец, мы можем использовать нашу монадическую игральную кость:
> evalState rollDie (mkStdGen 0)
6

Тут объясняют (как я перевёл), что "с помощью <- из get вытаскиваем генератор псевдо-случайных чисел. get перезаписывает монадное значение ('a' в 'm a') состоянием, и, таким образом, генератор связан с состоянием..."
?

@calabi-yau · 13.08.2013, 02:13

Сообщение от serrr

объясните, пожалуйста, что конкретно функция get с помощью оператора <- сбрасывает в переменную? Как это выглядит - в виде какого-то одного числа (значение результата или состояние) или кортежа?

При помощи get мы получаем доступ к значению состояния.
Вообще

Haskell
1
postincrement = do { x <- get; put (x+1); return x }

стоит переписать без do нотации, например

Haskell
1
postincrement = get >>= \x -> put (x+1) >>= \_ ->  return x

и пользуясь определениями get, put и опреатора >>= попытаться разобраться, как происходит конструирование вычисления.

@serrr · 13.08.2013, 15:39 **[ТС]**

Сообщение от calabi-yau

При помощи get мы получаем доступ к значению состояния.

Хорошо. Как оно выглядит применительно к данному примеру?
Дело в том, что:
Чтение состояния. Это достигается с помощью get:

get = state $ \st -> (st, st)

Результирующий процессор состояния произведёт ввод st в обе позиции кортежа вывода - то есть, и как результат, и как состояние, для того, чтобы он мог бы связан с другими процессорами.

Та же функция в развернутом (упрощенном) виде:

get :: State s s
get s = (s,s)

-- например: get 1 -> (1,1)

В примере с postincrement, неважно с сахаром или без, первоначальным состоянием за её пределами будет 1. Потом его получает get. Дальше что? Какая единица передается в переменную х?
Потому что дальше последовательность процедур понятна, какая-то из единиц поступает в put, путем сложения, модифицирует результат к () и состояние к 2: (put (1+1)) 1 -> ((),2). Свой конечный результат ((),2) put дальше хоть и передаёт, но оператора return интересует значение из переменной x, и он видит, что благодаря put уже изменилось состояние 2, он берёт единицу из своей переменной x, изменившееся состояние, и заворачивает их в монаду.
Чтобы их вытащить из монады State, в финале используется runState.

@Mysterious Light · 13.08.2013, 17:00

Делаю то, что попросил Вас calabi-yau, а именно расписываю всё по определению, принебрегая словами State и runState.

Haskell
1
postincrement = get >>= \x -> put (x+1) >>= \_ ->  return x

Haskell
1
2
f >>= g  =  \s -> let (v,s') = f s in g v s'
f >>= g  =  \s -> g (fst $ f s) (snd $ f s)

Haskell
1
2
3
4
5
postincrement =
    get >>= \x -> ((\ _ -> ((),x+1)) >>= \ _ s -> (x,s)) =
    get >>= \x -> (\s -> (x,snd ((),x+1))) =
    (\s -> (s,s)) >>= \x s -> (x,x+1) =
    \s -> (s,s+1)

Как мы видим, после всех редукций получена упрощённая форма postincrement = State $ \s -> (s, s+1).
Даже если вместо get, которая является диагональю \s -> (s,s), поставить \s -> (s,undefined), получится одно и тоже. Можете сделать вывод о том, что только первая единица играет роль. Впрочем, все единицы ведь тождественны. Или нет?

@Nameless One · 13.08.2013, 17:21

serrr, нужно вспомнить определение State как монады и то, что do-нотация — это синтаксический сахар над монадами:

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
data State s a = State { runState :: s -> (a, s) }
 
instance Monad (State s) where
    return a = State $ \s -> (a, s)
    m >>= f  = State $ \s -> let (a, s') = runState m s in runState (f a) s'
 
get :: State s s
get = State $ \s -> (s, s)
 
put :: s -> State s ()
put s = State $ \_ -> ((), s)
 
postIncrement :: Num a => State a a
postIncrement = do x <- get
                   put (x + 1)
                   return x

Функции runState передаётся монада и начальное состояние. Функция get берёт это начальное состояние и превращает его в значение (первый элемент в кортеже) монады State. Дальше то, что записывается в виде do { x <- get; f x } следует воспринимать следущим образом: get >>= \x -> f x, т.к. второй аргумент оператора bind — это функция, которая принимает значение монады и возвращает новую монаду State. Далее с помощью put меняется состояние монады (при этом значение отбрасывается), затем с помощью return устанавливаем значение монады.

@serrr · 13.08.2013, 22:26 **[ТС]**

Сообщение от Nameless One

Функция get берёт это начальное состояние и превращает его в значение (первый элемент в кортеже) монады State.

В принципе, это пока всё, что я хотел знать. Было также интересно наблюдать, как postincrement была редуцирована до State $ \s -> (s, s+1), но я и так знал, что postincrement - это монада State, ведь несколько постов выше я указывал её продолжение:

Haskell
1
2
3
runState postincrement 1
 
(1,2)

Функции runState передаётся монада и начальное состояние

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

@Nameless One · 14.08.2013, 04:58

Сообщение от serrr

И ещё, очень хотелось бы знать, как вы оцениваете данную статью, которую я тут встретил: "Тройка полезных монад"

«Yet another monad tutorial», который мало чем отличается от других (кроме рисунков, которые, судя по задумке автора, призваны упростить подачу материала).

Новые блоги и статьи Все статьи Все блоги /
Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .
Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .	Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при создании или изменении элементов справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .

@Mysterious Light $Эксперт по математике/физике$ 4313 / 2105 / 431 Регистрация: 19.07.2009 Сообщений: 3,205 Записей в блоге: 24
	04.08.2013, 14:13
	serrr, по моей просьбе сделайте следующее: 1. Оформляйте код тегом HASKELL, а не более общим CODE. 2. Вы привели «чистую от монад» реализацию factorial. Попробуйте переписать её, используя явно аккумулятор, чтоб логика функции соответствовала логике fact'. 3. Перепишите fact' 0, не используя do-нотацию, сокращая и упрощая по-максимуму выражение, делая его более понятным. Можете не делать этого, если не хотите. 1