Cách sử dụng Control.Monad.State với Parsec?

Question

Tôi rất ngạc nhiên vì tôi không thể tìm thấy bất kỳ thông tin nào về vấn đề này. Tôi phải là người duy nhất gặp rắc rối với nó.

Vì vậy, giả sử tôi có bộ đếm dấu gạch ngang. Tôi muốn nó đếm số lượng dấu gạch ngang trong chuỗi và trả về chuỗi. Giả sử tôi đưa ra một ví dụ không hoạt động khi sử dụng xử lý trạng thái của parsec. Vì vậy, điều này sẽ hoạt động:

dashCounter = do 
    str <- many1 dash 
    count <- get 
    return (count,str) 


dash = do 
    char '-' 
    modify (+1) 

Và thực sự, điều này biên dịch. OK, vì vậy tôi cố gắng sử dụng nó:

:t parse dashCounter "" "----" 
parse dashCounter "" "----" 
    :: (Control.Monad.State.Class.MonadState 
     t Data.Functor.Identity.Identity, 
     Num t) => 
    Either ParseError (t, [Char]) 

Được rồi, điều đó có ý nghĩa. Nó sẽ trả về trạng thái và chuỗi. Mát mẻ.

>parse dashCounter "" "----" 

<interactive>:1:7: 
    No instance for (Control.Monad.State.Class.MonadState 
         t0 Data.Functor.Identity.Identity) 
     arising from a use of `dashCounter' 
    Possible fix: 
     add an instance declaration for 
     (Control.Monad.State.Class.MonadState 
     t0 Data.Functor.Identity.Identity) 
    In the first argument of `parse', namely `dashCounter' 
    In the expression: parse dashCounter "" "----" 
    In an equation for `it': it = parse dashCounter "" "----" 

Rất tiếc. Nhưng sau đó làm thế nào nó có thể đã bao giờ hy vọng để làm việc ở nơi đầu tiên? Không có cách nào để nhập trạng thái ban đầu.

Ngoài ra còn có một chức năng:

>runPT dashCounter (0::Int) "" "----" 

Nhưng nó mang lại một lỗi tương tự.

<interactive>:1:7: 
    No instance for (Control.Monad.State.Class.MonadState Int m0) 
     arising from a use of `dashCounter' 
    Possible fix: 
     add an instance declaration for 
     (Control.Monad.State.Class.MonadState Int m0) 
    In the first argument of `runPT', namely `dashCounter' 
    In the expression: runPT dashCounter (0 :: Int) "" "----" 
    In an equation for `it': 
     it = runPT dashCounter (0 :: Int) "" "----" 

Tôi cảm thấy mình cần phải chạyState trên đó hoặc có chức năng đã thực hiện nội bộ, nhưng tôi không thể tìm ra nơi để đi từ đây.

Chỉnh sửa: Tôi phải xác định rõ ràng hơn, tôi không muốn sử dụng xử lý trạng thái của parsec. Lý do là tôi có một cảm giác tôi không muốn backtracking của nó để ảnh hưởng đến những gì nó thu thập với các vấn đề tôi đang chuẩn bị để giải quyết nó với.

Tuy nhiên, ông McCann đã tìm ra cách này phải phù hợp với nhau và mã cuối cùng sẽ trông như thế này:

dashCounter = do 
    str <- many1 dash 
    count <- get 
    return (count,str) 

dash = do 
    c <- char '-' 
    modify (+1) 
    return c 

test = runState (runPT dashCounter() "" "----------") 0 

Thanks a lot.

Answer 1

Bạn thực sự gặp phải nhiều sự cố đang diễn ra tại đây, tất cả những điều này tương đối không rõ ràng trong lần đầu tiên.

Bắt đầu với đơn giản nhất: dash đang quay lại (), dường như không phải là những gì bạn muốn khi bạn đang thu thập kết quả. Bạn có thể muốn một cái gì đó như dash = char '-' <* modify (+1). (Lưu ý rằng tôi đang sử dụng toán tử từ Control.Applicative tại đây, vì nó trông gọn hơn)

Tiếp theo, xóa một điểm nhầm lẫn: Khi bạn nhận được chữ ký kiểu hợp lý trong GHCi, hãy chú ý ngữ cảnh (Control.Monad.State.Class.MonadState t Data.Functor.Identity.Identity, Num t).Điều đó không nói điều gì là là, điều đó nói rằng bạn muốn họ cần. Không có gì đảm bảo rằng các trường hợp nó yêu cầu tồn tại và, trên thực tế, họ không. Identity không phải là một đơn vị nhà nước!

Mặt khác, bạn hoàn toàn đúng khi nghĩ rằng parse không có ý nghĩa; bạn không thể sử dụng nó ở đây. Xem xét loại của nó: Stream s Identity t => Parsec s() a -> SourceName -> s -> Either ParseError a. Theo phong tục với máy biến áp đơn nguyên, Parsec là một từ đồng nghĩa với được áp dụng cho đơn sắc danh tính. Và trong khi không cung cấp trạng thái người dùng, bạn dường như không muốn sử dụng nó và không không cho ví dụ MonadState dù sao đi nữa. Đây là trường hợp duy nhất có liên quan: MonadState s m => MonadState s (ParsecT s' u m). Nói cách khác, để coi một trình phân tích cú pháp là một đơn vị trạng thái, bạn phải áp dụng cho một số đơn vị trạng thái khác.

Loại này mang đến cho chúng tôi vấn đề tiếp theo: Sự mơ hồ. Bạn đang sử dụng rất nhiều loại phương pháp lớp và không có chữ ký loại, vì vậy bạn có khả năng chạy vào các tình huống mà GHC không thể biết loại bạn thực sự muốn, vì vậy bạn phải nói với nó.

Bây giờ, như một giải pháp nhanh chóng, trước tiên hãy xác định một loại từ đồng nghĩa để đặt tên cho các biến đống đơn nguyên chúng ta muốn:

type StateParse a = ParsecT String() (StateT Int Identity) a 

Cho dashCounter loại chữ ký liên quan:

dashCounter :: StateParse (Int, String) 
dashCounter = do str <- many1 dash 
       count <- get 
       return (count,str) 

Và thêm chức năng "chạy" chuyên dụng:

runStateParse p sn inp count = runIdentity $ runStateT (runPT p() sn inp) count 

Bây giờ, trong GHCi:

Main> runStateParse dashCounter "" "---" 0 
(Right (3,"---"),3) 

Ngoài ra, lưu ý rằng việc sử dụng newtype quanh ngăn thay thế chỉ là một từ đồng nghĩa loại. Điều này có thể giúp giải quyết các vấn đề mơ hồ trong một số trường hợp và rõ ràng tránh được việc kết thúc bằng chữ ký kiểu khổng lồ.

Answer 2

Nếu bạn muốn sử dụng thành phần trạng thái người dùng Parsec cung cấp dưới dạng tính năng tích hợp, khi đó bạn có thể sử dụng các chức năng đơn lẻ getState và modifyState.

Tôi đã cố gắng giữ đúng chương trình mẫu của mình, mặc dù sử dụng sự trở lại của dash dường như không hữu ích.

import Text.Parsec 

dashCounter :: Parsec String Int (Int, [()]) 
dashCounter = do 
    str <- many1 dash 
    count <- getState 
    return (count,str) 

dash :: Parsec String Int() 
dash = do 
    char '-' 
    modifyState (+1) 

test = runP dashCounter 0 "" "---" 

Lưu ý rằng runP thực sự giải quyết mối quan tâm của bạn về runState.

Answer 3

Trong khi những câu trả lời này phân loại vấn đề cụ thể này, họ bỏ qua vấn đề cơ bản nghiêm trọng hơn với cách tiếp cận như thế này. Tôi muốn mô tả nó ở đây cho bất cứ ai khác nhìn vào câu trả lời này.

Có sự khác biệt giữa trạng thái người dùng và sử dụng biến áp StateT. Trạng thái người dùng nội bộ được đặt lại trên backtracking nhưng StateT thì không. Hãy xem xét mã sau đây. Chúng tôi muốn thêm một vào quầy của chúng tôi nếu có dấu gạch ngang và hai nếu có dấu cộng. Chúng tạo ra các kết quả khác nhau.

Có thể thấy cả việc sử dụng trạng thái bên trong và gắn bộ biến áp StateT cung cấp kết quả chính xác. Sau này đến lúc các chi phí của việc phải nâng lên một cách rõ ràng hoạt động và cẩn thận hơn nhiều với các loại.

import Text.Parsec hiding (State) 
import Control.Monad.State 
import Control.Monad.Identity 

f :: ParsecT String Int Identity Int 
f = do 
    try dash <|> plus 
    getState 

dash = do 
    modifyState (+1) 
    char '-' 
plus = do 
    modifyState (+2) 
    char '+' 

f' :: ParsecT String() (State Int)() 
f' = void (try dash' <|> plus') 

dash' = do 
    modify (+1) 
    char '-' 

plus' = do 
    modify (+2) 
    char '+' 

f'' :: StateT Int (Parsec String())() 
f'' = void (dash'' <|> plus'') 

dash'' :: StateT Int (Parsec String()) Char 
dash'' = do 
    modify (+1) 
    lift $ char '-' 

plus'' :: StateT Int (Parsec String()) Char 
plus'' = do 
    modify (+2) 
    lift $ char '+' 

Đây là kết quả của việc chạy f, f 'và f' '.

*Main> runParser f 0 "" "+" 
Right 2 
*Main> flip runState 0 $ runPT f'() "" "+" 
(Right(),3) 
*Main> runParser (runStateT f'' 0)() "" "+" 
Right ((),2)