这个 State monad 代码是如何工作的?
How does this State monad code works?
此代码来自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
在这种情况下会产生什么?绝对不明白这一点。也许这与柯里化有关?
要实现的关键是 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
表示法。
Specifically do n <- fresh. We haven't passed any argument to fresh, right?
没错。例如,当我们做类似 apply (mlabel someTree) 5
的事情时,我们正在写一个论点,即 将 传递给 fresh
。一个很好的练习可以帮助您更清楚地看到正在发生的事情,首先用显式 (>>=)
代替 do-notation 编写 mlabel
,然后替换 (>>=)
和 return
正如 Monad
实例所说的那样。
内联 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 所做的就是为我们维护这个隐藏状态,并在连续计算之间传递更新。所以这毕竟不是什么主要。
此代码来自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
在这种情况下会产生什么?绝对不明白这一点。也许这与柯里化有关?
要实现的关键是 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
表示法。
Specifically do n <- fresh. We haven't passed any argument to fresh, right?
没错。例如,当我们做类似 apply (mlabel someTree) 5
的事情时,我们正在写一个论点,即 将 传递给 fresh
。一个很好的练习可以帮助您更清楚地看到正在发生的事情,首先用显式 (>>=)
代替 do-notation 编写 mlabel
,然后替换 (>>=)
和 return
正如 Monad
实例所说的那样。
内联 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 所做的就是为我们维护这个隐藏状态,并在连续计算之间传递更新。所以这毕竟不是什么主要。