Generic parser library capable of providing partial results from partial input.

LTS Haskell 22.28:0.5.1
Stackage Nightly 2024-07-12:0.5.1
Latest on Hackage:0.5.1

See all snapshots incremental-parser appears in

GPL-3.0-only licensed by Mario Blazevic
Maintained by [email protected]
This version can be pinned in stack with:incremental-parser-0.5.1@sha256:b0b0d929fa5ba8f3c4791c5c53f38fbc30e2a38147dd8f6c8f40608d6a63b81d,2491

The incremental-parser library is yet another parser combinator library, providing the usual set of Applicative, Alternative, and Monad combinators. Apart from this, it has four twists that make it unique.

Parsing incrementally

First, the parser is incremental. Not only can it be fed its input in chunks, but in proper circumstances it can also provide its output in parsed chunks. For this to be possible the result type must be a Monoid. The complete parsing result is then a concatenation of the partial results.

In order to make the incremental parsing easier, the combinator set is optimized for monoidal results. Apart from the usual combinators many and some, for example, there are concatMany and concatSome operators.

    many :: Parser s r -> Parser s [r]
    concatMany :: (Monoid s, Monoid r) => Parser s r -> Parser s r

Arbitrary monoidal inputs

The second weirdness, this one shared with Picoparsec, is that the the parser is generic in its input stream type, but this type is parameterized in a holistic way. There is no separate token type. Primitive parsers that need to peek into the input require its type to be an instance of a monoid subclass, from the monoid-subclasses package.

In Parsec:

    string :: Stream s m Char => String -> ParsecT s u m String
    char :: Stream s m Char => Char -> ParsecT s u m Char
    anyToken :: (Stream s m t, Show t) => ParsecT s u m t

In Attoparsec:

    string :: ByteString -> Parser ByteString
    word8 :: Word8 -> Parser Word8
    anyWord8 :: Parser Word8

In incremental-parser and Picoparsec:

    string :: (LeftCancellativeMonoid s, MonoidNull s) => s -> Parser s s
    token :: (Eq s, FactorialMonoid s) => s -> Parser s s
    anyToken :: FactorialMonoid s => Parser s s

Two Alternative alternatives

The library being implemented on the basis of Brzozowski derivatives, it can provide both the symmetric and the left-biased choice, <||> and <<|>. This is the same design choice made by Text.ParserCombinators.ReadP and uu-parsinglib. Parsec and its progeny on the other hand provide only the faster left-biased choice, at some cost to the expressiveness of the combinator language. The standard <|> operator from the Alternative class acts as one or the other of the above, depending on whether the first type parameter of Parser is Symmetric or LeftBiasedLocal.

MonadFix and record

Finally, the parser is an instance of the MonadFix class. Beware of its power. In particular, never ever try to mfix a strict function. This will hang. The argument of mfix takes the value constructed by the argument parser at the very same input position it’s looking at. The best and probably the only safe and useful argument to mfix is the record function. See the construct library for examples.


Revision history for incremental-parser

0.5.1 – 2023-12-19

  • Replaced the ListT transformer with LogicT
  • Bumped dependency bounds
  • Fixed some compiler warnings – 2023-04-09

  • Allow monoid-subclasses-1.2 and rank2classes-1.5, thanks to felixonmars – 2022-10-03

  • Incremented dependency versions. – 2022-03-09

  • Allow checkers-0.6 – 2021-03-07

  • Incremented monoid-subclasses and input-parsers upper bounds – 2020-12-25

  • Incremented the tasty dependency version bounds

0.5 – 2020-07-18

  • Fixed the take method implementation
  • Added the DeterministicParsing instance
  • Cleaned up the comments and warnings
  • Added the InputCharParsing instance
  • Added the InputParsing instance – 2020-05-10

  • Bumped up the upper dependency bound for tasty – 2020-03-08

  • Relax bound of rank2classes to < 1.5, thanks to felixonmars

0.4 – 2020-01-21

  • Improved error reporting
  • Changed the result type of inspect to report the error message
  • Added the missing Choice in ResultStructure case, eliminated all warnings except ListT
  • Generalized the CharParsing instance
  • Added mapInput and mapInput'
  • Preserve the input left after ResultStructure
  • Generalized ResultStructure off Identity
  • Eta-reduced the Parser type synonyms
  • Added ResultStructure and the record combinator
  • Moved the source code into the src/ directory
  • Added instances for MonoidFix and *Parsing classes

0.3.3 – 2019-10-10

  • Updated for monoid-subclasses-1.0 – 2019-03-30

  • Bumped the checkers dependency version bound
  • Fixed a bug in the ordering of incremental results – 2019-12-03

  • Incremented the upper bound for tasty

0.3.2 – 2018-10-14

  • Added MonadFail instance – 2018-05-12

  • Incremented the tasty upper bound
  • Fixed compilation with GHC 8.2

0.3.1 – 2018-04-26

  • Building with GHC-8.4 and Semigroup
  • Limited the base upper bound – 2018-01-09

  • Incremented the upper bound for tasty