这个州的monad代码是如何工作的？ [英] How does this State monad code works?
问题描述
此代码来自文章
我已经能够跟随它，直到这部分。
module测试其中
type State = Int
data ST a = S（State - >（a，State））
apply :: ST a - >状态 - > （a，State）
apply（S f）x = fx
fresh = S（\ n - >（n，n + 1））
实例Monad ST其中
- 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（sx）s'）
data树a =叶a |节点（树a）（树a）派生（显示）
mlabel :: Tree a - > ST（Tree（a，Int））
- 这是我不知道的部分：
mlabel（Leaf x）= do n < - fresh
return（Leaf（x ，n））
mlabel（Node lr）= do l'< - mlabel l
r'< - mlabel r
return（Node l'r'）
标签t = fst（apply（mlabel t）0）
tree = Node（节点（Leaf'a'）（Leaf'b'））（Leaf'c'）
和标签树产生：
$ b
））
我可以看到>> = 操作符是'链'函数返回monads（或类似的东西）的工具。
虽然我认为我理解这段代码，但是我没有了解这个特定的代码是如何工作的。
特别是 do n < - fresh 。我们没有通过任何新鲜的理由，对吧？在这种情况下， n < - fresh 产生了什么？绝对不了解这一点。也许它与咖喱有关？
随着monadic流水线内联，您的代码变为
<$ （state，state + 1）
mlabel（Leaf x）state = - do
let（n，state'）=新鲜状态 - n < - 新鲜
in（Leaf（x，n），state'） - return（Leaf（x，n））
mlabel（Node lr）state （r'，state''）= mlabel r state' - = do
let（l'，state'）= mlabel l state - l'< - mlabel l
r'< - mlabel r
in（节点1'r'，状态''） - 返回（节点1'r'）
main = let（result，state'） = mlabel tree 0
打印结果
{ - 或者用箭头，
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>>>打印$ 0
- }
或者在命令式伪代码中：
def state = unassigned
def fresh（）：
tmp = state
state：= state + 1 - `fresh`改变全局变量`state`
return tmp - 每次调用
def mlabel（Leaf x）： - 一种模式匹配的语言
n = fresh（） - 全局`state`被改变！
return（Leaf（x，n））
def mlabel（Node lr）：
l'= mlabel l - 影响全局
r'= mlabel r - 可分配变量
返回（节点l'r'） - `状态`
def main：
state：= 0 - 在计算前设置为0！
结果= mlabel树
打印结果
计算 result 改变状态赋值;它对应于Haskell的（a，State）元组中的 snd 字段。并且元组的 fst 字段是新构建的树，在它的叶子中携带一个数字和它的数据。
这些变体在功能上是等效的。
也许你已经听说过关于monadic bind是一个可编程分号的catch-phrase。在这里它的含义很清楚：它定义了函数调用协议，可以这么说，我们使用第一个返回值作为计算结果，第二个返回值作为更新状态，我们将其传递给下一个计算，所以它会看到更新状态。
这是状态传递编程风格（对于例如Prolog是必不可少的），使状态更改显式化，但必须手动手动注意传递正确的更新状态。 Monad允许我们抽象出这种从一种计算到下一种计算的状态布线，因此它是为我们自动完成的，其代价是必须以命令式的方式进行思考，并且让这种状态变得隐藏，再次隐含（像状态变化隐含在命令式编程中，当我们切换到函数式编程时，我们首先想避开这个变化......）。
所以，所有状态monad正在做的就是为我们维护这个隐藏状态，并在连续计算之间传递它。所以毕竟它不是主要的。
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?
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.
这篇关于这个州的monad代码是如何工作的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
