В вашем случае основной монадой является 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) возвращают свои результаты, заключенные в эту монаду.
Между этой монадой и монадическим парсингом в Хаскеле нет никакой связи. В этом случае Хаттон и Мейер ссылаются на экземпляр монады для самого ParsecT. Тот факт, что в Parsec-3.0.0 и более поздних версиях ParsecT стал преобразователем монад с лежащей в основе монадой, не имеет отношения к статье.
Однако я думаю, что вы ищете, куда попал список возможных результатов. В Hutton и Meijer парсер возвращает список всех возможных результатов, в то время как Parsec упрямо возвращает только один. Я думаю, что вы смотрите на m в результате и думаете про себя, что список результатов где-то там скрывается. Это не так.
Парсек из соображений эффективности сделал выбор в пользу первого совпадения в списке результатов Хаттона и Мейера. Это позволяет отбросить как неиспользованные результаты в хвосте списка Хаттона и Мейера, так и в начале потока токенов, потому что мы никогда не возвращаемся назад. В парсеке, учитывая объединенный парсер a <|> b, если a потребляет какой-либо ввод, b никогда не будет оцениваться. Обходной путь - это try, который вернет состояние обратно в прежнее состояние, если a потерпит неудачу, тогда оцените b.
Вы спросили в комментариях, было ли это сделано с помощью Maybe или Either. Ответ «почти, но не совсем». Если вы посмотрите на функции нижнего рычага run*, то увидите, что они возвращают алгебраический тип, который сообщает, что входные данные о погоде были израсходованы, затем секунду, которая дает либо результат, либо сообщение об ошибке. Эти типы работают вроде Either, но даже они не используются напрямую. Вместо того, чтобы продолжить это, я отсылаю вас к посту Антуана Латера, который объясняет, как это работает и почему это делается таким образом.