Đằng Parsec Monad

Question

Nhiều combinators Parsec tôi sử dụng là của một loại như:

foo :: CharParser st Foo 

CharParser được định nghĩa here như:

type CharParser st = GenParser Char st 

CharParser là như vậy, một từ đồng nghĩa loại liên quan đến GenParser, bản thân được xác định here là:

type GenParser tok st = Parsec [tok] st 

GenParser là sau đó một loại từ đồng nghĩa, phân công sử dụng Parsec, được xác định here như:

type Parsec s u = ParsecT s u Identity 

Vì vậy Parsec là một ứng dụng một phần của , tự liệt kê here với loại:

data ParsecT s u m a 

cùng với dòng chữ :

"ParsecT suma là trình phân tích cú pháp với st ream type s, kiểu trạng thái người dùng u, monad m cơ bản và kiểu trả về a. "

Đơn nguyên cơ bản là gì? Đặc biệt, khi tôi sử dụng các trình phân tích cú pháp CharParser là gì? Tôi không thể nhìn thấy nơi nó được chèn vào trong ngăn xếp. Có mối quan hệ nào với việc sử dụng danh sách đơn lẻ trong Monadic Parsing in Haskell để trả lại nhiều phân tích cú pháp thành công từ một trình phân tích cú pháp không rõ ràng không?

Answer 1

GenParser được định nghĩa dưới dạng Parsec, chứ không phải ParsecT. Parsec lần lượt được định nghĩa là

type Parsec s u = ParsecT s u Identity 

Vì vậy, câu trả lời là khi sử dụng CharParser, đơn nguyên cơ bản là mẫu đơn sắc.

Answer 2

Trong trường hợp của bạn, đơn nguyên cơ bản là Identity. Tuy nhiên ParsecT khác với hầu hết các biến thế đơn nguyên ở chỗ nó là một thể hiện của lớp Monad ngay cả khi tham số kiểu m thì không. Nếu bạn nhìn vào mã nguồn, bạn sẽ thấy thiếu "(Monad m) =>" trong khai báo cá thể.

Vì vậy, sau đó bạn tự hỏi, "Nếu tôi có một ngăn xếp đơn nguyên không tầm thường, nó sẽ được sử dụng ở đâu?"

Có một ba câu trả lời cho câu hỏi đó:

1. Nó được sử dụng để uncons token tiếp theo ra khỏi dòng:

   class (Monad m) => Stream s m t | s -> t where 
       uncons :: s -> m (Maybe (t,s)) 
   

   ý rằng uncons mất một s (dòng of tokens t) và trả về kết quả của nó được bọc trong đơn nguyên của bạn. Điều này cho phép một người làm điều thú vị trong khi hoặc ngay cả trong quá trình nhận mã thông báo tiếp theo.

2. Nó được sử dụng trong kết quả đầu ra của mỗi trình phân tích cú pháp.Điều này có nghĩa là bạn có thể tạo các trình phân tích cú pháp không chạm vào đầu vào nhưng thực hiện hành động trong đơn nguyên cơ bản và sử dụng các bộ kết hợp để liên kết chúng với các trình phân tích cú pháp thông thường. Nói cách khác, lift (x :: m a) :: ParsecT s u m a.

3. Cuối cùng, kết quả cuối cùng của RunParsecT và bạn bè (cho đến khi bạn xây dựng đến điểm mà m được thay thế bằng Identity) trả về kết quả của chúng được bọc trong đơn nguyên này.

Không có mối quan hệ nào giữa đơn nguyên này và đơn lẻ từ Monadic Parsing in Haskell. Trong trường hợp này Hutton và Meijer đang đề cập đến cá thể đơn lẻ cho chính ParsecT. Thực tế là trong Parsec-3.0.0 và hơn thế nữa ParsecT đã trở thành một biến thể đơn lẻ với một đơn nguyên cơ bản không liên quan đến bài báo.

Điều tôi nghĩ bạn đang tìm kiếm tuy nhiên là nơi danh sách các kết quả có thể có. Trong Hutton và Meijer, trình phân tích cú pháp trả về một danh sách tất cả các kết quả có thể trong khi Parsec cứng đầu chỉ trả về một kết quả. Tôi nghĩ rằng bạn đang nhìn vào số m trong kết quả và suy nghĩ cho chính mình rằng danh sách các kết quả phải được ẩn trong đó một nơi nào đó. Không phải vậy.

Parsec, vì lý do hiệu quả, đã lựa chọn thích kết quả phù hợp đầu tiên trong danh sách kết quả của Hutton và Meijer. Điều này chúng ta hãy quăng đi cả hai kết quả không sử dụng trong đuôi của Hutton và Meijer của danh sách và cũng là mặt trước của dòng thẻ bởi vì chúng tôi không bao giờ quay trở lại. Trong phân tích cú pháp, với trình phân tích cú pháp kết hợp a <|> b, nếu a tiêu thụ bất kỳ đầu vào b nào sẽ không bao giờ được đánh giá. Cách này là try sẽ đặt lại trạng thái về vị trí nếu a lỗi sau đó đánh giá b.

Bạn đã hỏi trong phần nhận xét nếu điều này được thực hiện bằng cách sử dụng Maybe hoặc Either. Câu trả lời là "gần như nhưng không hoàn toàn." Nếu bạn nhìn vào đòn bẩy thấp, các hàm run* bạn thấy rằng chúng trả về một kiểu đại số cho biết đầu vào thời tiết được tiêu thụ sau đó một giây cung cấp kết quả hoặc một thông báo lỗi. Những loại này hoạt động giống như Either, nhưng thậm chí chúng không được sử dụng trực tiếp. Thay vì sau đó kéo dài này ra xa hơn, tôi sẽ giới thiệu bạn đến the post bởi Antoine Latter giải thích cách thức hoạt động này và tại sao nó được thực hiện theo cách này.