Государственная Монада, почему не кортеж? - PullRequest
Новая
       21

Государственная Монада, почему не кортеж?

9 голосов
/ 08 апреля 2010

Я только что обернул голову вокруг монад (по крайней мере, мне бы хотелось так думать) и, более конкретно, государственной монады, которую некоторые люди, которые были намного умнее меня, выяснили, так что я, вероятно, способс этим вопросом.

В любом случае, монада состояний обычно реализуется с помощью M <'a> примерно так (F #): 

type State<'a, 'state> = State of ('state -> 'a * 'state)

Теперь мой вопрос: есть ли причинапочему вы не можете использовать кортеж здесь?Кроме возможной неоднозначности между MonadA<'a, 'b> и MonadB<'a, 'b>, которые оба станут эквивалентными ('a * 'b) кортежами.

Редактировать: Добавлен пример для ясности 

type StateMonad() =
  member m.Return a = (fun s -> a, s)
  member m.Bind(x, f) = (fun s -> let a, s_ = x s in f a s_)

let state = new StateMonad()
let getState = (fun s -> s, s)
let setState s = (fun _ -> (), s) 
let execute m s = m s |> fst

Ответы [ 3 ]

12 голосов
/ 08 апреля 2010

Монада State по существу работает с типом 'state -> 'res * 'state, который представляет вычисление, которое принимает некоторое начальное состояние и выдает результат (вместе с новым значением состояния).

Если вы спрашиваете, имеет ли какое-то значение, даем ли мы какое-то специальное имя этому типу (например, State<'state, 'res>), тогда ответ на самом деле не имеет значения. Единственная цель присвоения некоторого специального имени типу состоит в том, чтобы сделать код более читабельным. Например, давайте рассмотрим две возможные сигнатуры типов в следующем примере: 

let foo n = state {
  let! m = getState()
  do! setState(m + 1)
  return sprintf "Result: %d" (n * m) }

// Using State<'state, 'res> type:
val foo : int -> State<int, string>

// Using the underlying representation:
val foo : int -> int -> int * state

Первый тип подписи более четко говорит о том, что мы пишем функцию в некоторой монаде. Второй пример - это просто функция, которая принимает два значения int. Я думаю, что главное преимущество первого состоит в том, что вы можете легче понять, что тип может использоваться из других монадических вычислений (написанных с использованием state { ... }).

Однако, как я уже отметил, это не техническое требование. Люди, вероятно, используют этот стиль, потому что многие монады происходят из Хаскелла, где монады связаны с типом (например, State<'state, 'res>), а не с компилятором (например, state). ), поэтому неплохо определить новый тип для каждой монады в Haskell.

6 голосов
/ 08 апреля 2010

Тип монадического значения в вашем примере - это не просто кортеж - это функция, возвращающая кортеж: 

'state -> 'res * 'state

Если вы спрашиваете, можете ли вы использовать просто 'state * 'res в качестве типа монадического вычисления, тогда ответ - нет. Это не сработает, потому что нет способа (безопасно) реализовать операцию возврата, которая должна иметь следующую сигнатуру типа: 

// how would we get a value of type 'state in the implementation?
val return : 'a -> 'state * 'a
5 голосов
/ 08 апреля 2010

Ах, да, если вопрос таков: должен ли я использовать Дискриминационный Союз с одним тегом, который несет значение данных типа T, или я должен просто использовать T, тогда вы можете использовать любой из них.

В Haskell вам необходимо использовать тег данных с монадами, поскольку синтаксис Haskell do выводит тип монады на основе типов значений (представление кортежа может быть экземпляром не более одной монады). В то время как в F # выражения вычисления явно относятся к типу монады (например, state { ... } или async { ... } или как угодно), поэтому это ограничение не является необходимым, один и тот же тип представления может использоваться для нескольких монад.

...