Control.Applicative.Permutations

This module is a generalization of the package parsec-permutation authored by Samuel Hoffstaetter:

https://hackage.haskell.org/package/parsec-permutation

This module also takes inspiration from the algorithm is described in: Parsing Permutation Phrases, by Arthur Baars, Andres Loh and Doaitse Swierstra. Published as a functional pearl at the Haskell Workshop 2001.

From these two works we derive a flexible and general method for parsing permutations over an Applicative structure. Quite useful in conjunction with "Free" constructions of Applicatives, Monads, etc.

Other permutation parsing libraries tend towards using special "almost applicative" combinators for construction which denies the library user the ability to lift and unlift permutation parsing into any Applicative computational context. We redefine these combinators as convenience operators here alongside the equivalent Applicative instance.

For example, suppose we want to parse a permutation of: an optional string of a's, the character b and an optional c. Using a standard parsing library combinator char, this can be described using the Applicative instance by:

test = runPermutation $
         (,,) <$> toPermutationWithDefault ""  (some (char 'a'))
              <*> toPermutation (char 'b')
              <*> toPermutationWithDefault '_' (char 'c')

Equivalently, this can also be describe using the convenience operators reminiscent of other parsing libraries:

test = runPermutation $
         (,,) <$?> ("", some (char 'a'))
              <||> char 'b'
              <|?> ('_', char 'c')

Since: 0.2.0

Permutation type

data Permutation m a

An Applicative wrapper-type for constructing permutation parsers.

Instances

Functor m => Functor (Permutation m)

Methods

fmap :: (a -> b) -> Permutation m a -> Permutation m b

(<$) :: a -> Permutation m b -> Permutation m a

Alternative m => Applicative (Permutation m)

Methods

pure :: a -> Permutation m a

(<*>) :: Permutation m (a -> b) -> Permutation m a -> Permutation m b

(*>) :: Permutation m a -> Permutation m b -> Permutation m b

(<*) :: Permutation m a -> Permutation m b -> Permutation m a

Permutation evaluators

runPermutation

Arguments

:: (Alternative m, Monad m)

=> Permutation m a

Permutation specification

-> m a

Resulting base monad capable of handling the permutation

"Unlifts" a permutation parser into a parser to be evaluated.

intercalateEffect

Arguments

:: (Alternative m, Monad m)

=> m b

Effect to be intercalated between permutation components

-> Permutation m a

Permutation specification

-> m a

Resulting base monad capable of handling the permutation

"Unlifts" a permutation parser into a parser to be evaluated with an intercalated effect. Useful for separators between permutation elements.

For example, suppose that similar to above we want to parse a permutation of: an optional string of a's, the character b and an optional c. However, we also want each element of the permutation to be separated by a colon. Using a standard parsing library combinator char, this can be described using the Applicative instance by:

test = intercalateEffect (char ':') $
         (,,) <$?> ("", some (char 'a'))
              <||> char 'b'
              <|?> ('_', char 'c')

This will accept strings such as: "a:b:c", "b:c:a", "b:aa", "b", etc.

Note that the effect is intercalated between permutation components and that:

• There is never an effect parsed preceeding the first component of the permutation
• There is never an effect parsed following the last component of the permutation
• No effects are intercalated between missing components with a default value.

Permutation constructors

toPermutation

Arguments

:: Alternative m

=> m a

Permutation component

-> Permutation m a

"Lifts" a parser to a permutation parser.

toPermutationWithDefault

Arguments

:: Alternative m

=> a

Default Value

-> m a

Permutation component

-> Permutation m a

"Lifts" a parser with a default value to a permutation parser.

If no permutation containing the supplied parser can be parsed from the input, then the supplied default value is returned in lieu of a parse result.

Convenience operators

(<$$>) infixl 2

Arguments

:: Alternative m

=> (a -> b)

Function to use on result of parsing

-> m a

Normal parser

-> Permutation m b

Permutation parser build from it

The expression f <$$> p creates a fresh permutation parser consisting of parser p. The the final result of the permutation parser is the function f applied to the return value of p. The parser p is not allowed to accept empty input—use the optional combinator (<$?>) instead.

If the function f takes more than one parameter, the type variable b is instantiated to a functional type which combines nicely with the adds parser p to the (<||>) combinator. This results in stylized code where a permutation parser starts with a combining function f followed by the parsers. The function f gets its parameters in the order in which the parsers are specified, but actual input can be in any order.

(<$?>) infixl 2

Arguments

:: Alternative m

=> (a -> b)

Function to use on result of parsing

-> (a, m a)

Default value and parser

-> Permutation m b

Permutation parser

The expression f <$?> (x, p) creates a fresh permutation parser consisting of parser p. The final result of the permutation parser is the function f applied to the return value of p. The parser p is optional—if it cannot be applied, the default value x will be used instead.

(<||>) infixl 1

Arguments

:: Alternative m

=> Permutation m (a -> b)

Given permutation parser

-> m a

Parser to add (should not accept empty input)

-> Permutation m b

Resulting parser

The expression perm <||> p adds parser p to the permutation parser perm. The parser p is not allowed to accept empty input—use the optional combinator (<|?>) instead. Returns a new permutation parser that includes p.

(<|?>) infixl 1

Arguments

:: Alternative m

=> Permutation m (a -> b)

Given permutation parser

-> (a, m a)

Default value and parser

-> Permutation m b

Resulting parser

The expression perm <||> (x, p) adds parser p to the permutation parser perm. The parser p is optional—if it cannot be applied, the default value x will be used instead. Returns a new permutation parser that includes the optional parser p.