Monad变换器：使用MaybeT（状态堆栈）实现堆栈机器 [英] Monad transformers: Implementation of a stack machine with MaybeT (State Stack)

问题描述

我试图实现一个Maybe-State monad变换器并使用它来实现一个简单的堆栈机器。
状态monad的定义也许应该是正确的。现在我试图实现pop：

preop $ MaybeT（State Stack）Int
只需<弹出堆栈> $ b> C $ C>。
这是我到目前为止：

  pop :: MaybeT（状态堆栈）Int 
 pop = guard True（do（r：rs）<  -  get 
 put rs 
 return r）
  

（很明显， True 只是一个虚拟的占位符 - 稍后我会实现这个条件，因为现在我想让其他部分正确） p>

我的代码有什么问题？根据我的理解， guard 需要一个条件（ True ）和一个函数f。如果条件为真，它会给出纯f 。

在我的例子中，

  pure = MaybeT。返回。只是
  

所以我的函数f不应该返回一个 State Stack Int ？

---

下面是完整的代码，我的 MaybeT 和 State ：

  import Control.Applicative（Alternative（..） ）
 import Control.Monad（liftM，ap，guard）
 import Control.Monad.Trans.Class（MonadTrans（lift））
 $ b $ main :: IO（）
 main = return（）
 
 
  -  State Monad 
 -------------- 
 
 newtype状态sa = MakeState {runState :: s  - > （a，s）} 
 
实例Functor（State s）其中
 fmap = liftM 
 
 
实例（State）其中
 pure a = MakeState $ \s  - > （a，s）
（*）= ap 
 
实例Monad（State）其中
返回a = MakeState $ \s-> （a，s）
 m>> = k = MakeState $ \s->在runState（k x）s'中获得（x，s'）= runState m s 
获得:: State :: s 
 get = MakeState $ \ s  - > （s，s）
 
 put :: s  - > State s（）
 put s = MakeState $ \_  - > （（），s）
 
 modify ::（s  - > s） - >状态s（）
修改f = MakeState $ \s  - > （（），fs）
 
  -  MaybeT MonadTransformer 
 --------------------------- 
 
 newtype MaybeT ma = MaybeT {runMaybeT :: m（也许a）} 
 
实例Monad m => Functor（MaybeT m）其中
 fmap ax = MaybeT $ do e < -  runMaybeT x 
 return $ fmap ae 
 
 
 
实例Monad m = > Applicative（MaybeT m）其中
 pure = MaybeT。返回。只要
（*）a b = MaybeT $ do e < -  runMaybeT a 
 f < -  runMaybeT b 
 return $ e * f 
 
实例Monad m => Monad（MaybeT m）其中
 return = pure 
a>> = b = MaybeT $ do aa<  -  runMaybeT a 
也许（return Nothing）（runMaybeT。b）aa 
 
 
实例Monad m => Alternative（MaybeT m）其中
 empty = MaybeT $ return Nothing 
 a< |> b = MaybeT $ do aa<  -  runMaybeT a 
 bb<  -  runMaybeT b 
 return $ aa< |> bb 
 
 
实例MonadTrans MaybeT其中
  - herwrappenvan het参数
 lift x = MaybeT $ do r < -  x 
 return $只需
 
 
  - 堆栈操作
 --------------------- 
 
类型Stack = [Int] 
 
  -  plaats het参数bovenop de stack 
 push :: Int  - >状态堆栈（）
 push x =执行r < - 获取
 put（x：r）
  - 存储栈中的元素terug 
 size :: State Stack Int 
 size = do r < -  get 
 return $ length r 
 
  -  neem het eerste element van de stack，als het aanwezig is 
  - （提示：hoogle naar`guard`）
 pop：MaybeT（状态堆栈）Int 
 pop = guard（True）（do（r：rs）<  -  get 
 put rs 
返回r）
  

解决方案

