git.iko.soy/streamly
on dbf9fe8 help sign in
streamly/core/src/Streamly/Data/Parser.hs
177 lines 5.1 kB history raw
1{-# LANGUAGE CPP #-}
2-- |
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
8-- Portability : GHC
9--
10-- Fast, composable stream consumers with ability to terminate, backtrack and
11-- fail, supporting stream fusion. Parsers are a natural extension of
12-- "Streamly.Data.Fold". Parsers and folds can be interconverted.
13--
14-- Please refer to "Streamly.Internal.Data.Parser" for functions that have
15-- not yet been released.
16--
17module Streamly.Data.Parser
18 (
19 -- * Setup
20 -- | To execute the code examples provided in this module in ghci, please
21 -- run the following commands first.
22 --
23 -- $setup
25 -- * Overview
26 -- $overview
28 -- * Parser Type
29 Parser
31 -- -- * Downgrade to Fold
32 -- , toFold
34 -- * Parsers
35 -- ** From Folds
36 , fromFold
38 -- ** Without Input
39 -- , fromFoldMaybe
40 , fromPure
41 , fromEffect
42 , die
43 -- , dieM
44 , peek
45 , eof
47 -- ** Element parsers
49 -- All of these can be expressed in terms of either
50 , one
51 -- , oneEq
52 -- , oneNotEq
53 , oneOf
54 , noneOf
55 , satisfy
56 -- , maybe
57 -- , either
59 -- ** Sequences
60 , streamEqBy
61 , listEqBy
62 , listEq
64 -- * Combinators
65 -- Mapping on output
66 -- , rmapM
68 -- ** Mapping on input
69 , lmap
70 , lmapM
72 -- * Map on output
73 , rmapM
75 -- ** Filtering
76 , filter
78 -- ** Look Ahead
79 , lookAhead
81 -- ** Tokenize by length
82 -- , takeBetween
83 , takeEQ
84 -- , takeGE
85 -- , takeP
87 -- ** Tokenize by predicate
88 -- , takeWhileP
89 , takeWhile
90 , takeWhile1
91 , dropWhile
92 -- , takeEndBy
93 -- , takeEndByEsc
94 -- , takeStartBy
95 , wordBy
97 -- ** Grouping
98 , groupBy
99 , groupByRolling
100 , groupByRollingEither
102 -- ** Framing
103 -- , wordFramedBy
104 , wordWithQuotes
105 -- , wordProcessQuotes
106 -- , wordKeepQuotes
108 -- -- * Alternative
109 -- , alt
111 -- ** Splitting
112 , many
113 , some
114 , manyTill
116 -- ** De-interleaving
117 , deintercalate
118 )
120where
122import Streamly.Internal.Data.Parser
123import Prelude hiding (dropWhile, takeWhile, filter)
125#include "DocTestDataParser.hs"
127-- $overview
128--
129-- Several combinators in this module can be many times faster than CPS based
130-- parsers because of stream fusion. For example,
131-- 'Streamly.Internal.Data.Parser.many' combinator in this module is much
132-- faster than the 'Control.Applicative.many' combinator of
133-- 'Control.Applicative.Alternative' type class used by CPS based parsers.
134--
135-- The use of 'Alternative' type class, in parsers has another drawback.
136-- Alternative based parsers use plain Haskell lists to collect the results. In
137-- a strict Monad like IO, the results are necessarily buffered before they can
138-- be consumed. This may not perform optimally in streaming applications
139-- processing large amounts of data. Equivalent combinators in this module can
140-- consume the results of parsing using a 'Fold' or another parser, thus
141-- providing a scalable and composable consumer.
142--
143-- Note that these parsers do not report the error context (e.g. line number or
144-- column). This may be supported in future.
145--
146-- mtl instances are not provided. If the 'Parser' type is the top most layer
147-- (which should be the case almost always) you can just use 'fromEffect' to
148-- execute the lower layer monad effects.
149--
150-- == Performance Notes
151--
152-- The 'Parser' type represents a stream consumer by composing state as data
153-- which enables stream fusion. Stream fusion generates a tight loop without
154-- any constructor allocations between the stages, providing C like performance
155-- for the loop. Stream fusion works when multiple functions are combined in a
156-- pipeline statically. Therefore, the operations in this module must be
157-- inlined and must not be used recursively to allow for stream fusion. Note
158-- that operations like 'sequence', and 'asum' that compose pasrers using
159-- recursion should be avoided with these parsers. You can use these with the
160-- 'ParserK' module instead.
161--
162-- Using the 'Parser' type, parsing operations like 'one', 'splitWith' etc.
163-- degrade quadratically (O(n^2)) when combined many times. If you need to
164-- combine these operations, say more than 8 times in a single loop, then you
165-- should consider using the continuation style parser type 'ParserK' instead.
166-- Also, if you need to use these operations in a recursive loop you should use
167-- 'ParserK' instead.
168--
169-- The 'ParserK' type represents a stream consumer by composing function calls,
170-- therefore, a function call overhead is incurred at each composition. It is
171-- quite fast in general but may be a few times slower than a fused parser.
172-- However, it allows for scalable dynamic composition especially parsers can
173-- be used in recursive calls. Using the 'ParserK' type operations like
174-- 'splitWith' provide linear (O(n)) performance with respect to the number of
175-- compositions..
176--
177-- 'Parser' and 'ParserK' types can be interconverted.