状态Monad - HASKELL

nqwrtyyt 于 12个月前发布在其他

关注(0)|答案(1)|浏览(129)

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') = app st s
                            in app (f x) s')

type State = Int
newtype ST a = S (State -> (a, State))

data Tree a = Leaf a | Node (Tree a) (Tree a) deriving (Show)

app :: ST a -> State -> (a, State)
app (S st) s = st s

mlabel :: Tree a -> ST (Tree Int)
mlabel (Leaf _) = fresh >>= (\n -> return (Leaf n))
mlabel (Node l r) = mlabel l >>= (\l ->
                    mlabel r >>= (\r ->
                    return (Node l r)))

fresh :: ST Int
fresh = S (\n -> (n , n +1))

嗨，这是我的代码，我想确保我对mlabel函数扩展的理解是正确的。我没有使用任何额外的导入。

So suppose mlabel gets a input of Leaf 'a'

fresh >>== (\n -> return (Leaf n))
S (\n -> (n, n+1) >>== (\n -> return (Leaf n))
= S (\s -> let (x, s') = app (S (\n -> (n, n+1)) s
               (x, s') = (s, s+1)
               in app ((\n -> return (Leaf n) x) s'
                = app (S (\x -> (Leaf x, x+1)) s'
                = (\x -> (Leaf x, x+1) s'
                = (Leaf s+1, (s+1)+1)

型

haskell

来源：https://stackoverflow.com/questions/77474598/state-monad-haskell

1条答案

按热度按时间

uttx8gqw1#

你还没有包含这个monad的>>=和return操作的定义，但我假设你有这样的东西：

return x = S (\s -> (x, s))

a >>= f = S $ \s ->
  let (x, s') = app a s
  in app (f x) s'

字符串
如果是这样的话，你的扩展就有问题了：

app ((\n -> return (Leaf n) x) s'
=   app (S (\x -> (Leaf x, x+1)) s'

型
你在第一行少了一个右括号，我想你跳过了太多的步骤，把自己弄糊涂了。
无论如何，这应该看起来更像这样：

app ((\n -> return (Leaf n)) x) s'
=   app (return (Leaf x)) s'                -- apply lambda
=   app (S (\s -> (Leaf x, s))) s'          -- definition of `return`
=   (Leaf x, s')                            -- evaluate `app`

型

现在 *，当我们从let (x, s') = (s, s+1) in ...代入x和s'的值时，我们得到：

=   (Leaf s, s+1)

型
而不是(Leaf s+1, (s+1)+1)。
重写整个let xxx in yyy语句而不是单独重写xxx和yyy部分可能更安全，所以：

S $ \s -> let (x, s') = app (S (\n -> (n, n+1))) s
              in app ((\n -> return (Leaf n)) x) s'
-- apply lambda
=   S $ \s -> let (x, s') = app (S (\n -> (n, n+1))) s
              in app (return (Leaf x)) s'
-- definition of `return`
=   S $ \s -> let (x, s') = app (S (\n -> (n, n+1))) s
              in app (S (\s -> (Leaf x, s))) s'
-- expand both `app` calls:
=   S $ \s -> let (x, s') = (s, s+1)
              in (Leaf x, s')
-- substitute `let` definitions:
=   S $ \s -> (Leaf s, s+1)

型

赞(0）回复(0）举报 12个月前

我来回答

状态Monad - HASKELL

1条答案

相关问题

热门标签

最新问答