Làm các chức năng đơn thuần bình thường hoạt động với máy biến áp đơn nguyên tương đương

Question

Tôi đang cố gắng giải quyết vấn đề về khung cân bằng. Tôi không muốn làm IO liên tục, và thay vì sẽ thực hiện một cuộc gọi duy nhất để getLine và phân tích chuỗi kết quả. Do đó, hàm giải quyết vấn đề sẽ xử lý hai trạng thái khác nhau: Phần không được thêm vào của chuỗi đầu vào và ngăn xếp khung.

tôi muốn thiết lập một số chức năng cho thao tác một chồng:

type Stack = String 

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

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

Đó là tất cả tốt nếu tôi hoạt động trong các đơn nguyên nhà nước, tuy nhiên tôi đang hoạt động trong các đơn nguyên StateT

balanced :: StateT Stack (State String) Bool 

Tôi biết tôi đã được yêu cầu không có các bản sao đơn lẻ trong ngăn xếp. Tôi đang làm theo cách này bởi vì tôi thích cách đơn giản hóa các định nghĩa push và pop.

Hai vấn đề:

1. Không có vấn đề gì tôi làm tôi không thể tìm thấy một cách để áp dụng push và pop đến stack chứa trong StateT.
2. Tôi không có ý tưởng làm thế nào để gọi đây là từ chức năng chính

Dưới đây là phần còn lại của mã

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

Vấn đề của bạn là push của bạn và pop chỉ là bình thường, chức năng không monadic mà bạn đang cố gắng sử dụng trong khối đơn giản. Bạn đang sử dụng next chính xác, vì bạn gọi nó bằng cách sử dụng chức năng state, nhưng như bạn có thể nhận thấy, state chỉ hoạt động cho đồng bằng State đơn nguyên chứ không phải StateT.

Chúng tôi có thể thực hiện một phiên bản biến đơn nguyên của state như thế này:

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

Và sau đó sử dụng nó trong balanced chức năng với push và 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 

Các hàm được gọi như thế này:

evalState (evalStateT balanced []) s 

đâu s là chuỗi ban đầu và [] là ngăn xếp ban đầu.