Modulestreamly-core-0.3.1Haskell2010

Streamly.Data.Parser

Parsers are more powerful but less general than Streamly.Data.Fold.Folds:

folds cannot fail but parsers can fail and backtrack.
folds can be composed as a Tee but parsers cannot.
folds can be converted to parsers.

Streamly parsers support all operations offered by popular Haskell parser libraries. Unlike other parser libraries, (1) streamly parsers can operate on any Haskell type as input - not just bytes, (2) natively support streaming, (3) and are faster.

High Performance by Static Parser Fusion

Like folds, parsers are designed to utilize stream fusion, compiling to efficient low-level code comparable to the speed of C. Parsers are suitable for high-performance parsing of streams.

Operations in this module are designed to be composed statically rather than dynamically. They are inlined to enable static fusion. More importantly, they are not designed to be used recursively. Recursive use will break fusion and lead to quadratic performance slowdown. For dynamic and recursive compositions use the continuation passing style (CPS) operations from the Streamly.Data.ParserK module. Parser and Streamly.Data.ParserK.ParserK types are interconvertible.

How to parse a stream?

Parser combinators can be used to create a pipeline of parsers such that the next parser consumes the result of the previous parser. Such a composed pipeline of parsers can then be driven by one of many parser drivers available in the Stream and Array modules.

Use Streamly.Data.Stream.Streamly.Data.Stream.parse or Streamly.Data.Stream.Streamly.Data.Stream.parseBreak to run a parser on an input stream and return the parsed result.

Use Streamly.Data.Stream.Streamly.Data.Stream.parseMany or Streamly.Data.Stream.Streamly.Data.Stream.parseIterate to transform an input data stream to an output stream of parsed data elements using a parser.

Parser vs ParserK

There are two functionally equivalent parsing modules, Streamly.Data.Parser (this module) and Streamly.Data.ParserK. The latter is a CPS based wrapper over the former, and can be used for parsing in general. Streamly.Data.Parser enables stream fusion and where possible it should be preferred over Streamly.Data.ParserK for high performance stream parsing use cases. However, there are a few cases where this module is not suitable and ParserK should be used instead. As a thumb rule, when recursion or heavy nesting is needed use ParserK.

Parser: suitable for non-recursive static fusion

The Parser type is suitable only for non-recursive static fusion. It could be problematic for recursive definitions. To enable static fusion, parser combinators use strict pattern matching on arguments of type Parser. This leads to infinte loop when a parser is defined recursively, due to strict evaluation of the recursive call. For example, the following implementation loops infinitely because of the recursive use of parser p in the *> combinator:

Example5 expressions

>>> import Streamly.Data.Parser (Parser)>>> import qualified Streamly.Data.Fold as Fold>>> import qualified Streamly.Data.Parser as Parser>>> import qualified Streamly.Data.Stream as Stream>>> import Control.Applicative ((<|>))

Example6 expressions

>>> :{>>> p, p1, p2 :: Monad m => Parser Char m String>>> p1 = Parser.satisfy (== '(') *> p>>> p2 = Parser.fromFold Fold.toList>>> p = p1 <|> p2>>> :}

Another limitation of Parser type quadratic performance slowdown when too many nested compositions are used. Especially Applicative, Monad, Alternative instances, and sequenced parsing operations (e.g. nested one, and splitWith) exhibit quadratic slowdown (O(n^2) complexity) when combined n times, roughly 8 or less sequenced parsers usually work fine. READ THE DOCS OF APPLICATIVE, MONAD AND ALTERNATIVE INSTANCES.

ParserK: suitable for recursive definitions

ParserK is suitable for recursive definitions:

Example3 expressions

>>> import Streamly.Data.ParserK (ParserK)>>> import Streamly.Data.StreamK (toParserK)>>> import qualified Streamly.Data.StreamK as StreamK

Example6 expressions

>>> :{>>> p, p1, p2 :: Monad m => ParserK Char m String>>> p1 = toParserK (Parser.satisfy (== '(')) *> p>>> p2 = toParserK (Parser.fromFold Fold.toList)>>> p = p1 <|> p2>>> :}