首先，您应该了解如果你的堆栈是空的，你的模式 r：rs< - get 失败。但是你把它写在do-block中，所以失败函数会被调用。它用于实现 Monad m => MaybeT m 就像这样： fail _ = MaybeT（返回Nothing）。这意味着如果模式失败，它会返回 Nothing 。所以，你可以这样做：

  pop :: MaybeT（State Stack）Int 
 pop = do r：rs<  -  get 
 put rs 
 return r 
  

I'm trying to implement a Maybe-State monad transformer and use it to implement a simple stack machine. The definitions of state monad and maybe should be correct. Now I'm trying to implement pop:

pop :: MaybeT (State Stack) Int

So that if the stack is empty it returns nothing, otherwise it returns Just <popped stack>. This is what I have so far:

pop :: MaybeT (State Stack) Int
pop = guard True (do (r:rs) <- get
                     put rs
                     return r)

(Obviously True is just a dummy placeholder - I'll implement the condition later, for now I want to get the other part right).

What is wrong with my code? From my understanding guard takes a conditional (True) and a function f. If the conditional is true it then gives pure f.

In my case,

pure = MaybeT . return . Just

So shouldn't my function f just return a State Stack Int?

---

Here is the full code, with my implementations of MaybeT and State:

import Control.Applicative (Alternative(..))
import Control.Monad (liftM, ap, guard)
import Control.Monad.Trans.Class (MonadTrans(lift))

main :: IO()
main = return ()


-- State Monad
--------------

newtype State s a = MakeState { runState :: s -> (a, s) }

instance Functor (State s) where
    fmap  = liftM


instance Applicative (State s) where
    pure a = MakeState $ \s -> (a, s)
    (<*>)  = ap

instance Monad (State s) where
    return a = MakeState $ \s -> (a, s)
    m >>= k  = MakeState $ \s -> let (x, s') = runState m s
                              in runState (k x) s'

get :: State s s
get = MakeState $ \s -> (s, s)

put :: s -> State s ()
put s = MakeState $ \_ -> ((), s)

modify :: (s -> s) -> State s ()
modify f = MakeState $ \s -> ((), f s)

-- MaybeT MonadTransformer
---------------------------

newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) }

instance Monad m => Functor (MaybeT m) where
    fmap a x = MaybeT $ do e <- runMaybeT x
                           return $ fmap a e



instance Monad m => Applicative (MaybeT m) where
    pure      = MaybeT . return . Just
    (<*>) a b = MaybeT $ do e <- runMaybeT a
                            f <- runMaybeT b
                            return $ e <*> f

instance Monad m => Monad (MaybeT m) where
    return  = pure
    a >>= b = MaybeT $ do aa <- runMaybeT a
                          maybe (return Nothing) (runMaybeT . b) aa


instance Monad m => Alternative (MaybeT m) where
  empty   = MaybeT $ return Nothing
  a <|> b = MaybeT $ do aa <- runMaybeT a
                        bb <- runMaybeT b
                        return $ aa <|> bb


instance MonadTrans MaybeT where
    -- "herwrappen" van het argument
    lift x = MaybeT $ do r <- x
                         return $ Just r


-- Stack Manipulation
---------------------

type Stack = [Int]

-- plaats het argument bovenop de stack
push :: Int -> State Stack ()
push x = do r <- get
            put (x:r)
-- geef de grootte van de stack terug
size :: State Stack Int
size = do r <- get
          return $ length r

-- neem het eerste element van de stack, als het aanwezig is
-- (hint: hoogle naar `guard`)
pop :: MaybeT (State Stack) Int
pop = guard (True) (do (r:rs) <- get
                       put rs
                       return r)

解决方案

First of all, you should understand if your stack is empty, your pattern r:rs <- get fails. But you write it in do-block, so the fail function will be called. It is implemented for Monad m => MaybeT m like this: fail _ = MaybeT (return Nothing). This means that if the pattern fails it returns Nothing. That what you want.

So, you can do like this:

pop :: MaybeT (State Stack) Int
pop = do r:rs <- get
         put rs
         return r

这篇关于Monad变换器：使用MaybeT（状态堆栈）实现堆栈机器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！