HORIZON HASKELLDocslts/ghc-9.10.xc74966e2026-09-27Search names, modules, packages, or :: a typeCtrl K

GHC 9.10.3 · lts/ghc-9.10.x · c74966e · 2026-09-27

Moduleparser-combinators-1.3.0Haskell2010

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 Löh and Doaitse Swierstra. Published as a functional pearl at the Haskell Workshop 2001:

https://www.cs.ox.ac.uk/jeremy.gibbons/wg21/meeting56/loeh-paper.pdf

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 (e.g. ReadP) this can be described using the Applicative instance by:

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

Permutation type

1 declaration

Permutation evaluators

2 declarations
valuerunPermutation
  1. :: Alternative m
  2. => Permutation m a

    Permutation specification

  3. -> m a

    Resulting base monad capable of handling the permutation

#

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

valueintercalateEffect
  1. :: Alternative m
  2. => m b

    Effect to be intercalated between permutation components

  3. -> Permutation m a

    Permutation specification

  4. -> m a

    Resulting base applicative 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 ':') $
         (,,) <$> toPermutationWithDefault "" (some (char 'a'))
              <*> toPermutation (char 'b')
              <*> toPermutationWithDefault '_' (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.

  • If an effect is encountered after a component, another component must immediately follow the effect.

Permutation constructors

2 declarations
valuetoPermutationWithDefault
  1. :: Alternative m
  2. => a

    Default Value

  3. -> m a

    Permutation component

  4. -> 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.