Example1 expression

>>> StreamK.parse p $ StreamK.fromStream $ Stream.fromList "hello"Right "hello"

For this reason Applicative, Alternative or Monad compositions with recursion cannot be used with the Parser type. Alternative type class based operations like asum and Alternative based generic parser combinators use recursion. Similarly, Applicative type class based operations like sequence use recursion. Custom implementations of many such operations are provided in this module (e.g. some, many), and those should be used instead.

Parsers Galore!

Streamly provides all the parsing functionality provided by popular parsing libraries, and much more with higher performance. This module provides most of the elementary parsers and parser combinators. Additionally,

all the folds from the Streamly.Data.Fold module can be converted to parsers using fromFold.
Streamly.Unicode.Parser module provides Char stream parsers.
all the combinators from the parser-combinators package can be used with streamly ParserK.
See Streamly.Internal.Data.Parser for many more unreleased but useful APIs.

Generic Parser Combinators

With Streamly.Data.ParserK.ParserK you can use the Applicative and Alternative type class based generic parser combinators from the parser-combinators library or similar. However, if available, we recommend that you use the equivalent functionality from this module where performance and streaming behavior matters. Firstly, the combinators in this module are faster due to stream fusion. Secondly, these are streaming in nature as the results can be passed directly to other stream consumers (folds or parsers). The Alternative type class based parsers would end up buffering all the results in lists before they can be consumed.

Error Reporting

There are two types of parser drivers available, parse and parseBreak drivers do not track stream position, whereas parsePos and parseBreakPos drivers track and report stream position information with slightly more performance overhead.

When an error occurs the stream position is reported, in case of byte streams or unboxed array streams this is the byte position, in case of generic element parsers or generic array parsers this is the element position in the stream.

These parsers do not report a case specific error context (e.g. line number or column). If you need line number or column information you can read the stream again (if it is immutable) and this count the lines to translate the reported byte position to line number and column. More elaborate support for building arbitrary and custom error context information is planned to be added in future.

Monad Transformer Stack

MonadTrans instance is not provided. If the Parser type is the top most layer (which should be the case almost always) you can just use fromEffect to execute the lower layer monad effects.

Experimental APIs

Please refer to Streamly.Internal.Data.Parser for functions that have not yet been released.

3 types
31 values

Packagestreamly-core-0.3.1
Exports34
LanguageHaskell2010
LicenceBSD-3-Clause
SourceParser.hs

Setup

0 declarations

To execute the code examples provided in this module in ghci, please run the following commands first.

Example6 expressions

>>> :m>>> import Control.Applicative ((<|>))>>> import Data.Bifunctor (second)>>> import Data.Char (isSpace)>>> import qualified Data.Foldable as Foldable>>> import qualified Data.Maybe as Maybe

Example2 expressions

>>> import Streamly.Data.Fold (Fold)>>> import Streamly.Data.Parser (Parser)

Example3 expressions

>>> import qualified Streamly.Data.Fold as Fold>>> import qualified Streamly.Data.Parser as Parser>>> import qualified Streamly.Data.Stream as Stream

For APIs that have not been released yet.

Example2 expressions

>>> import qualified Streamly.Internal.Data.Fold as Fold>>> import qualified Streamly.Internal.Data.Parser as Parser

Parser Type

3 declarations

datadata Parser a (m :: Type -> Type) b

A parser is a fold that can fail and is represented as Parser step initial extract. Before we drive a parser we call the initial action to retrieve the initial state of the fold. The parser driver invokes step with the state returned by the previous step and the next input element. It results into a new state and a command to the driver represented by Step type. The driver keeps invoking the step function until it stops or fails. At any point of time the driver can call extract to inspect the result of the fold. If the parser hits the end of input extract is called. It may result in an error or an output value.

Pre-release

Instances6Monad, Functor, MonadFail, Applicative, Alternative, MonadIO

