Путаница в коде State Monad в Learn you a Haskell

Краткий ответ:

1. State предназначен для использования возможностей монад для имитации императивного состояния системы с локальными переменными. Основная идея состоит в том, чтобы скрыть внутри монады деятельность по принятию текущего состояния и возврату нового состояния вместе с промежуточным результатом на каждом шаге (и здесь у нас есть s -> (a,s).
2. Не путайте произвольные функции с функциями, заключенными в State. Первые могут иметь любой тип, который вы хотите (при условии, что они в конечном итоге производят несколько State a, если вы хотите использовать их в монаде состояний). Последний содержит функции типа s -> (a,s): это уровень передачи состояния, управляемый монадой.
3. Как я уже сказал, функция, заключенная в State, на самом деле создается с помощью (>>=) и return, как они определены для экземпляра Monad (State s). Его роль - передавать состояние через вызовы вашего кода.

Пункт 3 также является причиной того, что параметр состояния исчезает из функций, фактически используемых в монаде состояния.

Длинный ответ:

Государственная монада изучалась в разных статьях, а также существует во фреймворке Haskell (сейчас я не помню хороших ссылок, я добавлю их как можно скорее).

Это идея, которая следует из этого: рассмотрим тип data MyState = ..., значения которого содержат текущее состояние системы.

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

Функция, заключенная в State, не принимает параметров, кроме текущего состояния, которое необходимо для получения в результате нового состояния и промежуточного результата. Функции с большим количеством параметров, которые вы видели в примерах, не являются проблемой, потому что, когда вы используете их в do-нотации внутри монады, вы применяете их ко всем «лишним» необходимым параметрам, что означает, что каждый из них будет привести к частично примененной функции, единственным оставшимся параметром которой является состояние; экземпляр монады для State сделает все остальное.

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

Вычисление будет выполнено путем передачи всему блоку / композиции первого / начального состояния системы.

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

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

Поскольку функции в Haskell должны быть чистыми (т.е. не иметь побочных эффектов), мы имитируем эффект внешнего состояния, требуя, чтобы каждая функция принимала дополнительный параметр, представляющий текущее состояние мира, и возвращала дополнительное значение, представляющее измененное состояние. Фактически, внешнее состояние проходит через последовательность вычислений, как в этой мерзости диаграммы, которую я только что нарисовал в MSPaint:

Обратите внимание на то, что каждое поле (представляющее вычисление) имеет один вход и два выхода.

Если вы посмотрите на экземпляр Monad для State, вы увидите, что определение (>>=) говорит вам, как выполнять эту многопоточность. В нем говорится, что для привязки вычисления с сохранением состояния c0 к функции f, которая принимает результаты вычисления с сохранением состояния и возвращает другое вычисление с сохранением состояния, мы делаем следующее:

1. Запустите c0, используя начальное состояние s0, чтобы получить результат и новое состояние: (val, s1)
2. Подайте val в функцию f, чтобы получить новое вычисление с отслеживанием состояния, c1
3. Запустите новое вычисление c1 с измененным состоянием s1

Как это работает с функциями, которые уже принимают n аргументов? Поскольку каждая функция в Haskell по умолчанию каррирована, мы просто добавляем дополнительный аргумент (для состояния) в конец, и вместо обычного возвращаемого значения функция теперь возвращает пару, второй элемент которой является недавно измененным состоянием. Так что вместо

f :: a -> b

у нас теперь есть

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

Вы можете думать об этом как о

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

что то же самое в Haskell (поскольку композиция функций является правоассоциативной), которая гласит: «f - это функция, которая принимает аргумент типа a и возвращает вычисление с сохранением состояния». И это действительно все, что касается монады State.

Я новичок в Haskell, и я тоже не мог хорошо понять код State Monad в этой книге. Но позвольте мне добавить сюда свой ответ, чтобы помочь кому-то в будущем.

Ответы:

• Чего они пытаются достичь с помощью State Monad?

  Составные функции, которые обрабатывают вычисления с отслеживанием состояния.
  например push 3 >>= \_ -> push 5 >>= \_ -> pop
  
  

• Почему pop не принимает параметров, в то время как предполагается, что функция f принимает 1 параметр?

  pop не принимает аргументов, потому что она заключена в State.
  функция без замены, тип которой s -> (a, s), принимает один аргумент. то же самое касается push.
  вы можете развернуть с помощью runState.

  runState pop :: Stack -> (Int, Stack)
  runState (push 3) :: Stack -> ((), Stack)
  

  если вы имеете в виду правую часть >>= под «функцией f», f будет похоже на \a -> pop или \a -> push 3, а не только на pop.

Длинное объяснение:

Эти 3 вещи помогли мне немного лучше понять State Monad и пример стека.

• Рассмотрим типы аргументов для оператора привязки (>>=)

  Определение оператора связывания в классе типов Monad таково:

  (>>=) :: (Monad m) => m a -> (a -> m b) -> m b
  

  В примере со стеком m равно State Stack.
  Если мысленно заменить m на State Stack, определение может быть таким.

  (>>=) :: State Stack a -> (a -> State Stack b) -> State Stack b 

  Следовательно, тип аргумента левой стороны для оператора связывания будет State Stack a.
  А тип правой стороны будет a -> State Stack b.
  
  

• Перевести нотацию do в оператор привязки

  Вот пример кода в книге с использованием нотации do.

  stackManip :: State Stack Int  
  stackManip = do  
       push 3  
       pop  
       pop  
  

  его можно преобразовать в следующий код с помощью оператора привязки.

  stackManip :: State Stack Int  
  stackManip = push 3 >>= \_ -> pop >>= \_ -> pop
  

  Теперь мы можем увидеть, что будет с правой стороны для оператора связывания.
  Их типы a -> State Stack b.

  (\_ -> pop) :: a -> State Stack Int
  (\_ -> push 3) :: a -> State Stack ()
  

  
  

• Обратите внимание на разницу между (State s) и (State h) в объявлении экземпляра

  Вот объявление экземпляра для State в книге.

  instance Monad (State s) where  
      return x = State $ \s -> (x,s)  
      (State h) >>= f = State $ \s -> let (a, newState) = h s  
                                          (State g) = f a  
                                      in  g newState 
  

  Учитывая типы в примере Stack, тип (State s) будет

  (State s) :: State Stack
  s :: Stack
  

  И тип (State h) будет

  (State h) :: State Stack a
  h :: Stack -> (a, Stack)
  

  (State h) - это левый аргумент оператора связывания, его тип - State Stack a, как описано выше.
  

  Тогда почему h становится Stack -> (a, Stack)?
  Это результат сопоставления шаблонов с конструктором значения State, который определен в оболочке newtype. То же самое и с (State g).

  newtype State s a = State { runState :: s -> (a,s) }
  

  В общем, типом h является s ->(a, s), представление вычислений с отслеживанием состояния. Любое из следующих значений может быть h в примере Stack.

  runState pop :: Stack -> (Int, Stack)
  runState (push 3) :: Stack -> ((), Stack)
  runState stackManip :: Stack -> (Int, Stack)
  

  это оно.

Монада State по сути

type State s a = s -> (a,s)

функция от одного состояния (s) до пары желаемого результата (a) и нового состояния. Реализация делает потоки состояния неявным и обрабатывает передачу состояния и обновление за вас, поэтому нет риска случайной передачи неправильного состояния следующей функции.

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

В настройке, отличной от состояния, pop принимает один аргумент, стек, который является состоянием. Таким образом, в монадической настройке pop становится действием State Stack Int без явного аргумента.

Использование монады State вместо явной передачи состояния делает код более чистым с меньшими возможностями для ошибки, что и выполняет монада State. Без него все можно было бы сделать, просто это было бы более громоздко и подвержено ошибкам.