Попытка получить привязку, работающую для комбинации State и Delayed monad

Question

Если ответ на этот вопрос "ты все делаешь неправильно", непременно дай мне знать более правильный путь. У меня был код, который был структурирован так:

type Res<'T> =
    | E of (DC -> 'T)
    | V of 'T

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

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

type Res<'T> =
    | E of (DC -> DC * 'T)
    | V of 'T

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

type Res<'T> =
    | E of (DC -> DC * Res<'T>)
    | V of 'T

Я попробовал несколько вариантов следующего, но продолжаю получать:

Результирующий тип будет бесконечным при объединении ''a'и' Res<'a> -> Res<' b>'

(обычно происходит, когда я не вызываю возврат, т.е. Res.E <| ниже)

Или я не могу понять свои типы правильно, следующее (понятно) выдает ошибку типа, но у меня есть слепое пятно, исправляющее это:

Ожидается, что это выражение будет иметь тип 'Res<' a>', но здесь имеет тип' DC * Res<'a>'.

let rec bind k res =
    match res with
    | Res.V v -> k v      // not delayed, should it be?
    | Res.E e -> 
        Res.E <| fun dc -> bind k (e dc)   // here's my error, on 'e dc'
         //(fun dc -> dc, bind f (e dc))
bind k res

Я понимаю, что подпись должна быть ('a -> Res<'b>) -> Res<'a> -> XRes<'b>, Проблема возникает из-за правильной рекурсии, по крайней мере, в моей голове. Я даже не уверен, почему я кормлю результат Res.Eкак я понимаю k в любом случае продолжение должно возвращать этот тип.

Кроме того, у меня в настоящее время есть возвращение следующим образом (после Стива Хорсфилда):

let result v = Res.V v

Но также заметил в некоторых сообщениях (особенно веселый Frankenfunctor) это:

let result v = Res.E <| fun dc -> dc, Res.V v

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

Но я чувствую, что я рядом... Есть идеи?

Answer 1

Я не совсем уверен, что смысл этой монады будет, но
Хорошо, подумав немного и прочитав заголовок вопроса:-), я понимаю, что это значит, и я вижу, как построить bind для этого.

Ваша ошибка в том, что функция завернута в Res.E должен вернуть кортеж, но вы получите его вернуть просто Res<'b> рекурсивно вызывая bind, И чтобы отразить это, вы передаете результат e рекурсивный bind позвонить вместо Res<'b> параметр, в то время как e на самом деле возвращает кортеж.

Чтобы сделать это правильно, вам нужно деструктурировать результат e, затем передайте вторую часть рекурсивной bind вызовите, и соедините его результат с первой частью:

let rec bind (k: 'a -> 'b Res) (res: 'a Res) : 'b Res =
  match res with
  | V a -> k a
  | E e -> 
      E <| fun dc -> 
        let dc', res' = e dc 
        dc', bind k res'

Терминальный случай, я не верю, должен быть отсрочен. То есть я не вижу причины для этого. Насколько я понимаю, интерпретация V x case должен быть " вычислением, которое не меняет состояние и возвращает x ", в этом случае задержка не добавляет ничего, кроме дополнительного лямбда-выражения.