3-- Module : Streamly.Data.Parser
4-- Copyright : (c) 2020 Composewell Technologies
5-- License : BSD-3-Clause
6-- Maintainer : streamly@composewell.com
7-- Stability : pre-release
10-- Parsers are stream consumers like folds with the following differences:
12-- * folds cannot fail but parsers can fail and backtrack.
13-- * folds can be composed as a Tee but parsers cannot.
14-- * folds can be used for scanning but parsers cannot.
15-- * folds can be converted to parsers.
17-- This module implements parsers with stream fusion which compile to efficient
18-- loops comparable to the speed of C.
22-- This module provides elementary parsers and parser combinators that can be
23-- used to parse a stream of data. Additionally, all the folds from the
24-- "Streamly.Data.Fold" module can be converted to parsers using 'fromFold'.
25-- All the parsing functionality provided by popular parsing libraries, and
26-- more is available. Also see "Streamly.Unicode.Parser" module for Char stream
29-- A data stream can be transformed to a stream of parsed data elements. Parser
30-- combinators can be used to create a pipeline of folds or parsers such that
31-- the next fold or parser consumes the result of the previous parser. See
32-- 'Streamly.Data.Stream.parse' and 'Streamly.Data.Stream.parseMany' to run
33-- these parsers on a stream.
35-- == Parser vs ParserK
37-- There are two functionally equivalent parsing modules,
38-- "Streamly.Data.Parser" (this module) and "Streamly.Data.ParserK". The latter
39-- is a CPS based wrapper over the former, and can be used for parsing in
40-- general. "Streamly.Data.Parser" enables stream fusion and should be
41-- preferred over "Streamly.Data.ParserK" for high performance stream parsing
42-- use cases. However, there are a few cases where this module is not
43-- suitable and ParserK should be used instead.
45-- For static fusion, parser combinators have to use strict pattern matching on
46-- arguments of type Parser. This leads to infinte loop when a parser is
47-- defined recursively, due to strict evaluation of the recursive call. For
48-- example, the following implementation loops infinitely because of the
49-- recursive use of parser @p@ in the @*>@ combinator:
51-- >>> import Streamly.Data.Parser (Parser)
52-- >>> import qualified Streamly.Data.Fold as Fold
53-- >>> import qualified Streamly.Data.Parser as Parser
54-- >>> import qualified Streamly.Data.Stream as Stream
55-- >>> import Control.Applicative ((<|>))
58-- >>> p :: Monad m => Parser Char m String
59-- >>> p = Parser.satisfy (== '(') *> p <|> Parser.fromFold Fold.toList
62-- Use ParserK when recursive use is required:
64-- >>> import Streamly.Data.ParserK (ParserK)
65-- >>> import qualified Streamly.Data.StreamK as StreamK
66-- >>> import qualified Streamly.Internal.Data.StreamK as StreamK (parse)
67-- >>> import qualified Streamly.Internal.Data.ParserK as ParserK (adapt)
70-- >>> p :: Monad m => ParserK Char m String
71-- >>> p = ParserK.adapt (Parser.satisfy (== '(')) *> p <|> ParserK.adapt (Parser.fromFold Fold.toList)
74-- >>> StreamK.parse p $ StreamK.fromStream $ Stream.fromList "hello"
77-- For this reason Applicative, Alternative or Monad compositions with
78-- recursion cannot be used with the 'Parser' type. Alternative type class based
79-- operations like 'asum' and Alternative based generic parser combinators use
80-- recursion. Similarly, Applicative type class based operations like
81-- 'Prelude.sequence' use recursion. Custom implementations of many such
82-- operations are provided in this module (e.g. 'some', 'many'), and those
83-- should be used instead.
85-- Another limitation of Parser type is due to the quadratic complexity causing
86-- slowdown when too many nested compositions are used. Especially Applicative,
87-- Monad, Alternative instances, and sequenced parsing operations (e.g. nested
88-- 'one', and 'splitWith') degrade the performance quadratically (O(n^2)) when
89-- combined @n@ times, roughly 8 or less sequenced parsers are fine. READ THE
90-- DOCS OF APPLICATIVE, MONAD AND ALTERNATIVE INSTANCES.
92-- == Streaming Parsers
94-- With 'Streamly.Data.ParserK.ParserK' you can use the generic Alternative
95-- type class based parsers from the
96-- <https://hackage.haskell.org/package/parser-combinators parser-combinators>
97-- library or similar. However, we recommend that you use the equivalent
98-- functionality from this module for better performance and for streaming
101-- Firstly, the combinators in this module are faster due to stream fusion.
102-- Secondly, these are streaming in nature as the results can be passed
103-- directly to other stream consumers (folds or parsers). The Alternative type
104-- class based parsers would end up buffering all the results in lists before
105-- they can be consumed.
107-- When recursion or heavy nesting is needed use ParserK.
111-- These parsers do not report the error context (e.g. line number or column).
112-- This may be supported in future.
114-- == Monad Transformer Stack
116-- 'MonadTrans' instance is not provided. If the 'Parser' type is the top most
117-- layer (which should be the case almost always) you can just use 'fromEffect'
118-- to execute the lower layer monad effects.
120-- == Parser vs ParserK Implementation
122-- The 'Parser' type represents a stream consumer by composing state as data
123-- which enables stream fusion. Stream fusion generates a tight loop without
124-- any constructor allocations between the stages, providing C like performance
125-- for the loop. Stream fusion works when multiple functions are combined in a
126-- pipeline statically. Therefore, the operations in this module must be
127-- inlined and must not be used recursively to allow for stream fusion.
129-- The 'ParserK' type represents a stream consumer by composing function calls,
130-- therefore, a function call overhead is incurred at each composition. It is
131-- quite fast in general but may be a few times slower than a fused parser.
132-- However, it allows for scalable dynamic composition especially parsers can
133-- be used in recursive calls. Using the 'ParserK' type operations like
134-- 'splitWith' provide linear (O(n)) performance with respect to the number of
137-- == Experimental APIs
139-- Please refer to "Streamly.Internal.Data.Parser" for functions that have not
142module Streamly.Data.Parser
145 -- | To execute the code examples provided in this module in ghci, please
146 -- run the following commands first.
153 -- -- * Downgrade to Fold
169 -- ** Element parsers
171 -- All of these can be expressed in terms of either
190 -- ** Mapping on input
203 -- ** Tokenize by length
209 -- ** Tokenize by predicate
222 , groupByRollingEither
227 -- , wordProcessQuotes
238 -- ** De-interleaving
244import Streamly.Internal.Data.Parser
245import Prelude hiding (dropWhile, takeWhile, filter)
247#include "DocTestDataParser.hs"
keysesc to close
- j k
- move down, up
- enter
- open
- esc
- back, or up a level
- 1 2 3 4
- readme, files, commits, refs
- /
- filter
- y
- copy the clone command
- c
- compare the chosen commit with another (or shift-click both)
- ?
- show or hide this list