 | parsec-3.0.0: Monadic parser combinators | Contents | Index |
| Text.Parsec.Perm |
|
This module implements permutation parsers. The algorithm used is fairly complex since we push the type system to its limits :-) 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.
| type PermParser tok st a = StreamPermParser String st a |
| data StreamPermParser s st a |
| permute :: Stream s Identity tok => StreamPermParser s st a -> Parsec s st a |
| (<||>) :: Stream s Identity tok => StreamPermParser s st (a -> b) -> Parsec s st a -> StreamPermParser s st b |
| (<$$>) :: Stream s Identity tok => (a -> b) -> Parsec s st a -> StreamPermParser s st b |
| (<|?>) :: Stream s Identity tok => StreamPermParser s st (a -> b) -> (a, Parsec s st a) -> StreamPermParser s st b |
| (<$?>) :: Stream s Identity tok => (a -> b) -> (a, Parsec s st a) -> StreamPermParser s st b |
The type StreamPermParser s st a denotes a permutation parser that, when converted by the permute function, parses s streams with user state st and returns a value of type a on success. Normally, a permutation parser is first build with special operators like (<||>) and than transformed into a normal parser using permute. |
The parser permute perm parses a permutation of parser described by perm. For example, suppose we want to parse a permutation of: an optional string of a's, the character b and an optional c. This can be described by:
test = permute (tuple <$?> ("",many1 (char 'a'))
<||> char 'b'
<|?> ('_',char 'c'))
where
tuple a b c = (a,b,c)
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.