Monad變換器：用MaybeT（狀態堆棧）實現堆棧機

Question

我試圖實現一個Maybe-State monad變換器並使用它來實現一個簡單的堆棧機器。 狀態monad的定義也許應該是正確的。現在我想實現流行：

pop :: MaybeT (State Stack) Int 

因此，如果堆棧是空的它沒有返回，否則返回Just <popped stack>。 這是我到目前爲止有：

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

（顯然True只是一個虛擬佔位符 - 我以後會實現的條件，現在我想找到另一部分右）。

我的代碼有什麼問題？從我的理解guard需要一個條件（True）和函數f。如果條件爲真，則給出pure f。

在我的情況下，

pure = MaybeT . return . Just 

所以應該不是我的函數f只返回一個State Stack Int？

---

下面是完整的代碼，用我的MaybeT和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) 

Answer 1

首先，你應該，如果您的堆棧是空的理解，你的模式失敗。但是你把它寫在do-block中，所以fail函數將被調用。它是這樣實現的：Monad m => MaybeT m像這樣：fail _ = MaybeT (return Nothing)。這意味着如果模式失敗，則返回Nothing。那就是你想要的。

所以，你可以這樣做：

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

Answer 2

guard並不需要兩個參數，只需要Bool說法。

您還需要解除您的狀態操作到MaybeT：

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

Answer 3

爲了比較的緣故，這裏是一個較粗略的實現不依賴既不guard也沒有對fail：

pop :: MaybeT (State Stack) Int 
pop = do 
    stk <- lift get 
    case stk of 
    [] -> empty 
    (r:rs) -> do 
     lift (put rs) 
     return r 

生產empty當堆棧爲[]相當於使用guard時您想要的方式或使用fail利用失敗的模式匹配（如自由式的答案）。