Monad m => Monad (Parser a m)Defined in streamly-core-0.3.1 · Streamly.Internal.Data.Parser.Type
READ THE CAVEATS in concatMap before using this instance.
Example1 expression
```
>>> (>>=) = flip Parser.concatMap
```
Functor m => Functor (Parser a m)Defined in streamly-core-0.3.1 · Streamly.Internal.Data.Parser.Type
Map a function on the result i.e. on b in Parser a m b.
Monad m => MonadFail (Parser a m)Defined in streamly-core-0.3.1 · Streamly.Internal.Data.Parser.Type
Example1 expression
```
>>> fail = Parser.die
```
Monad m => Applicative (Parser a m)Defined in streamly-core-0.3.1 · Streamly.Internal.Data.Parser.Type
READ THE CAVEATS in splitWith before using this instance.
Example3 expressions
```
>>> pure = Parser.fromPure>>> (<*>) = Parser.splitWith id>>> (*>) = Parser.split_
```
Monad m => Alternative (Parser a m)Defined in streamly-core-0.3.1 · Streamly.Internal.Data.Parser.Type
READ THE CAVEATS in alt before using this instance.
Example4 expressions
```
>>> empty = Parser.die "empty">>> (<|>) = Parser.alt>>> many = flip Parser.many Fold.toList>>> some = flip Parser.some Fold.toList
```
MonadIO m => MonadIO (Parser a m)Defined in streamly-core-0.3.1 · Streamly.Internal.Data.Parser.Type
Example1 expression
```
>>> liftIO = Parser.fromEffect . liftIO
```

newtypenewtype ParseError

This exception is used when a parser ultimately fails, the user of the parser is intimated via this exception.

Constructors

ParseError String

Instances3Eq, Show, Exception

Eq ParseErrorDefined in streamly-core-0.3.1 · Streamly.Internal.Data.Parser.Type
Show ParseErrorDefined in streamly-core-0.3.1 · Streamly.Internal.Data.Parser.Type
Exception ParseErrorDefined in streamly-core-0.3.1 · Streamly.Internal.Data.Parser.Type

datadata ParseErrorPos

Like ParseError but reports the stream position where the error ocurred. The Int is the position in the stream where the error ocurred. This exception is used by position reporting parser drivers.

Constructors

ParseErrorPos Int String

Instances3Eq, Show, Exception

Eq ParseErrorPosDefined in streamly-core-0.3.1 · Streamly.Internal.Data.Parser.Type
Show ParseErrorPosDefined in streamly-core-0.3.1 · Streamly.Internal.Data.Parser.Type
Exception ParseErrorPosDefined in streamly-core-0.3.1 · Streamly.Internal.Data.Parser.Type

Elementary Parsers

0 declarations

From Folds

valuefromFold :: Monad m => Fold m a b -> Parser a m b

Make a Parser from a Fold. This parser sends all of its input to the fold.

Without Input

valuefromPure :: Monad m => b -> Parser a m b

A parser that always yields a pure value without consuming any input.

valuefromEffect :: Monad m => m b -> Parser a m b

A parser that always yields the result of an effectful action without consuming any input.

valuedie :: Monad m => String -> Parser a m b

A parser that always fails with an error message without consuming any input.

valuepeek :: Monad m => Parser a m a

Peek the head element of a stream, without consuming it. Fails if it encounters end of input.

Example1 expression

>>> Stream.parse ((,) <$> Parser.peek <*> Parser.satisfy (> 0)) $ Stream.fromList [1]Right (1,1)

peek = lookAhead (satisfy True)

valueeof :: Monad m => Parser a m ()

Succeeds if we are at the end of input, fails otherwise.

Example1 expression

>>> Stream.parse ((,) <$> Parser.satisfy (> 0) <*> Parser.eof) $ Stream.fromList [1]Right (1,())

Single Elements

valueone :: Monad m => Parser a m a

Consume one element from the head of the stream. Fails if it encounters end of input.

Example1 expression

>>> one = Parser.satisfy $ const True

valueoneOf :: (Monad m, Eq a, Foldable f) => f a -> Parser a m a

Match any one of the elements in the supplied list.

Example1 expression

>>> oneOf xs = Parser.satisfy (`Foldable.elem` xs)

