使正常的monadic函數與單相變壓器相當

Question

我試圖解決平衡括號問題。我不想執行連續的IO，而只想調用getLine並分析結果字符串。因此解決問題的函數將處理兩種不同的狀態：輸入字符串的未消耗部分和括號堆棧。

我想設置一些功能操作堆棧：

type Stack = String 

pop :: Stack -> (Char,Stack) 
pop (x:xs) = (x,xs) 

push :: Char -> Stack -> ((),Stack) 
push a xs = ((),a:xs) 

，如果我在狀態單子正在運行的都好，但是我在StateT單子正在運行

balanced :: StateT Stack (State String) Bool 

我知道我被告知不要在堆棧中有重複單子。我這樣做是因爲我喜歡它如何簡化push和pop定義。

兩個問題：

1. 不管我做什麼，我不能找到一個辦法適用push和pop包含在StateT的 堆棧。
2. 我不知道如何從主要功能

這裏稱之爲是代碼

next :: String -> (Maybe Char,String) 
next ""  = (Nothing,[]) 
next (x:xs) = (Just x,xs) 

balanced = do 
      c <- lift (state next) 
      case c of 
       Nothing -> return True 
       Just c -> if elem c open 
         then (push c) >> balanced 
         else if elem c close 
           then pop >>= \x -> 
           if eq x c 
           then balanced 
           else return False 
           else balanced 
      where open = "<{([" 
       close = "])}>" 
       eq '(' ')' = True 
       eq '{' '}' = True 
       eq '<' '>' = True 
       eq '[' ']' = True 
       eq _ _ = False 

Answer 1

你的問題是，你的push和pop只是普通的其餘部分，非一元函數你正嘗試在monadic do-block中使用它。您正確使用next，因爲您使用state函數調用該函數，但正如您可能注意到的，state僅適用於簡單State monad，而不適用於StateT。

我們可以實現的state一個單子轉換的版本是這樣的：

stateT :: Monad m => (s -> (a, s)) -> StateT s m a 
stateT f = do 
    (x, s') <- gets f 
    put s' 
    return x 

然後在balanced功能與push和pop使用它。

balanced :: StateT Stack (State String) Bool 
balanced = do 
      c <- lift (state next) 
      case c of 
       Nothing -> return True 
       Just c -> if elem c open 
         then (stateT $ push c) >> balanced 
         else if elem c close 
           then stateT pop >>= \x -> 
           if eq x c 
            then balanced 
            else return False 
           else balanced 
      where open = "<{([" 
       close = "])}>" 
       eq '(' ')' = True 
       eq '{' '}' = True 
       eq '<' '>' = True 
       eq '[' ']' = True 
       eq _ _ = False 

的函數被調用是這樣的：

evalState (evalStateT balanced []) s 

哪裏s是初始字符串，[]是初始堆棧。