状态 monad 如何绑定到外部上下文

Question

我正在尝试理解 State monad，我必须承认我非常困惑。我创建了一个计算表达式并添加了很多打印语句，这样我就可以跟进谁在什么时候被调用了。

type State<'st,'a> =
    | Ok of  'a * 'st
    | Error of string
and StateMonadBuilder() =
    member b.Return(x) = printfn "100 Return %A" x; fun s -> Ok (x, s)
    member b.ReturnFrom(x) = printfn "100 ReturnFrom %A" x; x
    member b.Bind(p, rest) =
        printfn "100 Bind:: %A %A" p rest
        fun state ->
            printfn "200 Bind:: %A %A" p rest
            let result = p state in
            match result with
            | Ok (value,state2) -> (rest value) state2
            | Error msg -> Error msg  

    member b.Get () = 
        printfn "100 Get"
        fun state -> 
            printfn "200 Get :: %A" state
            Ok (state, state)
    member b.Put s = fun state -> Ok ((), s)

let state = StateMonadBuilder()

let turn () =
    state {
        printfn "100 turn::"
        let! pos1 = state.Get()
        printfn "200 turn:: %A" pos1
        let! pos2 = state.Get()
        printfn "300 turn:: %A" pos1
        return! state.Put(fst pos1, snd pos1 - 1)
    }

let move () =
    state {
        printfn "100 move::"
        let! x = turn()
        printfn "200 move:: %A" x
        let! y = turn()
        printfn "200 move:: %A" y
        return x
    }

let run () =
    state {
        printfn "100 run::"
        do! move()
    }

run () (5,5) |> ignore

以上代码打印出如下输出

100 run::
100 move::
100 turn::
100 Get
100 Bind:: <fun:Get@301> <fun:turn@312>
100 Bind:: <fun:Bind@292-2> <fun:move@322>
100 Bind:: <fun:Bind@292-2> <fun:run@329>
200 Bind:: <fun:Bind@292-2> <fun:run@329>
200 Bind:: <fun:Bind@292-2> <fun:move@322>
200 Bind:: <fun:Get@301> <fun:turn@312>
200 Get :: (5, 5)
200 turn:: (5, 5)
100 Get
100 Bind:: <fun:Get@301> <fun:turn@314-1>
200 Bind:: <fun:Get@301> <fun:turn@314-1>
200 Get :: (5, 5)
300 turn:: (5, 5)
100 ReturnFrom <fun:Put@304>
200 move:: <null>
100 Return <null>
100 Return <null>

我理解此输出的前 5 行。显然run调用move调用turn调用Get。然后有一个 let! pos1 = ... 触发对 Bind 的调用。到目前为止，一切都很好。但是随后还有对 Bind 的额外调用。它们是如何产生的？我从表面上理解绑定到那些外部上下文一定是状态 monad 的魔力，但这种机制是如何工作的？然后在函数 turn 中还有另一个 let! pos2 = ... 也会触发 Bind 但这次只有一次，而不是之前的 3 次！

期待您的讲解

Answer 1

没有魔法，一切都是烟雾和镜子。

您在工作流程中建立的计算是 'st -> State<'st, 'a> 类型的一大功能。您调用 run 的地方实际上是您将此函数应用于初始参数的地方 - 这就是通过绑定传递的内容，反过来，从 "parent" move 工作流程到 turn。因此，并不是您的嵌套工作流正在访问外部的任何内容 - 您自己将其传递到那里。

您做出的一个 non-standard 选择 - 这可能不会让您更容易理解正在发生的事情 - 是您的 State monad 不是纯粹的 state monad，而是结合了 State 和Either/Maybe monads（通过 State 类型的 Error case）。当你定义 State 类型时，你这里的实际 monadic 类型是我之前提到的函数类型。

典型的方法是将类型定义为如下所示：

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

即您使用单个 case 联合作为函数类型的包装器，或者只使用没有包装类型的函数。错误处理通常不是 state monad 处理的问题。

至于问题的第二部分，您的路径上确实有三个绑定 - do! move()、let! x = turn() 和 let! pos1 = state.Get() - 这就是您在日志中看到的内容.我认为事情发生的顺序在这里可能很棘手。

记住绑定是如何脱糖的：

{| let! pattern = expr in cexpr |} => builder.Bind(expr, (fun pattern -> {| cexpr |}))

这意味着首先计算 expr，然后才调用 Bind，最后才是计算的其余部分 cexpr。在你的情况下，你去 "three binds deep" 评估第一个 expr - 这是对 Get() 的调用 - 然后你开始解析你的绑定堆栈，在某些时候调用另一个绑定作为cexpr.

如果在 Bind 中计算 let result = p state 之后添加另一个打印语句，这可能会更容易看到真正发生的事情，这是解除绑定的时候。

状态 monad 如何绑定到外部上下文

How does the state monad bind into outer context

f#

state-monad