When performance matters a pattern matching predicate could be more efficient than a Foldable datatype:

let p x =
   case x of
      a -> True
      e -> True
       _  -> False
in satisfy p

GHC may use a binary search instead of linear search in the list. Alternatively, you can also use an array instead of list for storage and search.

valuenoneOf :: (Monad m, Eq a, Foldable f) => f a -> Parser a m a

See performance notes in oneOf.

Example1 expression

>>> noneOf xs = Parser.satisfy (`Foldable.notElem` xs)

valuesatisfy :: Monad m => (a -> Bool) -> Parser a m a

Returns the next element if it passes the predicate, fails otherwise.

Example1 expression

>>> Stream.parse (Parser.satisfy (== 1)) $ Stream.fromList [1,0,1]Right 1

Example2 expressions

>>> toMaybe f x = if f x then Just x else Nothing>>> satisfy f = Parser.maybe (toMaybe f)

Sequences

valuestreamEqBy :: Monad m => (a -> a -> Bool) -> Stream m a -> Parser a m ()

Like listEqBy but uses a stream instead of a list and does not return the stream.

valuelistEqBy :: Monad m => (a -> a -> Bool) -> [a] -> Parser a m [a]

Match the given sequence of elements using the given comparison function. Returns the original sequence if successful.

Definition:

Example1 expression

>>> listEqBy cmp xs = Parser.streamEqBy cmp (Stream.fromList xs) *> Parser.fromPure xs

Examples:

Example1 expression

>>> Stream.parse (Parser.listEqBy (==) "string") $ Stream.fromList "string"Right "string"

Example1 expression

>>> Stream.parsePos (Parser.listEqBy (==) "mismatch") $ Stream.fromList "match"Left (ParseErrorPos 2 "streamEqBy: mismtach occurred")

valuelistEq :: (Monad m, Eq a) => [a] -> Parser a m [a]

Match the input sequence with the supplied list and return it if successful.

Example1 expression

>>> listEq = Parser.listEqBy (==)

Transformations

0 declarations

Map on input

valuelmap :: (a -> b) -> Parser b m r -> Parser a m r

lmap f parser maps the function f on the input of the parser.

Example1 expression

>>> Stream.parse (Parser.lmap (\x -> x * x) (Parser.fromFold Fold.sum)) (Stream.enumerateFromTo 1 100)Right 338350

lmap = Parser.lmapM return

valuelmapM :: Monad m => (a -> m b) -> Parser b m r -> Parser a m r

lmapM f parser maps the monadic function f on the input of the parser.

Map on output

valuermapM :: Monad m => (b -> m c) -> Parser a m b -> Parser a m c

rmapM f parser maps the monadic function f on the output of the parser.

Example1 expression

>>> rmap = fmap

Filtering

valuefilter :: Monad m => (a -> Bool) -> Parser a m b -> Parser a m b

Include only those elements that pass a predicate.

Example1 expression

>>> Stream.parse (Parser.filter (> 5) (Parser.fromFold Fold.sum)) $ Stream.fromList [1..10]Right 40

Look Ahead

valuelookAhead :: Monad m => Parser a m b -> Parser a m b

Run a parser without consuming the input.

Tokenizing Combinators

0 declarations

Tokenize by length

valuetakeEQ :: Monad m => Int -> Fold m a b -> Parser a m b

Stops after taking exactly n input elements.

Stops - after consuming n elements.
Fails - if the stream or the collecting fold ends before it can collect exactly n elements.

Example1 expression

>>> Stream.parsePos (Parser.takeEQ 2 Fold.toList) $ Stream.fromList [1,0,1]Right [1,0]

Example1 expression

>>> Stream.parsePos (Parser.takeEQ 4 Fold.toList) $ Stream.fromList [1,0,1]Left (ParseErrorPos 3 "takeEQ: Expecting exactly 4 elements, input terminated on 3")

Tokenize by predicate

valuetakeWhile :: Monad m => (a -> Bool) -> Fold m a b -> Parser a m b

Collect stream elements until an element fails the predicate. The element on which the predicate fails is returned back to the input stream.

