Haciendo que las funciones monádicas normales funcionen con el transformador de mónada equivalente

Question

Estoy tratando de resolver el problema de los soportes equilibrados. No quiero hacer IO continuo, y preferiría hacer una sola llamada a getLine y analizar la cadena resultante. Por lo tanto, la función que resuelve el problema tratará dos estados diferentes: la parte no consumida de la cadena de entrada y la pila de paréntesis.

quiero establecer algunas funciones para manipular una pila:

type Stack = String 

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

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

Eso es todo bueno si estoy operando en la mónada estado, sin embargo estoy operando en la mónada Statet

balanced :: StateT Stack (State String) Bool 

Sé que me han dicho que no tenga mónadas duplicadas en la pila. Lo hago de esta manera porque me gusta cómo simplifica las definiciones push y pop.

dos problemas:

1. No importa lo que hago no puedo encontrar una manera de aplicar presión y el pop a la Pila contenida en el Statet.
2. no tengo idea de cómo llamar a esto desde la función principal

Aquí está el resto del código

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

Su problema es que su push y pop son simplemente normal, la función no monádico que intentas usar en el bloque do monádico. Está utilizando next correctamente, ya que lo llama utilizando la función state, pero como probablemente habrá notado, state solo funciona para la mónada simple State y no para StateT.

podemos implementar una versión transformador mónada de state así:

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

Y luego utilizarlo en la función balanced con push y 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 

La función se llama así:

evalState (evalStateT balanced []) s 

Dónde s es la cadena inicial y [] es la pila inicial.