这个 State monad 代码是如何工作的？

Question

此代码来自article

我一直能跟到这部分。

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))

我可以看到 >>= 运算符是 'chain' 函数的工具 return 单子（或类似的东西）。

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

具体来说 do n <- fresh。我们没有向 fresh 传递任何参数，对吗？ n <- fresh 在这种情况下会产生什么？绝对不明白这一点。也许这与柯里化有关？

Answer 1

要实现的关键是 do 符号被转换为 Monad 函数，所以

do n <- fresh
   return (Leaf (x,n))

是

的缩写

fresh >>= (\n -> 
           return (Leaf (x,n))  )

和

do l' <- mlabel l
   r' <- mlabel r
   return (Node l' r')

是

的缩写

mlabel l >>= (\l' -> 
              mlabel r >>= (\r' ->
                            return (Node l' r') ))

这有望让您继续弄清楚代码的含义，但要获得更多帮助，您应该阅读 Monad 的 do 表示法。

Answer 2

Specifically do n <- fresh. We haven't passed any argument to fresh, right?

没错。例如，当我们做类似 apply (mlabel someTree) 5 的事情时，我们正在写一个论点，即将传递给 fresh。一个很好的练习可以帮助您更清楚地看到正在发生的事情，首先用显式 (>>=) 代替 do-notation 编写 mlabel，然后替换 (>>=) 和 return正如 Monad 实例所说的那样。

Answer 3

内联 monadic "pipelining" 后，您的代码变为

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 字段是新构造的树，在其叶子中的数据旁边带有编号。

这些变体在功能上是等效的。

也许您听说过关于单子绑定是 "programmable semicolon" 的流行语。这里的意思很明确：它定义了"function call protocol"可以这么说，我们使用第一个返回值作为计算结果，第二个返回值作为更新状态，我们传递给下一个计算，所以它会看到 updated 状态。

这是状态传递编程风格（对于例如 Prolog 至关重要），使状态更改显式但必须手动注意传递正确的更新状态。 Monads 允许我们抽象这种从一个计算传递到下一个计算的状态 "wiring"，所以它是自动为我们完成的，代价是必须以命令式的方式思考，并且让这个状态变得隐藏，再次隐式（就像状态变化隐含在命令式编程中一样，我们希望在切换到函数式编程时首先避开它...)。

所以 State monad 所做的就是为我们维护这个隐藏状态，并在连续计算之间传递更新。所以这毕竟不是什么主要。

这个 State monad 代码是如何工作的？

How does this State monad code works?

haskell

monads

state-monad