Copyright	© 2017 Mark Karpov
License	BSD 3 clause
Maintainer	Mark Karpov <[email protected]>
Stability	experimental
Portability	portable
Safe Haskell	Safe
Language	Haskell2010

Control.Applicative.Combinators

Contents

Re-exports from Control.Applicative
Original combinators

Description

The module provides parser combinators defined for instances of Applicative and Alternative. It also re-exports functions that are commonly used in parsing from Control.Applicative with additional parsing-related comments added.

Due to the nature of the Applicative and Alternative abstractions, they are prone to memory leaks and not as efficient as their monadic counterparts. Although all the combinators we provide in this module are perfectly expressible in terms of Applicative and Alternative, please prefer Control.Monad.Combinators instead when possible.

If you wish that the combinators that cannot return empty lists return values of the NonEmpty data type, use the Control.Applicative.Combinators.NonEmpty module.

A note on backtracking

Certain parsing libraries, such as Megaparsec, do not backtrack every branch of parsing automatically for the sake of performance and better error messages. They typically backtrack only “atomic” parsers, e.g. those that match a token or several tokens in a row. To backtrack an arbitrary complex parser/branch, a special combinator should be used, typically called try. Combinators in this module are defined in terms Applicative and Alternative operations. Being quite abstract, they cannot know anything about inner workings of any concrete parsing library, and so they cannot use try.

The essential feature of the Alternative type class is the (<|>) operator that allows to express choice. In libraries that do not backtrack everything automatically, the choice operator and everything that is build on top of it require the parser on the left hand side to backtrack in order for the alternative branch of parsing to be tried. Thus it is the responsibility of the programmer to wrap more complex, composite parsers in try to achieve correct behavior.

Synopsis

Re-exports from Control.Applicative

(<|>) :: Alternative f => forall a. f a -> f a -> f a infixl 3 #

An associative binary operation

This combinator implements choice. The parser p <|> q first applies p. If it succeeds, the value of p is returned. If p fails, parser q is tried.

many :: Alternative f => forall a. f a -> f [a] #

Zero or more.

many p applies the parser p zero or more times and returns a list of the values returned by p.

identifier = (:) <$> letter <*> many (alphaNumChar <|> char '_')

some :: Alternative f => forall a. f a -> f [a] #

One or more.

some p applies the parser p one or more times and returns a list of the values returned by p.

word = some letter

optional :: Alternative f => f a -> f (Maybe a) #

One or none.

optional p tries to apply the parser p. It will parse p or Nothing. It only fails if p fails after consuming input. On success result of p is returned inside of Just, on failure Nothing is returned.

Original combinators

between :: Applicative m => m open -> m close -> m a -> m a Source #

between open close p parses open, followed by p and close. Returns the value returned by p.

braces = between (symbol "{") (symbol "}")

choice :: (Foldable f, Alternative m) => f (m a) -> m a Source #

choice ps tries to apply the parsers in the list ps in order, until one of them succeeds. Returns the value of the succeeding parser.

choice = asum

count :: Applicative m => Int -> m a -> m [a] Source #

count n p parses n occurrences of p. If n is smaller or equal to zero, the parser equals to pure []. Returns a list of n parsed values.

count = replicateM