2012-02-08 72 views
5

我試圖解決平衡括號問題。我不想執行連續的IO,而只想調用getLine並分析結果字符串。因此解決問題的函數將處理兩種不同的狀態:輸入字符串的未消耗部分和括號堆棧。使正常的monadic函數與單相變壓器相當

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

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 
+0

嘗試使用'Reader String'而不是'State String'作爲內部monad。 – dflemstr 2012-02-08 06:35:41

回答

7

你的問題是,你的pushpop只是普通的其餘部分,非一元函數你正嘗試在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功能與pushpop使用它。

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是初始字符串,[]是初始堆棧。