这个州的monad代码是如何工作的？(How does this State monad code works?)

这个州的monad代码是如何工作的？(How does this State monad code works?)

这段代码来自这篇文章

直到这一部分，我才能够遵循它。

module Test where type State = Int data ST a = S (State -> (a, State)) apply :: ST a -> State -> (a,State) apply (S f) x = f x fresh = S (\n -> (n, n+1)) instance Monad ST where -- return :: a -> ST a return x = S (\s -> (x,s)) -- (>>=) :: ST a -> (a -> ST b) -> ST b st >>= f = S (\s -> let (x,s') = apply st s in apply (f x) s') data Tree a = Leaf a | Node (Tree a) (Tree a) deriving (Show) mlabel :: Tree a -> ST (Tree (a,Int)) -- THIS IS THE PART I DON'T UNDERSTAND: mlabel (Leaf x) = do n <- fresh return (Leaf (x,n)) mlabel (Node l r) = do l' <- mlabel l r' <- mlabel r return (Node l' r') label t = fst (apply (mlabel t) 0) tree = Node (Node (Leaf 'a') (Leaf 'b')) (Leaf 'c')

label tree产生：

Node (Node (Leaf ('a',0)) (Leaf ('b',1))) (Leaf ('c',2))

我可以看到>>=操作符是'链'返回单子（或类似的东西）的函数的工具。

虽然我认为我理解这个代码，但我不明白这个特定的代码是如何工作的。

具体do n <- fresh 。 我们没有通过任何新鲜的理由，对吧？ 在这种情况下n <- fresh产生了什么？ 绝对不了解这一点。 也许它与咖喱有关？

This code is from this article

I've been able to follow it until this part.

module Test where type State = Int data ST a = S (State -> (a, State)) apply :: ST a -> State -> (a,State) apply (S f) x = f x fresh = S (\n -> (n, n+1)) instance Monad ST where -- return :: a -> ST a return x = S (\s -> (x,s)) -- (>>=) :: ST a -> (a -> ST b) -> ST b st >>= f = S (\s -> let (x,s') = apply st s in apply (f x) s') data Tree a = Leaf a | Node (Tree a) (Tree a) deriving (Show) mlabel :: Tree a -> ST (Tree (a,Int)) -- THIS IS THE PART I DON'T UNDERSTAND: mlabel (Leaf x) = do n <- fresh return (Leaf (x,n)) mlabel (Node l r) = do l' <- mlabel l r' <- mlabel r return (Node l' r') label t = fst (apply (mlabel t) 0) tree = Node (Node (Leaf 'a') (Leaf 'b')) (Leaf 'c')

And label tree produces:

Node (Node (Leaf ('a',0)) (Leaf ('b',1))) (Leaf ('c',2))

I can see that >>= operator is the tool to 'chain' functions that return monads (or something like that).

And while I think I understand this code, I don't understand how this particular code works.

Specifically do n <- fresh. We haven't passed any argument to fresh, right? What does n <- fresh produces in that case? Absolutely don't understand that. Maybe it has something to do with currying?

最满意答案

随着monadic“流水线”内联，你的代码变成了

fresh state = (state, state + 1) mlabel (Leaf x) state = -- do let (n, state') = fresh state -- n <- fresh in (Leaf (x,n), state') -- return (Leaf (x,n)) mlabel (Node l r) state = -- do let (l', state') = mlabel l state -- l' <- mlabel l in let (r', state'') = mlabel r state' -- r' <- mlabel r in (Node l' r', state'') -- return (Node l' r') main = let (result, state') = mlabel tree 0 in print result {- Or with arrows, mlabel (Leaf x) = Leaf . (x ,) &&& (+ 1) mlabel (Node l r) = mlabel l >>> second (mlabel r) >>> (\(a,(b,c)) -> (Node a b,c)) main = mlabel tree >>> fst >>> print $ 0 -}

或者在一个命令性的伪代码中：

def state = unassigned def fresh (): tmp = state state := state + 1 -- `fresh` alters the global var `state` return tmp -- each time it is called def mlabel (Leaf x): -- a language with pattern matching n = fresh () -- global `state` is altered! return (Leaf (x,n)) def mlabel (Node l r): l' = mlabel l -- affects the global r' = mlabel r -- assignable variable return (Node l' r') -- `state` def main: state := 0 -- set to 0 before the calculation! result = mlabel tree print result

计算result改变可分配的state ; 它对应于Haskell (a, State)元组中的snd字段。 而元组的fst字段是新构建的树，在它的叶子上携带一个数字和数据。

这些变体在功能上等同。

也许你已经听到关于monadic bind是一个“可编程分号”的口头禅。 在这里它的含义很清楚：它定义了“函数调用协议”，可以这么说，我们使用第一个返回值作为计算结果，第二个返回值作为更新状态，我们将其传递给下一个计算，所以它会看到更新的状态。

这是一种传统的编程风格（对于例如Prolog而言是必不可少的），使得状态变化明确，但不得不手动处理正确的更新状态。 Monad允许我们抽象出这种从一种计算到下一种计算的状态“布线”，因此它是为我们自动完成的，其代价是必须以命令式的方式进行思考，并且让这种状态变得隐藏，再次隐含（像状态变化是隐含在命令式编程中的，当我们切换到函数式编程时，我们首先想避免这种变化...）。

所以国家monad正在做的就是为我们保留这个隐藏状态，并在连续计算之间更新它。 所以它毕竟没什么特别的。

With the monadic "pipelining" inlined, your code becomes

fresh state = (state, state + 1) mlabel (Leaf x) state = -- do let (n, state') = fresh state -- n <- fresh in (Leaf (x,n), state') -- return (Leaf (x,n)) mlabel (Node l r) state = -- do let (l', state') = mlabel l state -- l' <- mlabel l in let (r', state'') = mlabel r state' -- r' <- mlabel r in (Node l' r', state'') -- return (Node l' r') main = let (result, state') = mlabel tree 0 in print result {- Or with arrows, mlabel (Leaf x) = Leaf . (x ,) &&& (+ 1) mlabel (Node l r) = mlabel l >>> second (mlabel r) >>> (\(a,(b,c)) -> (Node a b,c)) main = mlabel tree >>> fst >>> print $ 0 -}

Or in an imperative pseudocode:

def state = unassigned def fresh (): tmp = state state := state + 1 -- `fresh` alters the global var `state` return tmp -- each time it is called def mlabel (Leaf x): -- a language with pattern matching n = fresh () -- global `state` is altered! return (Leaf (x,n)) def mlabel (Node l r): l' = mlabel l -- affects the global r' = mlabel r -- assignable variable return (Node l' r') -- `state` def main: state := 0 -- set to 0 before the calculation! result = mlabel tree print result

Calculating the result changes the state assignable; it corresponds to the snd field in Haskell's (a, State) tuple. And the fst field of the tuple is the newly constructed tree, carrying a numbering alongside its data in its leaves.

These variants are functionally equivalent.

Perhaps you've heard the catch-phrase about monadic bind being a "programmable semicolon". Here the meaning of it is clear: it defines the "function call protocol" so to speak, that we use the first returned value as a calculated result, and the second returned value as the updated state, which we pass along to the next calculation, so it gets to see the updated state.

This is the state-passing style of programming (essential for e.g. Prolog), making the state change explicit but having to manually take care of passing along the correct, updated state. Monads allow us to abstract this "wiring" of state passing from one calculation to the next, so it is done automatically for us, at the price of having to think in imperative style, and having this state become hidden, implicit again (like the state change is implicit in the imperative programming, which we wanted to eschew in the first place when switching to the functional programming...).

So all that the State monad is doing is to maintain for us this hidden state, and passing it along updated between the consecutive calculations. So it's nothing major after all.