Stops - when the predicate fails or the collecting fold stops.
Fails - never.

Example1 expression

>>> Stream.parse (Parser.takeWhile (== 0) Fold.toList) $ Stream.fromList [0,0,1,0,1]Right [0,0]

Example1 expression

>>> takeWhile cond f = Parser.takeWhileP cond (Parser.fromFold f)

We can implement a breakOn using takeWhile:

breakOn p = takeWhile (not p)

valuetakeWhile1 :: Monad m => (a -> Bool) -> Fold m a b -> Parser a m b

Like takeWhile but takes at least one element otherwise fails.

Example1 expression

>>> takeWhile1 cond p = Parser.takeWhileP cond (Parser.takeBetween 1 maxBound p)

valuedropWhile :: Monad m => (a -> Bool) -> Parser a m ()

Drain the input as long as the predicate succeeds, running the effects and discarding the results.

This is also called skipWhile in some parsing libraries.

Example1 expression

>>> dropWhile p = Parser.takeWhile p Fold.drain

valuewordBy :: Monad m => (a -> Bool) -> Fold m a b -> Parser a m b

Like splitOn but strips leading, trailing, and repeated separators. Therefore, ".a..b." having . as the separator would be parsed as ["a","b"]. In other words, its like parsing words from whitespace separated text.

Stops - when it finds a word separator after a non-word element
Fails - never.

Example1 expression

>>> wordBy = Parser.wordFramedBy (const False) (const False) (const False)

S.wordsBy pred f = S.parseMany (PR.wordBy pred f)

Grouping

valuegroupBy :: Monad m => (a -> a -> Bool) -> Fold m a b -> Parser a m b

Given an input stream [a,b,c,...] and a comparison function cmp, the parser assigns the element a to the first group, then if a `cmp` b is True b is also assigned to the same group. If a `cmp` c is True then c is also assigned to the same group and so on. When the comparison fails the parser is terminated. Each group is folded using the Fold f and the result of the fold is the result of the parser.

Stops - when the comparison fails.
Fails - never.

Example1 expression

>>> :{ runGroupsBy eq =     Stream.fold Fold.toList         . Stream.parseMany (Parser.groupBy eq Fold.toList)         . Stream.fromList:}

Example1 expression

>>> runGroupsBy (<) [][]

Example1 expression

>>> runGroupsBy (<) [1][Right [1]]

Example1 expression

>>> runGroupsBy (<) [3, 5, 4, 1, 2, 0][Right [3,5,4],Right [1,2],Right [0]]

valuegroupByRolling :: Monad m => (a -> a -> Bool) -> Fold m a b -> Parser a m b

Unlike groupBy this combinator performs a rolling comparison of two successive elements in the input stream. Assuming the input stream is [a,b,c,...] and the comparison function is cmp, the parser first assigns the element a to the first group, then if a `cmp` b is True b is also assigned to the same group. If b `cmp` c is True then c is also assigned to the same group and so on. When the comparison fails the parser is terminated. Each group is folded using the Fold f and the result of the fold is the result of the parser.

Stops - when the comparison fails.
Fails - never.

Example1 expression

>>> :{ runGroupsByRolling eq =     Stream.fold Fold.toList         . Stream.parseMany (Parser.groupByRolling eq Fold.toList)         . Stream.fromList:}

Example1 expression

>>> runGroupsByRolling (<) [][]

Example1 expression

>>> runGroupsByRolling (<) [1][Right [1]]

Example1 expression

>>> runGroupsByRolling (<) [3, 5, 4, 1, 2, 0][Right [3,5],Right [4],Right [1,2],Right [0]]

Pre-release

valuegroupByRollingEither

:: Monad m
=> a -> a -> Bool
-> Fold m a b
-> Fold m a c
-> Parser a m (Either b c)

Like groupByRolling, but if the predicate is True then collects using the first fold as long as the predicate holds True, if the predicate is False collects using the second fold as long as it remains False. Returns Left for the first case and Right for the second case.

