使正常的monadic函数与monad变换器等效

Question

我正试图解决平衡括号问题.我不想做连续的IO,宁愿只调用getLine并解析生成的字符串.因此,解决问题的函数将处理两种不同的状态:输入字符串的未消耗部分和括号堆栈.

我想设置一些操作堆栈的函数:

type Stack = String

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

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

如果我在州monad运营,那就好了,不过我在StateT monad运营

balanced :: StateT Stack (State String) Bool

我知道我被告知不要在堆栈中有重复的monad.我这样做是因为我喜欢它如何简化推送和流行定义.

两个问题:

1. 无论我做什么,我都找不到将push和pop应用到StateT中包含的Stack的方法.
2. 我不知道如何从main函数调用它

这是代码的其余部分

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是其试图在一元做块只使用普通的非一元函数.您使用next正确,因为您使用该state函数调用它,但正如您可能注意到的那样,state只适用于普通Statemonad而不是StateT.

我们可以实现这样的monad变换器版本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初始字符串在哪里,[]是初始堆栈.