Le normali funzioni monadiche funzionano con l'equivalente del trasformatore monade

Question

Sto provando a risolvere il problema delle parentesi equilibrate. Non voglio fare l'I/O continuo, e preferisco fare una sola chiamata per ottenereLine e analizzare la stringa risultante. Pertanto la funzione che risolve il problema si occuperà di due stati diversi: la parte non consumata della stringa di input e la pila di parentesi.

voglio impostare alcune funzioni per la manipolazione di una pila:

type Stack = String 

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

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

Questo è tutto bene se sto operando in monade stato, tuttavia sto operando in monade StateT

balanced :: StateT Stack (State String) Bool 

So che mi è stato detto di non avere monadi duplicati nello stack. Lo sto facendo in questo modo perché mi piace come semplifica le definizioni push e pop.

due problemi:

1. Non importa quello che faccio, non riesco a trovare un modo per applicare push e pop al Stack contenuta nel StateT.
2. non ho idea di come chiamare questo dalla funzione principale

Ecco il resto del codice

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

Il tuo problema è che il vostro push e pop sono solo ordinaria, la funzione non monadica che stai tentando di usare nel blocco do monade. Si sta utilizzando next correttamente, poiché si chiama utilizzando la funzione state, ma come probabilmente notato, state funziona solo per la monade semplice State e non StateT.

possiamo implementare una versione trasformatore monade state simili:

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

E poi utilizzarlo nella funzione balanced con push e 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 funzione viene richiamata in questo modo:

evalState (evalStateT balanced []) s 

Dove s è la stringa iniziale e [] è lo stack iniziale.