For example, if we want to detect sorted sequences in a stream, both ascending and descending cases we can use 'groupByRollingEither (<=) Fold.toList Fold.toList'.

Pre-release

Framing

valuewordWithQuotes

:: (Monad m, Eq a)
=> Bool
Retain the quotes and escape chars in the output
-> (a -> a -> Maybe a)
quote char -> escaped char -> translated char
-> a
Matches an escape elem?
-> (a -> Maybe a)
If left quote, return right quote, else Nothing.
-> (a -> Bool)
Matches a word separator?
-> Fold m a b
-> Parser a m b

Quote and bracket aware word splitting with escaping. Like wordBy but word separators within specified quotes or brackets are ignored. Quotes and escape characters can be processed. If the end quote is different from the start quote it is called a bracket. The following quoting rules apply:

In an unquoted string a character may be preceded by an escape character. The escape character is removed and the character following it is treated literally with no special meaning e.g. e.g. h e l l o is a single word, n is same as n.
Any part of the word can be placed within quotes. Inside quotes all characters are treated literally with no special meaning. Quoting character itself cannot be used within quotes unless escape processing within quotes is applied to allow it.
Optionally escape processing for quoted part can be specified. Escape character has no special meaning inside quotes unless it is followed by a character that has a escape translation specified, in that case the escape character is removed, and the specified translation is applied to the character following it. This can be used to escape the quoting character itself within quotes.
There can be multiple quoting characters, when a quote starts, all other quoting characters within that quote lose any special meaning until the quote is closed.
A starting quote char without an ending char generates a parse error. An ending bracket char without a corresponding bracket begin is ignored.
Brackets can be nested.

We should note that unquoted and quoted escape processing are different. In unquoted part escape character is always removed. In quoted part it is removed only if followed by a special meaning character. This is consistent with how shell performs escape processing.

Splitting

3 declarations

valuemany :: Monad m => Parser a m b -> Fold m b c -> Parser a m c

Collect zero or more parses. Apply the supplied parser repeatedly on the input stream and push the parse results to a downstream fold.

Stops: when the downstream fold stops or the parser fails. Fails: never, produces zero or more results.

Example1 expression

>>> many = Parser.countBetween 0 maxBound

Compare with many.

valuesome :: Monad m => Parser a m b -> Fold m b c -> Parser a m c

Collect one or more parses. Apply the supplied parser repeatedly on the input stream and push the parse results to a downstream fold.

Stops: when the downstream fold stops or the parser fails. Fails: if it stops without producing a single result.

Example2 expressions

>>> some p f = Parser.manyP p (Parser.takeGE 1 f)>>> some = Parser.countBetween 1 maxBound

Compare with some.

valuemanyTill

:: Monad m
=> Parser a m b
-> Parser a m x
-> Fold m b c
-> Parser a m c

manyTill p test f tries the parser test on the input, if test fails it backtracks and tries p, after p succeeds test is tried again and so on. The parser stops when test succeeds. The output of test is discarded and the output of p is accumulated by the supplied fold. The parser fails if p fails.

Stops when the fold f stops.

De-interleaving

1 declaration

valuedeintercalate

:: Monad m
=> Parser a m x
-> Parser a m y
-> Fold m (Either x y) z
-> Parser a m z

Apply two parsers alternately to an input stream. The input stream is considered an interleaving of two patterns. The two parsers represent the two patterns. Parsing starts at the first parser and stops at the first parser. It can be used to parse a infix style pattern e.g. p1 p2 p1 . Empty input or single parse of the first parser is accepted.

Example7 expressions

>>> p1 = Parser.takeWhile1 (not . (== '+')) Fold.toList>>> p2 = Parser.satisfy (== '+')>>> p = Parser.deintercalate p1 p2 Fold.toList>>> Stream.parse p $ Stream.fromList ""Right []>>> Stream.parse p $ Stream.fromList "1"Right [Left "1"]>>> Stream.parse p $ Stream.fromList "1+"Right [Left "1"]>>> Stream.parse p $ Stream.fromList "1+2+3"Right [Left "1",Right '+',Left "2",Right '+',Left "3"]