Блог

Многие из используемых мной комбинаторов 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
  

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

 data ParsecT s u m a
  

наряду со словами:

«ParsecT s u m a — это анализатор с типом потока s, типом состояния пользователя u, базовой монадой m и типом возвращаемого значения a».

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

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

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

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

1. Используется для uncons извлечения следующего токена из потока:

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

   Обратите внимание, что uncons принимает s (поток токенов t ) и возвращает его результат, завернутый в вашу монаду. Это позволяет делать интересные вещи во время или даже во время процесса получения следующего токена.

2. Он используется в результирующем выводе каждого анализатора. Это означает, что вы можете создавать анализаторы, которые не касаются входных данных, но выполняют действие в базовой монаде и используют комбинаторы для привязки их к обычным анализаторам. Другими словами, lift (x :: m a) :: ParsecT s u m a .

3. Наконец, конечный результат RunParsecT и friends (пока вы не создадите до точки, где m заменяется на Identity ) возвращает их результаты, завернутые в эту монаду.

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

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

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

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

GenParser определяется в терминах Parsec, а не ParsecT. Parsec, в свою очередь, определяется как

 type Parsec s u = ParsecT s u Identity
  

Итак, ответ заключается в том, что при использовании CharParser базовой монадой является монада Identity.