1{-# OPTIONS_GHC -Wno-orphans #-}
4-- Module : Streamly.Internal.Data.Parser
5-- Copyright : (c) 2020 Composewell Technologies
6-- License : BSD-3-Clause
7-- Maintainer : streamly@composewell.com
8-- Stability : pre-release
11-- Fast backtracking parsers with stream fusion and native streaming
14-- 'Applicative' and 'Control.Applicative.Alternative' type class based
15-- combinators from the
16-- <http://hackage.haskell.org/package/parser-combinators parser-combinators>
17-- package can also be used with the 'Parser' type. However, there are two
18-- important differences between @parser-combinators@ and the equivalent ones
19-- provided in this module in terms of performance:
21-- 1) @parser-combinators@ use plain Haskell lists to collect the results, in a
22-- strict Monad like IO, the results are necessarily buffered before they can
23-- be consumed. This may not perform optimally in streaming applications
24-- processing large amounts of data. Equivalent combinators in this module can
25-- consume the results of parsing using a 'Fold', thus providing a scalability
26-- and a composable consumer.
28-- 2) Several combinators in this module can be many times faster because of
29-- stream fusion. For example, 'Streamly.Internal.Data.Parser.many' combinator
30-- in this module is much faster than the 'Control.Applicative.many' combinator
31-- of 'Control.Applicative.Alternative' type class.
35-- Failing parsers in this module throw the 'D.ParseError' exception.
39-- As far as possible, try that the names of the combinators in this module are
42-- * <https://hackage.haskell.org/package/base/docs/Text-ParserCombinators-ReadP.html base/Text.ParserCombinators.ReadP>
43-- * <http://hackage.haskell.org/package/parser-combinators parser-combinators>
44-- * <http://hackage.haskell.org/package/megaparsec megaparsec>
45-- * <http://hackage.haskell.org/package/attoparsec attoparsec>
46-- * <http://hackage.haskell.org/package/parsec parsec>
48module Streamly.Internal.Data.Parser
54 -- * Downgrade to Fold
57 -- First order parsers
80 -- | Parsers chained in series, if one parser terminates the composition
83 -- | Grab a sequence of input elements without inspecting them
85 -- , take -- takeBetween 0 n
86 , takeEQ -- takeBetween n n
87 , takeGE -- takeBetween n maxBound
89 -- Grab a sequence of input elements by inspecting them
106 , groupByRollingEither
111 -- , prefixOf -- match any prefix of a given string
112 -- , suffixOf -- match any suffix of a given string
113 -- , infixOf -- match any substring of a given string
116 -- Second order parsers (parsers using parsers)
117 -- * Binary Combinators
119 -- ** Sequential Applicative
123 -- ** Parallel Applicatives
127 -- , teeTill -- like manyTill but parallel
129 -- ** Sequential Interleaving
130 -- Use two folds, run a primary parser, its rejected values go to the
134 -- ** Sequential Alternative
137 -- ** Parallel Alternatives
142 -- * N-ary Combinators
143 -- ** Sequential Collection
147 -- ** Sequential Repetition
159 -- | TODO: traditional implmentations of these may be of limited use. For
160 -- example, consider parsing lines separated by @\\r\\n@. The main parser
161 -- will have to detect and exclude the sequence @\\r\\n@ anyway so that we
162 -- can apply the "sep" parser.
164 -- We can instead implement these as special cases of deintercalate.
177 -- | A simple and stupid impl would be to just convert the stream to an
178 -- array and give the array reference to all consumers. The array can be
179 -- grown on demand by any consumer and truncated when nonbody needs it.
181 -- ** Distribute to collection
182 -- ** Distribute to repetition
184 -- ** Interleaved collection
191 -- ** Collection of Alternatives
197 -- , fastestN -- first N successful in time
198 -- , choiceN -- first N successful in position
200 , choice -- first successful in position
202 -- ** Repeated Alternatives
209import Control.Monad.Catch (MonadCatch, MonadThrow)
211 (any, all, take, takeWhile, sequence, concatMap, maybe, either, filter)
213import Streamly.Internal.Data.Fold.Type (Fold(..))
214import Streamly.Internal.Data.Parser.ParserK.Type (Parser)
216import qualified Streamly.Internal.Data.Fold.Type as FL
217import qualified Streamly.Internal.Data.Parser.ParserD as D
218import qualified Streamly.Internal.Data.Parser.ParserK.Type as K
223-- >>> :set -package streamly
224-- >>> import Prelude hiding (any, all, take, takeWhile, sequence, concatMap, maybe, either)
225-- >>> import qualified Streamly.Prelude as Stream
226-- >>> import qualified Streamly.Internal.Data.Stream.IsStream as Stream (parse, parseMany)
227-- >>> import qualified Streamly.Data.Fold as Fold
228-- >>> import qualified Streamly.Internal.Data.Parser as Parser
230-------------------------------------------------------------------------------
231-- Downgrade a parser to a Fold
232-------------------------------------------------------------------------------
234-- | Make a 'Fold' from a 'Parser'. The fold just throws an exception if the
235-- parser fails or tries to backtrack.
237-- This can be useful in combinators that accept a Fold and we know that a
238-- Parser cannot fail or failure exception is acceptable as there is no way to
244toFold :: MonadThrow m => Parser m a b -> Fold m a b
245toFold p = D.toFold $ D.fromParserK p
247-------------------------------------------------------------------------------
248-- Upgrade folds to parses
249-------------------------------------------------------------------------------
251-- | Make a 'Parser' from a 'Fold'.
255{-# INLINE fromFold #-}
256fromFold :: MonadCatch m => Fold m a b -> Parser m a b
257fromFold = D.toParserK . D.fromFold
259-------------------------------------------------------------------------------
260-- Terminating but not failing folds
261-------------------------------------------------------------------------------
263-- This is the dual of stream "fromPure".
265-- | A parser that always yields a pure value without consuming any input.
269{-# INLINE [3] fromPure #-}
270fromPure :: MonadCatch m => b -> Parser m a b
271fromPure = D.toParserK . D.fromPure
272{-# RULES "fromPure fallback to CPS" [2]
273 forall a. D.toParserK (D.fromPure a) = K.fromPure a #-}
275-- This is the dual of stream "fromEffect".
277-- | A parser that always yields the result of an effectful action without
278-- consuming any input.
282{-# INLINE fromEffect #-}
283fromEffect :: MonadCatch m => m b -> Parser m a b
284fromEffect = K.fromEffect -- D.toParserK . D.fromEffect
286-- This is the dual of "nil".
288-- | A parser that always fails with an error message without consuming
293{-# INLINE [3] die #-}
294die :: MonadCatch m => String -> Parser m a b
295die = D.toParserK . D.die
296{-# RULES "die fallback to CPS" [2]
297 forall a. D.toParserK (D.die a) = K.die a #-}
299-- This is the dual of "nilM".
301-- | A parser that always fails with an effectful error message and without
302-- consuming any input.
307dieM :: MonadCatch m => m String -> Parser m a b
308dieM = D.toParserK . D.dieM
310-------------------------------------------------------------------------------
312-------------------------------------------------------------------------------
314-- | @lmap f parser@ maps the function @f@ on the input of the parser.
316-- >>> Stream.parse (Parser.lmap (\x -> x * x) (Parser.fromFold Fold.sum)) (Stream.enumerateFromTo 1 100)
319-- > lmap = Parser.lmapM return
323lmap :: MonadCatch m => (a -> b) -> Parser m b r -> Parser m a r
324lmap f p = D.toParserK $ D.lmap f $ D.fromParserK p
326-- | @lmapM f parser@ maps the monadic function @f@ on the input of the parser.
330lmapM :: MonadCatch m => (a -> m b) -> Parser m b r -> Parser m a r
331lmapM f p = D.toParserK $ D.lmapM f $ D.fromParserK p
333-- | Include only those elements that pass a predicate.
335-- >>> Stream.parse (Parser.filter (> 5) (Parser.fromFold Fold.sum)) $ Stream.fromList [1..10]
340filter :: MonadCatch m => (a -> Bool) -> Parser m a b -> Parser m a b
341filter f p = D.toParserK $ D.filter f $ D.fromParserK p
343-------------------------------------------------------------------------------
345-------------------------------------------------------------------------------
347-- | Peek the head element of a stream, without consuming it. Fails if it
348-- encounters end of input.
350-- >>> Stream.parse ((,) <$> Parser.peek <*> Parser.satisfy (> 0)) $ Stream.fromList [1]
354-- peek = lookAhead (satisfy True)
360peek :: MonadCatch m => Parser m a a
361peek = D.toParserK D.peek
363-- | Succeeds if we are at the end of input, fails otherwise.
365-- >>> Stream.parse ((,) <$> Parser.satisfy (> 0) <*> Parser.eof) $ Stream.fromList [1]
371eof :: MonadCatch m => Parser m a ()
372eof = D.toParserK D.eof
374-- | Returns the next element if it passes the predicate, fails otherwise.
376-- >>> Stream.parse (Parser.satisfy (== 1)) $ Stream.fromList [1,0,1]
381{-# INLINE satisfy #-}
382satisfy :: MonadCatch m => (a -> Bool) -> Parser m a a
383satisfy = D.toParserK . D.satisfy
385-- | Return the next element of the input. Returns 'Nothing'
386-- on end of input. Also known as 'head'.
391next :: MonadCatch m => Parser m a (Maybe a)
392next = D.toParserK D.next
394-- | Map a 'Maybe' returning function on the next element in the stream. The
395-- parser fails if the function returns 'Nothing' otherwise returns the 'Just'
401maybe :: MonadCatch m => (a -> Maybe b) -> Parser m a b
402maybe = D.toParserK . D.maybe
404-- | Map an 'Either' returning function on the next element in the stream. If
405-- the function returns 'Left err', the parser fails with the error message
406-- @err@ otherwise returns the 'Right' value.
411either :: MonadCatch m => (a -> Either String b) -> Parser m a b
412either = D.toParserK . D.either
414-------------------------------------------------------------------------------
416-------------------------------------------------------------------------------
418-- | @takeBetween m n@ takes a minimum of @m@ and a maximum of @n@ input
419-- elements and folds them using the supplied fold.
421-- Stops after @n@ elements.
422-- Fails if the stream ends before @m@ elements could be taken.
428-- takeBetween' low high ls = Stream.parse prsr (Stream.fromList ls)
429-- where prsr = Parser.takeBetween low high Fold.toList
434-- >>> takeBetween' 2 4 [1, 2, 3, 4, 5]
437-- >>> takeBetween' 2 4 [1, 2]
440-- >>> takeBetween' 2 4 [1]
441-- *** Exception: ParseError "takeBetween: Expecting alteast 2 elements, got 1"
443-- >>> takeBetween' 0 0 [1, 2]
446-- >>> takeBetween' 0 1 []
449-- @takeBetween@ is the most general take operation, other take operations can
450-- be defined in terms of takeBetween. For example:
453-- take = takeBetween 0 n -- equivalent of take
454-- take1 = takeBetween 1 n -- equivalent of takeLE1
455-- takeEQ = takeBetween n n
456-- takeGE = takeBetween n maxBound
461{-# INLINE takeBetween #-}
462takeBetween :: MonadCatch m =>
463 Int -> Int -> Fold m a b -> Parser m a b
464takeBetween m n = D.toParserK . D.takeBetween m n
466-- | Stops after taking exactly @n@ input elements.
468-- * Stops - after consuming @n@ elements.
469-- * Fails - if the stream or the collecting fold ends before it can collect
470-- exactly @n@ elements.
472-- >>> Stream.parse (Parser.takeEQ 4 Fold.toList) $ Stream.fromList [1,0,1]
473-- *** Exception: ParseError "takeEQ: Expecting exactly 4 elements, input terminated on 3"
478takeEQ :: MonadCatch m => Int -> Fold m a b -> Parser m a b
479takeEQ n = D.toParserK . D.takeEQ n
481-- | Take at least @n@ input elements, but can collect more.
483-- * Stops - when the collecting fold stops.
484-- * Fails - if the stream or the collecting fold ends before producing @n@
487-- >>> Stream.parse (Parser.takeGE 4 Fold.toList) $ Stream.fromList [1,0,1]
488-- *** Exception: ParseError "takeGE: Expecting at least 4 elements, input terminated on 3"
490-- >>> Stream.parse (Parser.takeGE 4 Fold.toList) $ Stream.fromList [1,0,1,0,1]
496takeGE :: MonadCatch m => Int -> Fold m a b -> Parser m a b
497takeGE n = D.toParserK . D.takeGE n
500-- Note: This is called @takeWhileP@ and @munch@ in some parser libraries.
502-- | Like 'takeWhile' but uses a 'Parser' instead of a 'Fold' to collect the
503-- input. The combinator stops when the condition fails or if the collecting
506-- This is a generalized version of takeWhile, for example 'takeWhile1' can be
507-- implemented in terms of this:
510-- takeWhile1 cond p = takeWhile cond (takeBetween 1 maxBound p)
513-- Stops: when the condition fails or the collecting parser stops.
514-- Fails: when the collecting parser fails.
518{-# INLINE takeWhileP #-}
519takeWhileP :: -- MonadCatch m =>
520 (a -> Bool) -> Parser m a b -> Parser m a b
521takeWhileP _cond = undefined -- D.toParserK . D.takeWhileP cond
523-- | Collect stream elements until an element fails the predicate. The element
524-- on which the predicate fails is returned back to the input stream.
526-- * Stops - when the predicate fails or the collecting fold stops.
529-- >>> Stream.parse (Parser.takeWhile (== 0) Fold.toList) $ Stream.fromList [0,0,1,0,1]
532-- We can implement a @breakOn@ using 'takeWhile':
535-- breakOn p = takeWhile (not p)
540{-# INLINE takeWhile #-}
541takeWhile :: MonadCatch m => (a -> Bool) -> Fold m a b -> Parser m a b
542takeWhile cond = D.toParserK . D.takeWhile cond
544-- | Like 'takeWhile' but takes at least one element otherwise fails.
548{-# INLINE takeWhile1 #-}
549takeWhile1 :: MonadCatch m => (a -> Bool) -> Fold m a b -> Parser m a b
550takeWhile1 cond = D.toParserK . D.takeWhile1 cond
552-- | Drain the input as long as the predicate succeeds, running the effects and
553-- discarding the results.
555-- This is also called @skipWhile@ in some parsing libraries.
559{-# INLINE drainWhile #-}
560drainWhile :: MonadCatch m => (a -> Bool) -> Parser m a ()
561drainWhile p = takeWhile p FL.drain
563-- | @sliceSepByP cond parser@ parses a slice of the input using @parser@ until
564-- @cond@ succeeds or the parser stops.
566-- This is a generalized slicing parser which can be used to implement other
570-- sliceSepByMax cond n p = sliceSepByP cond (take n p)
571-- sliceSepByBetween cond m n p = sliceSepByP cond (takeBetween m n p)
576{-# INLINE sliceSepByP #-}
579 (a -> Bool) -> Parser m a b -> Parser m a b
580sliceSepByP cond = D.toParserK . D.sliceSepByP cond . D.fromParserK
582-- | Like 'sliceSepBy' but does not drop the separator element, instead
583-- separator is emitted as a separate element in the output.
586{-# INLINE sliceSepWith #-}
587sliceSepWith :: -- MonadCatch m =>
588 (a -> Bool) -> Fold m a b -> Parser m a b
589sliceSepWith _cond = undefined -- D.toParserK . D.sliceSepBy cond
591-- | Collect stream elements until an elements passes the predicate, return the
592-- last element on which the predicate succeeded back to the input stream. If
593-- the predicate succeeds on the first element itself then the parser does not
594-- terminate there. The succeeding element in the leading position
595-- is treated as a prefix separator which is kept in the output segment.
597-- * Stops - when the predicate succeeds in non-leading position.
600-- S.splitWithPrefix pred f = S.parseMany (PR.sliceBeginWith pred f)
605-- sliceBeginWithOdd ls = Stream.parse prsr (Stream.fromList ls)
606-- where prsr = Parser.sliceBeginWith odd Fold.toList
610-- >>> sliceBeginWithOdd [2, 4, 6, 3]
611-- *** Exception: sliceBeginWith : slice begins with an element which fails the predicate
614-- >>> sliceBeginWithOdd [3, 5, 7, 4]
617-- >>> sliceBeginWithOdd [3, 4, 6, 8, 5]
620-- >>> sliceBeginWithOdd []
625{-# INLINE sliceBeginWith #-}
628 (a -> Bool) -> Fold m a b -> Parser m a b
629sliceBeginWith cond = D.toParserK . D.sliceBeginWith cond
631-- | Like 'sliceSepBy' but the separator elements can be escaped using an
632-- escape char determined by the second predicate.
635{-# INLINE escapedSliceSepBy #-}
636escapedSliceSepBy :: -- MonadCatch m =>
637 (a -> Bool) -> (a -> Bool) -> Fold m a b -> Parser m a b
638escapedSliceSepBy _cond _esc = undefined
639 -- D.toParserK . D.escapedSliceSepBy cond esc
641-- | @escapedFrameBy begin end escape@ parses a string framed using @begin@ and
642-- @end@ as the frame begin and end marker elements and @escape@ as an escaping
643-- element to escape the occurrence of the framing elements within the frame.
644-- Nested frames are allowed, but nesting is removed when parsing.
649-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello}"
652-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello {world}}"
655-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello \\{world\\}}"
658-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello {world}"
659-- ParseError "Unterminated '{'"
664{-# INLINE escapedFrameBy #-}
665escapedFrameBy :: -- MonadCatch m =>
666 (a -> Bool) -> (a -> Bool) -> (a -> Bool) -> Fold m a b -> Parser m a b
667escapedFrameBy _begin _end _escape _p = undefined
668 -- D.toParserK . D.frameBy begin end escape p
670-- | Like 'splitOn' but strips leading, trailing, and repeated separators.
671-- Therefore, @".a..b."@ having '.' as the separator would be parsed as
672-- @["a","b"]@. In other words, its like parsing words from whitespace
675-- * Stops - when it finds a word separator after a non-word element
679-- S.wordsBy pred f = S.parseMany (PR.wordBy pred f)
683wordBy :: MonadCatch m => (a -> Bool) -> Fold m a b -> Parser m a b
684wordBy f = D.toParserK . D.wordBy f
686-- | Given an input stream @[a,b,c,...]@ and a comparison function @cmp@, the
687-- parser assigns the element @a@ to the first group, then if @a \`cmp` b@ is
688-- 'True' @b@ is also assigned to the same group. If @a \`cmp` c@ is 'True'
689-- then @c@ is also assigned to the same group and so on. When the comparison
690-- fails the parser is terminated. Each group is folded using the 'Fold' @f@ and
691-- the result of the fold is the result of the parser.
693-- * Stops - when the comparison fails.
699-- . Stream.parseMany (Parser.groupBy eq Fold.toList)
703-- >>> runGroupsBy (<) []
706-- >>> runGroupsBy (<) [1]
709-- >>> runGroupsBy (<) [3, 5, 4, 1, 2, 0]
710-- [[3,5,4],[1,2],[0]]
714{-# INLINE groupBy #-}
715groupBy :: MonadCatch m => (a -> a -> Bool) -> Fold m a b -> Parser m a b
716groupBy eq = D.toParserK . D.groupBy eq
718-- | Unlike 'groupBy' this combinator performs a rolling comparison of two
719-- successive elements in the input stream. Assuming the input stream
720-- is @[a,b,c,...]@ and the comparison function is @cmp@, the parser
721-- first assigns the element @a@ to the first group, then if @a \`cmp` b@ is
722-- 'True' @b@ is also assigned to the same group. If @b \`cmp` c@ is 'True'
723-- then @c@ is also assigned to the same group and so on. When the comparison
724-- fails the parser is terminated. Each group is folded using the 'Fold' @f@ and
725-- the result of the fold is the result of the parser.
727-- * Stops - when the comparison fails.
731-- runGroupsByRolling eq =
733-- . Stream.parseMany (Parser.groupByRolling eq Fold.toList)
737-- >>> runGroupsByRolling (<) []
740-- >>> runGroupsByRolling (<) [1]
743-- >>> runGroupsByRolling (<) [3, 5, 4, 1, 2, 0]
744-- [[3,5],[4],[1,2],[0]]
748{-# INLINE groupByRolling #-}
749groupByRolling :: MonadCatch m => (a -> a -> Bool) -> Fold m a b -> Parser m a b
750groupByRolling eq = D.toParserK . D.groupByRolling eq
752-- | Like 'groupByRolling', but if the predicate is 'True' then collects using
753-- the first fold as long as the predicate holds 'True', if the predicate is
754-- 'False' collects using the second fold as long as it remains 'False'.
755-- Returns 'Left' for the first case and 'Right' for the second case.
757-- For example, if we want to detect sorted sequences in a stream, both
758-- ascending and descending cases we can use 'groupByRollingEither (<=)
759-- Fold.toList Fold.toList'.
762{-# INLINE groupByRollingEither #-}
763groupByRollingEither :: MonadCatch m =>
764 (a -> a -> Bool) -> Fold m a b -> Fold m a c -> Parser m a (Either b c)
765groupByRollingEither eq f1 = D.toParserK . D.groupByRollingEither eq f1
767-- | Match the given sequence of elements using the given comparison function.
769-- >>> Stream.parse (Parser.eqBy (==) "string") $ Stream.fromList "string"
771-- >>> Stream.parse (Parser.eqBy (==) "mismatch") $ Stream.fromList "match"
772-- *** Exception: ParseError "eqBy: failed, yet to match 7 elements"
777eqBy :: MonadCatch m => (a -> a -> Bool) -> [a] -> Parser m a ()
778eqBy cmp = D.toParserK . D.eqBy cmp
780-------------------------------------------------------------------------------
782-------------------------------------------------------------------------------
784-- | Sequential parser application. Apply two parsers sequentially to an input
785-- stream. The input is provided to the first parser, when it is done the
786-- remaining input is provided to the second parser. If both the parsers
787-- succeed their outputs are combined using the supplied function. The
788-- operation fails if any of the parsers fail.
790-- Note: This is a parsing dual of appending streams using
791-- 'Streamly.Prelude.serial', it splits the streams using two parsers and zips
794-- This implementation is strict in the second argument, therefore, the
795-- following will fail:
797-- >>> Stream.parse (Parser.serialWith const (Parser.satisfy (> 0)) undefined) $ Stream.fromList [1]
798-- *** Exception: Prelude.undefined
801-- Compare with 'Applicative' instance method '<*>'. This implementation allows
802-- stream fusion but has quadratic complexity. This can fuse with other
803-- operations and can be faster than 'Applicative' instance for small number
804-- (less than 8) of compositions.
806-- Many combinators can be expressed using @serialWith@ and other parser
807-- primitives. Some common idioms are described below,
810-- span :: (a -> Bool) -> Fold m a b -> Fold m a b -> Parser m a b
811-- span pred f1 f2 = serialWith (,) ('takeWhile' pred f1) ('fromFold' f2)
815-- spanBy :: (a -> a -> Bool) -> Fold m a b -> Fold m a b -> Parser m a b
816-- spanBy eq f1 f2 = serialWith (,) ('groupBy' eq f1) ('fromFold' f2)
820-- spanByRolling :: (a -> a -> Bool) -> Fold m a b -> Fold m a b -> Parser m a b
821-- spanByRolling eq f1 f2 = serialWith (,) ('groupByRolling' eq f1) ('fromFold' f2)
826{-# INLINE serialWith #-}
827serialWith :: MonadCatch m
828 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
830 D.toParserK $ D.serialWith f (D.fromParserK p1) (D.fromParserK p2)
832-- | Sequential parser application ignoring the output of the first parser.
833-- Apply two parsers sequentially to an input stream. The input is provided to
834-- the first parser, when it is done the remaining input is provided to the
835-- second parser. The output of the parser is the output of the second parser.
836-- The operation fails if any of the parsers fail.
838-- This implementation is strict in the second argument, therefore, the
839-- following will fail:
841-- >>> Stream.parse (Parser.split_ (Parser.satisfy (> 0)) undefined) $ Stream.fromList [1]
842-- *** Exception: Prelude.undefined
845-- Compare with 'Applicative' instance method '*>'. This implementation allows
846-- stream fusion but has quadratic complexity. This can fuse with other
847-- operations, and can be faster than 'Applicative' instance for small
848-- number (less than 8) of compositions.
853split_ :: MonadCatch m => Parser m x a -> Parser m x b -> Parser m x b
854split_ p1 p2 = D.toParserK $ D.split_ (D.fromParserK p1) (D.fromParserK p2)
856-- | @teeWith f p1 p2@ distributes its input to both @p1@ and @p2@ until both
857-- of them succeed or anyone of them fails and combines their output using @f@.
858-- The parser succeeds if both the parsers succeed.
862{-# INLINE teeWith #-}
863teeWith :: MonadCatch m
864 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
866 D.toParserK $ D.teeWith f (D.fromParserK p1) (D.fromParserK p2)
868-- | Like 'teeWith' but ends parsing and zips the results, if available,
869-- whenever the first parser ends.
873{-# INLINE teeWithFst #-}
874teeWithFst :: MonadCatch m
875 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
877 D.toParserK $ D.teeWithFst f (D.fromParserK p1) (D.fromParserK p2)
879-- | Like 'teeWith' but ends parsing and zips the results, if available,
880-- whenever any of the parsers ends or fails.
884{-# INLINE teeWithMin #-}
885teeWithMin :: MonadCatch m
886 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
888 D.toParserK $ D.teeWithMin f (D.fromParserK p1) (D.fromParserK p2)
890-- | Sequential alternative. Apply the input to the first parser and return the
891-- result if the parser succeeds. If the first parser fails then backtrack and
892-- apply the same input to the second parser and return the result.
894-- Note: This implementation is not lazy in the second argument. The following
897-- >>> Stream.parse (Parser.satisfy (> 0) `Parser.alt` undefined) $ Stream.fromList [1..10]
900-- Compare with 'Alternative' instance method '<|>'. This implementation allows
901-- stream fusion but has quadratic complexity. This can fuse with other
902-- operations and can be much faster than 'Alternative' instance for small
903-- number (less than 8) of alternatives.
908alt :: MonadCatch m => Parser m x a -> Parser m x a -> Parser m x a
909alt p1 p2 = D.toParserK $ D.alt (D.fromParserK p1) (D.fromParserK p2)
911-- | Shortest alternative. Apply both parsers in parallel but choose the result
912-- from the one which consumed least input i.e. take the shortest succeeding
917{-# INLINE shortest #-}
918shortest :: MonadCatch m
919 => Parser m x a -> Parser m x a -> Parser m x a
920shortest p1 p2 = D.toParserK $ D.shortest (D.fromParserK p1) (D.fromParserK p2)
922-- | Longest alternative. Apply both parsers in parallel but choose the result
923-- from the one which consumed more input i.e. take the longest succeeding
928{-# INLINE longest #-}
929longest :: MonadCatch m
930 => Parser m x a -> Parser m x a -> Parser m x a
931longest p1 p2 = D.toParserK $ D.longest (D.fromParserK p1) (D.fromParserK p2)
933-- | Run a parser without consuming the input.
937{-# INLINE lookAhead #-}
938lookAhead :: MonadCatch m => Parser m a b -> Parser m a b
939lookAhead p = D.toParserK $ D.lookAhead $ D.fromParserK p
941-- | Takes at-most @n@ input elements.
943-- * Stops - when the collecting parser stops.
944-- * Fails - when the collecting parser fails.
946-- >>> Stream.parse (Parser.takeP 4 (Parser.takeEQ 2 Fold.toList)) $ Stream.fromList [1, 2, 3, 4, 5]
949-- >>> Stream.parse (Parser.takeP 4 (Parser.takeEQ 5 Fold.toList)) $ Stream.fromList [1, 2, 3, 4, 5]
950-- *** Exception: ParseError "takeEQ: Expecting exactly 5 elements, input terminated on 4"
954takeP :: MonadCatch m => Int -> Parser m a b -> Parser m a b
955takeP i p = D.toParserK $ D.takeP i $ D.fromParserK p
957-------------------------------------------------------------------------------
959-------------------------------------------------------------------------------
961-- To deinterleave we can chain two parsers one behind the other. The input is
962-- given to the first parser and the input definitively rejected by the first
963-- parser is given to the second parser.
965-- We can either have the parsers themselves buffer the input or use the shared
966-- global buffer to hold it until none of the parsers need it. When the first
967-- parser returns Skip (i.e. rewind) we let the second parser consume the
968-- rejected input and when it is done we move the cursor forward to the first
969-- parser again. This will require a "move forward" command as well.
971-- To implement grep we can use three parsers, one to find the pattern, one
972-- to store the context behind the pattern and one to store the context in
973-- front of the pattern. When a match occurs we need to emit the accumulator of
974-- all the three parsers. One parser can count the line numbers to provide the
977-- | Apply two parsers alternately to an input stream. The input stream is
978-- considered an interleaving of two patterns. The two parsers represent the
981-- This undoes a "gintercalate" of two streams.
985{-# INLINE deintercalate #-}
988 Fold m a y -> Parser m x a
989 -> Fold m b z -> Parser m x b
991deintercalate = undefined
993-------------------------------------------------------------------------------
994-- Sequential Collection
995-------------------------------------------------------------------------------
997-- | @concatSequence f t@ collects sequential parses of parsers in the
998-- container @t@ using the fold @f@. Fails if the input ends or any of the
1001-- This is same as 'Data.Traversable.sequence' but more efficient.
1005{-# INLINE concatSequence #-}
1008 Fold m b c -> t (Parser m a b) -> Parser m a c
1009concatSequence _f _p = undefined
1011-- | Map a 'Parser' returning function on the result of a 'Parser'.
1013-- Compare with 'Monad' instance method '>>='. This implementation allows
1014-- stream fusion but has quadratic complexity. This can fuse with other
1015-- operations and can be much faster than 'Monad' instance for small number
1016-- (less than 8) of compositions.
1020{-# INLINE concatMap #-}
1021concatMap :: MonadCatch m
1022 => (b -> Parser m a c) -> Parser m a b -> Parser m a c
1023concatMap f p = D.toParserK $ D.concatMap (D.fromParserK . f) (D.fromParserK p)
1025-------------------------------------------------------------------------------
1026-- Alternative Collection
1027-------------------------------------------------------------------------------
1029-- | @choice parsers@ applies the @parsers@ in order and returns the first
1032-- This is same as 'asum' but more efficient.
1036{-# INLINE choice #-}
1038 (Functor t, Foldable t, MonadCatch m) => t (Parser m a b) -> Parser m a b
1039choice ps = D.toParserK $ D.choice $ D.fromParserK <$> ps
1041-------------------------------------------------------------------------------
1042-- Sequential Repetition
1043-------------------------------------------------------------------------------
1046-- TODO "many" is essentially a Fold because it cannot fail. So it can be
1047-- downgraded to a Fold. Or we can make the return type a Fold instead and
1048-- upgrade that to a parser when needed.
1050-- | Like 'many' but uses a 'Parser' instead of a 'Fold' to collect the
1051-- results. Parsing stops or fails if the collecting parser stops or fails.
1056manyP :: -- MonadCatch m =>
1057 Parser m a b -> Parser m b c -> Parser m a c
1058manyP _p _f = undefined -- D.toParserK $ D.manyP (D.fromParserK p) f
1060-- | Collect zero or more parses. Apply the supplied parser repeatedly on the
1061-- input stream and push the parse results to a downstream fold.
1063-- Stops: when the downstream fold stops or the parser fails.
1064-- Fails: never, produces zero or more results.
1066-- Compare with 'Control.Applicative.many'.
1071many :: MonadCatch m => Parser m a b -> Fold m b c -> Parser m a c
1072many p f = D.toParserK $ D.many (D.fromParserK p) f
1073-- many = countBetween 0 maxBound
1075-- Note: many1 would perhaps be a better name for this and consistent with
1076-- other names like takeWhile1. But we retain the name "some" for
1079-- | Collect one or more parses. Apply the supplied parser repeatedly on the
1080-- input stream and push the parse results to a downstream fold.
1082-- Stops: when the downstream fold stops or the parser fails.
1083-- Fails: if it stops without producing a single result.
1085-- @some fld parser = manyP (takeGE 1 fld) parser@
1087-- Compare with 'Control.Applicative.some'.
1092some :: MonadCatch m => Parser m a b -> Fold m b c -> Parser m a c
1093some p f = D.toParserK $ D.some (D.fromParserK p) f
1094-- some p f = manyP p (takeGE 1 f)
1095-- many = countBetween 1 maxBound
1097-- | @countBetween m n f p@ collects between @m@ and @n@ sequential parses of
1098-- parser @p@ using the fold @f@. Stop after collecting @n@ results. Fails if
1099-- the input ends or the parser fails before @m@ results are collected.
1103{-# INLINE countBetween #-}
1106 Int -> Int -> Parser m a b -> Fold m b c -> Parser m a c
1107countBetween _m _n _p = undefined
1108-- countBetween m n p f = manyP (takeBetween m n f) p
1110-- | @count n f p@ collects exactly @n@ sequential parses of parser @p@ using
1111-- the fold @f@. Fails if the input ends or the parser fails before @n@
1112-- results are collected.
1119 Int -> Parser m a b -> Fold m b c -> Parser m a c
1120count n = countBetween n n
1121-- count n p f = manyP (takeEQ n f) p
1123-- | Like 'manyTill' but uses a 'Parser' to collect the results instead of a
1124-- 'Fold'. Parsing stops or fails if the collecting parser stops or fails.
1126-- We can implemnent parsers like the following using 'manyTillP':
1129-- countBetweenTill m n f p = manyTillP (takeBetween m n f) p
1134{-# INLINE manyTillP #-}
1135manyTillP :: -- MonadCatch m =>
1136 Parser m a b -> Parser m a x -> Parser m b c -> Parser m a c
1137manyTillP _p1 _p2 _f = undefined
1138 -- D.toParserK $ D.manyTillP (D.fromParserK p1) (D.fromParserK p2) f
1140-- | @manyTill f collect test@ tries the parser @test@ on the input, if @test@
1141-- fails it backtracks and tries @collect@, after @collect@ succeeds @test@ is
1142-- tried again and so on. The parser stops when @test@ succeeds. The output of
1143-- @test@ is discarded and the output of @collect@ is accumulated by the
1144-- supplied fold. The parser fails if @collect@ fails.
1146-- Stops when the fold @f@ stops.
1150{-# INLINE manyTill #-}
1151manyTill :: MonadCatch m
1152 => Parser m a b -> Parser m a x -> Fold m b c -> Parser m a c
1154 D.toParserK $ D.manyTill f (D.fromParserK p1) (D.fromParserK p2)
1156-- | @manyThen f collect recover@ repeats the parser @collect@ on the input and
1157-- collects the output in the supplied fold. If the the parser @collect@ fails,
1158-- parser @recover@ is run until it stops and then we start repeating the
1159-- parser @collect@ again. The parser fails if the recovery parser fails.
1161-- For example, this can be used to find a key frame in a video stream after an
1166{-# INLINE manyThen #-}
1167manyThen :: -- (Foldable t, MonadCatch m) =>
1168 Parser m a b -> Parser m a x -> Fold m b c -> Parser m a c
1169manyThen _parser _recover _f = undefined
1171-------------------------------------------------------------------------------
1172-- Interleaving a collection of parsers
1173-------------------------------------------------------------------------------
1175-- | Apply a collection of parsers to an input stream in a round robin fashion.
1176-- Each parser is applied until it stops and then we repeat starting with the
1177-- the first parser again.
1181{-# INLINE roundRobin #-}
1182roundRobin :: -- (Foldable t, MonadCatch m) =>
1183 t (Parser m a b) -> Fold m b c -> Parser m a c
1184roundRobin _ps _f = undefined
1186-------------------------------------------------------------------------------
1187-- Repeated Alternatives
1188-------------------------------------------------------------------------------
1190-- | Keep trying a parser up to a maximum of @n@ failures. When the parser
1191-- fails the input consumed till now is dropped and the new instance is tried
1192-- on the fresh input.
1196{-# INLINE retryMaxTotal #-}
1197retryMaxTotal :: -- (MonadCatch m) =>
1198 Int -> Parser m a b -> Fold m b c -> Parser m a c
1199retryMaxTotal _n _p _f = undefined
1201-- | Like 'retryMaxTotal' but aborts after @n@ successive failures.
1205{-# INLINE retryMaxSuccessive #-}
1206retryMaxSuccessive :: -- (MonadCatch m) =>
1207 Int -> Parser m a b -> Fold m b c -> Parser m a c
1208retryMaxSuccessive _n _p _f = undefined
1210-- | Keep trying a parser until it succeeds. When the parser fails the input
1211-- consumed till now is dropped and the new instance is tried on the fresh
1217retry :: -- (MonadCatch m) =>
1218 Parser m a b -> Parser m a b
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