Normal monadik işlevler oluşturmak, monad trafo eşdeğeri

Question

ile çalışır. Dengelenmiş parantez sorununu çözmeye çalışıyorum. Sürekli IO yapmak istemiyorum, ve sadece bir arama yapmak ve sonuçta ortaya çıkan dizeyi ayrıştırmak istiyorum. Bu nedenle, sorunu çözen işlev, iki farklı durumu ele alır: Girdi dizesinin tükenmeyen kısmı ve parantez yığını.

Bir yığın manipüle bazı fonksiyonlarının ayarlanması için istiyorum: ancak Durumluk monad faaliyet ediyorum

type Stack = String 

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

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

Ben devlet monad faaliyet ediyorsam hepsi iyi

balanced :: StateT Stack (State String) Bool 

Yığında yinelenen monadlara sahip olmamam söylendi. Bu şekilde yapıyorum çünkü itme ve pop tanımlamalarını nasıl basitleştirdiğini seviyorum.

İki sorun:

1. Ne yaparsam ne itmek uygulamak ve Durumluk içerdiği Stack pop için bir yol bulmak mümkün değil.
2. Ben ana işlevi İşte

bu çağırmak için nasıl hiçbir fikrim yok

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

Kişisel Sorun push ve pop sadece sıradan olmasıdır kodun kalan var olmayan monadic fonksiyonu Monadic blokta kullanmaya çalıştığınız. next'u, state işlevini kullanarak çağırdığınızdan, ancak muhtemelen fark ettiğiniz gibi, state yalnızca State tekdüze için değil StateT için çalışır.

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

Sonra push ve pop ile balanced fonksiyonda kullanın:

Böyle state bir monad trafo uygulayabilir.

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 

işlevi aşağıdaki gibi adlandırılır:

evalState (evalStateT balanced []) s 

s ilk dize

ve [] ilk yığın.