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

Question

此代码来自本文

我已经能够遵循它直到这一部分.

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

我可以看到>>=运算符是"链接"返回monad(或类似的东西)函数的工具.

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

具体do n <- fresh.我们还没有通过任何争论,对吧？n <- fresh在那种情况下会产生什么？绝对不明白.也许它与currying有关？

Answer 1

特别是n < - fresh.我们还没有通过任何争论,对吧？

究竟.我们正在编写一个参数,这个参数将被传递给fresh我们,例如,当我们做类似的事情时apply (mlabel someTree) 5.一个很好的锻炼,这将帮助你更清楚地看到正在发生的事情是第一次写mlabel有明确的(>>=)而不是DO-符号,然后更换(>>=)和return用什么Monad情况下说,他们是.

Answer 2

要实现的关键是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') ))

这将有助于您继续查明代码的含义,但是为了获得更多帮助,您应该阅读doMonads 的符号.