Каковы преимущества аппликативного разбора над монадическим разбором?

похоже, существует консенсус, что вы должны использовать Parsec в качестве аппликатора, а не монады. Каковы преимущества аппликативного разбора над монадическим разбором?

  • стиль
  • производительность
  • абстрагирование

монадический разбор?

5 57
haskell monads parsec applicative

5 ответов:

основное различие между монадическим и прикладным разбором заключается в том, как обрабатывается последовательная композиция. В случае аппликативного парсера мы используем (<*>), тогда как с монадой мы используем (>>=).

(<*>) :: Parser (a -> b) -> Parser a -> Parser b
(>>=) :: Parser a -> (a -> Parser b) -> Parser b

монадический подход является более гибким, поскольку он позволяет грамматике второй части зависеть от результата от первого, но нам редко нужна эта дополнительная гибкость на практике.

можно подумать, что имея некоторую дополнительную гибкость не может навредить, но на самом деле может. Это мешает нам делать полезный статический анализ на парсере без его запуска. Например, предположим, что мы хотим знать, может ли парсер соответствовать пустой строке или нет, и какие возможные первые символы могут быть в совпадении. Мы хотим функции

empty :: Parser a -> Bool
first :: Parser a -> Set Char

С помощью аппликативного парсера мы можем легко ответить на этот вопрос. (Я тут немного жульничаю. Представьте, что у нас есть конструкторы данных, соответствующие (<*>) и (>>=) в нашем кандидате парсер "языки").

empty (f <*> x) = empty f && empty x
first (f <*> x) | empty f   = first f `union` first x
                | otherwise = first f

однако, с монадическим синтаксическим анализатором мы не знаем, что такое грамматика второй части, не зная ввода.

empty (x >>= f) = empty x && empty (f ???)
first (x >>= f) | empty x   = first x `union` first (f ???)
                | otherwise = first x

разрешение больше, мы можем рассуждать меньше. Это похоже на выбор между динамическими и статическими системами типа.

но какой в этом смысл? Для чего мы можем использовать эти дополнительные статические знания? Ну, мы можем, например, использовать его, чтобы избежать отката в ll(1) разбора путем сравнения следующий символ first набор каждой альтернативы. Мы также можем статически определить, будет ли это неоднозначно, проверив, если first наборы из двух вариантов перекрытия.

другой пример заключается в том, что он может быть использован для восстановления ошибок, как показано в статье Детерминированные, Исправляющие Ошибки Комбинаторные Парсеры С. Doaitse Swierstra и Люк Дюпоншель.

обычно, однако, выбор между аппликативным и монадическим разбором уже есть сделано авторами библиотеки синтаксического анализа, которую вы используете. Когда библиотека, такая как Parsec, предоставляет оба интерфейса, выбор того, какой из них использовать, является чисто стилистическим. В некоторых случаях прикладной код легче читать, чем монадический код, а иногда и наоборот.

83

если парсер является чисто прикладным, можно проанализировать его структуру и" оптимизировать " его перед запуском. Если парсер является монадическим, это в основном полная программа Тьюринга, и выполнение почти любого интересного анализа эквивалентно решению проблемы остановки (т. е. невозможно).

О, И да, есть стилистическая разница тоже...

12

основная причина, по которой я могу предпочесть аппликативные Парсеры над монадическими парсерами, такая же, как и основная причина предпочтения аппликативного кода над монадическим кодом в любом контексте: будучи менее мощными, аппликаторы проще в использовании.

это пример более общего инженерного изречения:использовать простой инструмент, который получает работу. не используйте вилочный погрузчик, когда тележка будет делать. Не используйте столовую пилу, чтобы вырезать купоны. Не пишите код в IO когда он может быть чистым. Пусть все будет просто.

но иногда, вы нужно дополнительная мощность Monad. Верный признак этого - когда вам нужно изменить ход вычислений на основе того, что было вычислено до сих пор. В терминах синтаксического анализа это означает определение того, как анализировать то, что происходит дальше, на основе того, что было проанализировано до сих пор; другими словами, вы можете построить контекстно-зависимые грамматики таким образом.

10

с парсеком преимущество использования Аппликативного-это просто стиль. Монада имеет то преимущество, что она более мощная - вы можете реализовать контекстно-зависимые Парсеры.

разбор UU Doaitse Swierstra является более эффективным, если используется только в прикладном плане.

4

монады строго a более функциональная абстракция чем прозрачна. Вы могли бы написать

instance (Monad m) => Applicative m where
  pure  = return
  (<*>) = ap

но нет никакого способа, чтобы написать

instance (Applicative a) => Monad a where
  return = pure
  (>>=) = ???

так что да, это по сути дело стиль. Я думаю, если вы используете return и ap, то должно быть нет потерь С помощью pure и <*>. поскольку Applicative-это строго меньший интерфейс, чем Monad, это означает, что <*> иногда может быть более оптимизирован, чем ap. (Но с умными правилами переписывания GHC часто можно достичь одной и той же оптимизации независимо.)

монадический разбор?

поскольку монады являются подмножеством прозрачна, я бы заключить, что прикладной анализ является подмножеством монадических разбора.

2