В основе Parsec Monad - программирование

Многие из множителей Parsec, которые я использую, имеют тип, например:

foo :: CharParser st Foo

CharParser определяется здесь как:

type CharParser st = GenParser Char st

CharParser является, таким образом, синонимом типа GenParser, который сам определяет здесь как:

type GenParser tok st = Parsec [tok] st

GenParser является другим синонимом типа, назначенным с помощью Parsec, определяемым здесь как:

type Parsec s u = ParsecT s u Identity

So Parsec - это частичное приложение ParsecT, которое перечисляет здесь с типом:

data ParsecT s u m a

вместе со словами:

"ParsecT s u m a - синтаксический анализатор с типом потока s, тип пользовательского типа u, основной монады m и типа возврата a."

Какова основная монада? В частности, что я использую парсеры CharParser? Я не вижу, где он вставлен в стек. Есть ли связь с использованием монады списка в Monadic Parsing в Haskell, чтобы вернуть несколько успешных парсов из двусмысленного парсера?

Ответ 2

В вашем случае основная монада Identity. Однако ParsecT отличается от большинства монадных трансформаторов тем, что он является экземпляром класса Monad, даже если параметр типа m не является. Если вы посмотрите на исходный код, вы заметите отсутствие "(Monad m) =>" в объявлении экземпляра.

Итак, вы спрашиваете себя: "Если бы у меня был нетривиальный стек монады, где он был бы использован?"

Есть три ответа на этот вопрос:

Используется для uncons следующего токена из потока:
```
class (Monad m) => Stream s m t | s -> t where
    uncons :: s -> m (Maybe (t,s))
```
Обратите внимание, что uncons принимает s (поток токенов t) и возвращает результат, завернутый в вашу монаду. Это позволяет делать интересную вещь во время или даже во время процесса получения следующего токена.
Он используется в результирующем результате каждого анализатора. Это означает, что вы можете создавать парсеры, которые не касаются ввода, но предпринимают действия в основной монаде и используют комбинаторы для привязки их к регулярным синтаксическим анализаторам. Другими словами, lift (x :: m a) :: ParsecT s u m a.
Наконец, конечный результат RunParsecT и друзей (до тех пор, пока вы не вернетесь к точке, где m заменяется на Identity), верните их результаты, завернутые в эту монаду.

Между этой монадой и одной из не существует взаимосвязи между Monadic Parsing в Haskell. В этом случае Хаттон и Мейер ссылаются на экземпляр монады для самого ParsecT. Тот факт, что в Parsec-3.0.0 и вне ParsecT стал монадным трансформатором с основной монадой, не имеет отношения к бумаге.

То, что я думаю, что вы ищете, есть список возможных результатов. В Hutton и Meijer парсер возвращает список всех возможных результатов, в то время как Parsec упрямо возвращает только один. Я думаю, что вы смотрите на m в результате и думаете себе, что список результатов должен где-то прятаться. Это не так.

Parsec по соображениям эффективности сделал выбор, чтобы предпочесть первый результат сопоставления в списке результатов Хаттона и Мейера. Это позволяет отбросить как неиспользованные результаты в хвост Хаттона, так и список Мейера, а также фронт потока токенов, потому что мы никогда не возвращаемся назад. В parsec, учитывая объединенный синтаксический анализатор a <|> b, если a потребляет любой вход b, он никогда не будет оценен. Способ вокруг этого try, который будет reset вернуться к тому месту, где он был, если a не работает, тогда оцените b.

Вы спросили в комментариях, было ли это сделано с помощью Maybe или Either. Ответ "почти, но не совсем". Если вы посмотрите на функции с низким рычагом run*, вы увидите, что они возвращают алгебраический тип, который сообщает, что входной сигнал потребляется, а затем секунда, которая дает либо результат, либо сообщение об ошибке. Эти типы работают как Either, но даже они не используются напрямую. Вместо этого растяните это дальше, я отсылаю вас к сообщению от Антуана Лэтера, который объясняет, как это работает и почему это делается именно так.

Ответ 1

Ответ 2