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
75 -- | Parsers chained in series, if one parser terminates the composition
78 -- | Grab a sequence of input elements without inspecting them
80 -- , take -- takeBetween 0 n
81 , takeEQ -- takeBetween n n
82 , takeGE -- takeBetween n maxBound
84 -- Grab a sequence of input elements by inspecting them
101 , groupByRollingEither
106 -- , prefixOf -- match any prefix of a given string
107 -- , suffixOf -- match any suffix of a given string
108 -- , infixOf -- match any substring of a given string
111 -- Second order parsers (parsers using parsers)
112 -- * Binary Combinators
114 -- ** Sequential Applicative
118 -- ** Parallel Applicatives
122 -- , teeTill -- like manyTill but parallel
124 -- ** Sequential Interleaving
125 -- Use two folds, run a primary parser, its rejected values go to the
129 -- ** Sequential Alternative
132 -- ** Parallel Alternatives
137 -- * N-ary Combinators
138 -- ** Sequential Collection
142 -- ** Sequential Repetition
154 -- | TODO: traditional implmentations of these may be of limited use. For
155 -- example, consider parsing lines separated by @\\r\\n@. The main parser
156 -- will have to detect and exclude the sequence @\\r\\n@ anyway so that we
157 -- can apply the "sep" parser.
159 -- We can instead implement these as special cases of deintercalate.
172 -- | A simple and stupid impl would be to just convert the stream to an
173 -- array and give the array reference to all consumers. The array can be
174 -- grown on demand by any consumer and truncated when nonbody needs it.
176 -- ** Distribute to collection
177 -- ** Distribute to repetition
179 -- ** Interleaved collection
186 -- ** Collection of Alternatives
192 -- , fastestN -- first N successful in time
193 -- , choiceN -- first N successful in position
195 , choice -- first successful in position
197 -- ** Repeated Alternatives
204import Control.Monad.Catch (MonadCatch, MonadThrow)
206 hiding (any, all, take, takeWhile, sequence, concatMap, maybe, either)
208import Streamly.Internal.Data.Fold.Type (Fold(..))
209import Streamly.Internal.Data.Parser.ParserK.Type (Parser)
211import qualified Streamly.Internal.Data.Fold.Type as FL
212import qualified Streamly.Internal.Data.Parser.ParserD as D
213import qualified Streamly.Internal.Data.Parser.ParserK.Type as K
218-- >>> import Prelude hiding (any, all, take, takeWhile, sequence, concatMap, maybe, either)
219-- >>> import qualified Streamly.Prelude as Stream
220-- >>> import qualified Streamly.Internal.Data.Stream.IsStream as Stream (parse, parseMany)
221-- >>> import qualified Streamly.Data.Fold as Fold
222-- >>> import qualified Streamly.Internal.Data.Parser as Parser
224-------------------------------------------------------------------------------
225-- Downgrade a parser to a Fold
226-------------------------------------------------------------------------------
228-- | Make a 'Fold' from a 'Parser'. The fold just throws an exception if the
229-- parser fails or tries to backtrack.
231-- This can be useful in combinators that accept a Fold and we know that a
232-- Parser cannot fail or failure exception is acceptable as there is no way to
238toFold :: MonadThrow m => Parser m a b -> Fold m a b
239toFold p = D.toFold $ K.fromParserK p
241-------------------------------------------------------------------------------
242-- Upgrade folds to parses
243-------------------------------------------------------------------------------
245-- | Make a 'Parser' from a 'Fold'.
249{-# INLINE fromFold #-}
250fromFold :: MonadCatch m => Fold m a b -> Parser m a b
251fromFold = K.toParserK . D.fromFold
253-------------------------------------------------------------------------------
254-- Terminating but not failing folds
255-------------------------------------------------------------------------------
257-- This is the dual of stream "fromPure".
259-- | A parser that always yields a pure value without consuming any input.
263{-# INLINE [3] fromPure #-}
264fromPure :: MonadCatch m => b -> Parser m a b
265fromPure = K.toParserK . D.fromPure
266{-# RULES "fromPure fallback to CPS" [2]
267 forall a. K.toParserK (D.fromPure a) = K.fromPure a #-}
269-- This is the dual of stream "fromEffect".
271-- | A parser that always yields the result of an effectful action without
272-- consuming any input.
276{-# INLINE fromEffect #-}
277fromEffect :: MonadCatch m => m b -> Parser m a b
278fromEffect = K.fromEffect -- K.toParserK . D.fromEffect
280-- This is the dual of "nil".
282-- | A parser that always fails with an error message without consuming
287{-# INLINE [3] die #-}
288die :: MonadCatch m => String -> Parser m a b
289die = K.toParserK . D.die
290{-# RULES "die fallback to CPS" [2]
291 forall a. K.toParserK (D.die a) = K.die a #-}
293-- This is the dual of "nilM".
295-- | A parser that always fails with an effectful error message and without
296-- consuming any input.
301dieM :: MonadCatch m => m String -> Parser m a b
302dieM = K.toParserK . D.dieM
304-------------------------------------------------------------------------------
306-------------------------------------------------------------------------------
308-- | Peek the head element of a stream, without consuming it. Fails if it
309-- encounters end of input.
311-- >>> Stream.parse ((,) <$> Parser.peek <*> Parser.satisfy (> 0)) $ Stream.fromList [1]
315-- peek = lookAhead (satisfy True)
321peek :: MonadCatch m => Parser m a a
322peek = K.toParserK D.peek
324-- | Succeeds if we are at the end of input, fails otherwise.
326-- >>> Stream.parse ((,) <$> Parser.satisfy (> 0) <*> Parser.eof) $ Stream.fromList [1]
332eof :: MonadCatch m => Parser m a ()
333eof = K.toParserK D.eof
335-- | Returns the next element if it passes the predicate, fails otherwise.
337-- >>> Stream.parse (Parser.satisfy (== 1)) $ Stream.fromList [1,0,1]
342{-# INLINE satisfy #-}
343satisfy :: MonadCatch m => (a -> Bool) -> Parser m a a
344satisfy = K.toParserK . D.satisfy
346-- | Return the next element of the input. Returns 'Nothing'
347-- on end of input. Also known as 'head'.
352next :: MonadCatch m => Parser m a (Maybe a)
353next = K.toParserK D.next
355-- | Map a 'Maybe' returning function on the next element in the stream. The
356-- parser fails if the function returns 'Nothing' otherwise returns the 'Just'
362maybe :: MonadCatch m => (a -> Maybe b) -> Parser m a b
363maybe = K.toParserK . D.maybe
365-- | Map an 'Either' returning function on the next element in the stream. If
366-- the function returns 'Left err', the parser fails with the error message
367-- @err@ otherwise returns the 'Right' value.
372either :: MonadCatch m => (a -> Either String b) -> Parser m a b
373either = K.toParserK . D.either
375-------------------------------------------------------------------------------
377-------------------------------------------------------------------------------
379-- | @takeBetween m n@ takes a minimum of @m@ and a maximum of @n@ input
380-- elements and folds them using the supplied fold.
382-- Stops after @n@ elements.
383-- Fails if the stream ends before @m@ elements could be taken.
389-- takeBetween' low high ls = Stream.parse prsr (Stream.fromList ls)
390-- where prsr = Parser.takeBetween low high Fold.toList
395-- >>> takeBetween' 2 4 [1, 2, 3, 4, 5]
398-- >>> takeBetween' 2 4 [1, 2]
401-- >>> takeBetween' 2 4 [1]
402-- *** Exception: ParseError "takeBetween: Expecting alteast 2 elements, got 1"
404-- >>> takeBetween' 0 0 [1, 2]
407-- >>> takeBetween' 0 1 []
410-- @takeBetween@ is the most general take operation, other take operations can
411-- be defined in terms of takeBetween. For example:
414-- take = takeBetween 0 n -- equivalent of take
415-- take1 = takeBetween 1 n -- equivalent of takeLE1
416-- takeEQ = takeBetween n n
417-- takeGE = takeBetween n maxBound
422{-# INLINE takeBetween #-}
423takeBetween :: MonadCatch m =>
424 Int -> Int -> Fold m a b -> Parser m a b
425takeBetween m n = K.toParserK . D.takeBetween m n
427-- | Stops after taking exactly @n@ input elements.
429-- * Stops - after consuming @n@ elements.
430-- * Fails - if the stream or the collecting fold ends before it can collect
431-- exactly @n@ elements.
433-- >>> Stream.parse (Parser.takeEQ 4 Fold.toList) $ Stream.fromList [1,0,1]
434-- *** Exception: ParseError "takeEQ: Expecting exactly 4 elements, input terminated on 3"
439takeEQ :: MonadCatch m => Int -> Fold m a b -> Parser m a b
440takeEQ n = K.toParserK . D.takeEQ n
442-- | Take at least @n@ input elements, but can collect more.
444-- * Stops - when the collecting fold stops.
445-- * Fails - if the stream or the collecting fold ends before producing @n@
448-- >>> Stream.parse (Parser.takeGE 4 Fold.toList) $ Stream.fromList [1,0,1]
449-- *** Exception: ParseError "takeGE: Expecting at least 4 elements, input terminated on 3"
451-- >>> Stream.parse (Parser.takeGE 4 Fold.toList) $ Stream.fromList [1,0,1,0,1]
457takeGE :: MonadCatch m => Int -> Fold m a b -> Parser m a b
458takeGE n = K.toParserK . D.takeGE n
461-- Note: This is called @takeWhileP@ and @munch@ in some parser libraries.
463-- | Like 'takeWhile' but uses a 'Parser' instead of a 'Fold' to collect the
464-- input. The combinator stops when the condition fails or if the collecting
467-- This is a generalized version of takeWhile, for example 'takeWhile1' can be
468-- implemented in terms of this:
471-- takeWhile1 cond p = takeWhile cond (takeBetween 1 maxBound p)
474-- Stops: when the condition fails or the collecting parser stops.
475-- Fails: when the collecting parser fails.
479{-# INLINE takeWhileP #-}
480takeWhileP :: -- MonadCatch m =>
481 (a -> Bool) -> Parser m a b -> Parser m a b
482takeWhileP _cond = undefined -- K.toParserK . D.takeWhileP cond
484-- | Collect stream elements until an element fails the predicate. The element
485-- on which the predicate fails is returned back to the input stream.
487-- * Stops - when the predicate fails or the collecting fold stops.
490-- >>> Stream.parse (Parser.takeWhile (== 0) Fold.toList) $ Stream.fromList [0,0,1,0,1]
493-- We can implement a @breakOn@ using 'takeWhile':
496-- breakOn p = takeWhile (not p)
501{-# INLINE takeWhile #-}
502takeWhile :: MonadCatch m => (a -> Bool) -> Fold m a b -> Parser m a b
503takeWhile cond = K.toParserK . D.takeWhile cond
505-- | Like 'takeWhile' but takes at least one element otherwise fails.
509{-# INLINE takeWhile1 #-}
510takeWhile1 :: MonadCatch m => (a -> Bool) -> Fold m a b -> Parser m a b
511takeWhile1 cond = K.toParserK . D.takeWhile1 cond
513-- | Drain the input as long as the predicate succeeds, running the effects and
514-- discarding the results.
516-- This is also called @skipWhile@ in some parsing libraries.
520{-# INLINE drainWhile #-}
521drainWhile :: MonadCatch m => (a -> Bool) -> Parser m a ()
522drainWhile p = takeWhile p FL.drain
524-- | @sliceSepByP cond parser@ parses a slice of the input using @parser@ until
525-- @cond@ succeeds or the parser stops.
527-- This is a generalized slicing parser which can be used to implement other
531-- sliceSepByMax cond n p = sliceSepByP cond (take n p)
532-- sliceSepByBetween cond m n p = sliceSepByP cond (takeBetween m n p)
537{-# INLINABLE sliceSepByP #-}
540 (a -> Bool) -> Parser m a b -> Parser m a b
541sliceSepByP cond = K.toParserK . D.sliceSepByP cond . K.fromParserK
543-- | Like 'sliceSepBy' but does not drop the separator element, instead
544-- separator is emitted as a separate element in the output.
547{-# INLINABLE sliceSepWith #-}
548sliceSepWith :: -- MonadCatch m =>
549 (a -> Bool) -> Fold m a b -> Parser m a b
550sliceSepWith _cond = undefined -- K.toParserK . D.sliceSepBy cond
552-- | Collect stream elements until an elements passes the predicate, return the
553-- last element on which the predicate succeeded back to the input stream. If
554-- the predicate succeeds on the first element itself then the parser does not
555-- terminate there. The succeeding element in the leading position
556-- is treated as a prefix separator which is kept in the output segment.
558-- * Stops - when the predicate succeeds in non-leading position.
561-- S.splitWithPrefix pred f = S.parseMany (PR.sliceBeginWith pred f)
566-- sliceBeginWithOdd ls = Stream.parse prsr (Stream.fromList ls)
567-- where prsr = Parser.sliceBeginWith odd Fold.toList
571-- >>> sliceBeginWithOdd [2, 4, 6, 3]
572-- *** Exception: sliceBeginWith : slice begins with an element which fails the predicate
575-- >>> sliceBeginWithOdd [3, 5, 7, 4]
578-- >>> sliceBeginWithOdd [3, 4, 6, 8, 5]
581-- >>> sliceBeginWithOdd []
586{-# INLINABLE sliceBeginWith #-}
589 (a -> Bool) -> Fold m a b -> Parser m a b
590sliceBeginWith cond = K.toParserK . D.sliceBeginWith cond
592-- | Like 'sliceSepBy' but the separator elements can be escaped using an
593-- escape char determined by the second predicate.
596{-# INLINABLE escapedSliceSepBy #-}
597escapedSliceSepBy :: -- MonadCatch m =>
598 (a -> Bool) -> (a -> Bool) -> Fold m a b -> Parser m a b
599escapedSliceSepBy _cond _esc = undefined
600 -- K.toParserK . D.escapedSliceSepBy cond esc
602-- | @escapedFrameBy begin end escape@ parses a string framed using @begin@ and
603-- @end@ as the frame begin and end marker elements and @escape@ as an escaping
604-- element to escape the occurrence of the framing elements within the frame.
605-- Nested frames are allowed, but nesting is removed when parsing.
610-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello}"
613-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello {world}}"
616-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello \\{world\\}}"
619-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello {world}"
620-- ParseError "Unterminated '{'"
625{-# INLINABLE escapedFrameBy #-}
626escapedFrameBy :: -- MonadCatch m =>
627 (a -> Bool) -> (a -> Bool) -> (a -> Bool) -> Fold m a b -> Parser m a b
628escapedFrameBy _begin _end _escape _p = undefined
629 -- K.toParserK . D.frameBy begin end escape p
631-- | Like 'splitOn' but strips leading, trailing, and repeated separators.
632-- Therefore, @".a..b."@ having '.' as the separator would be parsed as
633-- @["a","b"]@. In other words, its like parsing words from whitespace
636-- * Stops - when it finds a word separator after a non-word element
640-- S.wordsBy pred f = S.parseMany (PR.wordBy pred f)
644wordBy :: MonadCatch m => (a -> Bool) -> Fold m a b -> Parser m a b
645wordBy f = K.toParserK . D.wordBy f
647-- | Given an input stream @[a,b,c,...]@ and a comparison function @cmp@, the
648-- parser assigns the element @a@ to the first group, then if @a \`cmp` b@ is
649-- 'True' @b@ is also assigned to the same group. If @a \`cmp` c@ is 'True'
650-- then @c@ is also assigned to the same group and so on. When the comparison
651-- fails the parser is terminated. Each group is folded using the 'Fold' @f@ and
652-- the result of the fold is the result of the parser.
654-- * Stops - when the comparison fails.
660-- . Stream.parseMany (Parser.groupBy eq Fold.toList)
664-- >>> runGroupsBy (<) []
667-- >>> runGroupsBy (<) [1]
670-- >>> runGroupsBy (<) [3, 5, 4, 1, 2, 0]
671-- [[3,5,4],[1,2],[0]]
675{-# INLINABLE groupBy #-}
676groupBy :: MonadCatch m => (a -> a -> Bool) -> Fold m a b -> Parser m a b
677groupBy eq = K.toParserK . D.groupBy eq
679-- | Unlike 'groupBy' this combinator performs a rolling comparison of two
680-- successive elements in the input stream. Assuming the input stream to the
681-- parser is @[a,b,c,...]@ and the comparison function is @cmp@, the parser
682-- first assigns the element @a@ to the first group, then if @a \`cmp` b@ is
683-- 'True' @b@ is also assigned to the same group. If @b \`cmp` c@ is 'True'
684-- then @c@ is also assigned to the same group and so on. When the comparison
685-- fails the parser is terminated. Each group is folded using the 'Fold' @f@ and
686-- the result of the fold is the result of the parser.
688-- * Stops - when the comparison fails.
692-- runGroupsByRolling eq =
694-- . Stream.parseMany (Parser.groupByRolling eq Fold.toList)
698-- >>> runGroupsByRolling (<) []
701-- >>> runGroupsByRolling (<) [1]
704-- >>> runGroupsByRolling (<) [3, 5, 4, 1, 2, 0]
705-- [[3,5],[4],[1,2],[0]]
709{-# INLINABLE groupByRolling #-}
710groupByRolling :: MonadCatch m => (a -> a -> Bool) -> Fold m a b -> Parser m a b
711groupByRolling eq = K.toParserK . D.groupByRolling eq
713-- | Like 'groupByRolling', but if the predicate is 'True' then collects using
714-- the first fold as long as the predicate holds 'True', if the predicate is
715-- 'False' collects using the second fold as long as it remains 'False'.
716-- Returns 'Left' for the first case and 'Right' for the second case.
718-- For example, if we want to detect sorted sequences in a stream, both
719-- ascending and descending cases we can use 'groupByRollingEither (<=)
720-- Fold.toList Fold.toList'.
723{-# INLINABLE groupByRollingEither #-}
724groupByRollingEither :: MonadCatch m =>
725 (a -> a -> Bool) -> Fold m a b -> Fold m a c -> Parser m a (Either b c)
726groupByRollingEither eq f1 = K.toParserK . D.groupByRollingEither eq f1
728-- | Match the given sequence of elements using the given comparison function.
730-- >>> Stream.parse (Parser.eqBy (==) "string") $ Stream.fromList "string"
732-- >>> Stream.parse (Parser.eqBy (==) "mismatch") $ Stream.fromList "match"
733-- *** Exception: ParseError "eqBy: failed, yet to match 7 elements"
738eqBy :: MonadCatch m => (a -> a -> Bool) -> [a] -> Parser m a ()
739eqBy cmp = K.toParserK . D.eqBy cmp
741-------------------------------------------------------------------------------
743-------------------------------------------------------------------------------
745-- | Sequential parser application. Apply two parsers sequentially to an input
746-- stream. The input is provided to the first parser, when it is done the
747-- remaining input is provided to the second parser. If both the parsers
748-- succeed their outputs are combined using the supplied function. The
749-- operation fails if any of the parsers fail.
751-- Note: This is a parsing dual of appending streams using
752-- 'Streamly.Prelude.serial', it splits the streams using two parsers and zips
755-- This implementation is strict in the second argument, therefore, the
756-- following will fail:
758-- >>> Stream.parse (Parser.serialWith const (Parser.satisfy (> 0)) undefined) $ Stream.fromList [1]
759-- *** Exception: Prelude.undefined
762-- Compare with 'Applicative' instance method '<*>'. This implementation allows
763-- stream fusion but has quadratic complexity. This can fuse with other
764-- operations and can be faster than 'Applicative' instance for small number
765-- (less than 8) of compositions.
767-- Many combinators can be expressed using @serialWith@ and other parser
768-- primitives. Some common idioms are described below,
771-- span :: (a -> Bool) -> Fold m a b -> Fold m a b -> Parser m a b
772-- span pred f1 f2 = serialWith (,) ('takeWhile' pred f1) ('fromFold' f2)
776-- spanBy :: (a -> a -> Bool) -> Fold m a b -> Fold m a b -> Parser m a b
777-- spanBy eq f1 f2 = serialWith (,) ('groupBy' eq f1) ('fromFold' f2)
781-- spanByRolling :: (a -> a -> Bool) -> Fold m a b -> Fold m a b -> Parser m a b
782-- spanByRolling eq f1 f2 = serialWith (,) ('groupByRolling' eq f1) ('fromFold' f2)
787{-# INLINE serialWith #-}
788serialWith :: MonadCatch m
789 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
791 K.toParserK $ D.serialWith f (K.fromParserK p1) (K.fromParserK p2)
793-- | Sequential parser application ignoring the output of the first parser.
794-- Apply two parsers sequentially to an input stream. The input is provided to
795-- the first parser, when it is done the remaining input is provided to the
796-- second parser. The output of the parser is the output of the second parser.
797-- The operation fails if any of the parsers fail.
799-- This implementation is strict in the second argument, therefore, the
800-- following will fail:
802-- >>> Stream.parse (Parser.split_ (Parser.satisfy (> 0)) undefined) $ Stream.fromList [1]
803-- *** Exception: Prelude.undefined
806-- Compare with 'Applicative' instance method '*>'. This implementation allows
807-- stream fusion but has quadratic complexity. This can fuse with other
808-- operations, and can be faster than 'Applicative' instance for small
809-- number (less than 8) of compositions.
814split_ :: MonadCatch m => Parser m x a -> Parser m x b -> Parser m x b
815split_ p1 p2 = K.toParserK $ D.split_ (K.fromParserK p1) (K.fromParserK p2)
817-- | @teeWith f p1 p2@ distributes its input to both @p1@ and @p2@ until both
818-- of them succeed or anyone of them fails and combines their output using @f@.
819-- The parser succeeds if both the parsers succeed.
823{-# INLINE teeWith #-}
824teeWith :: MonadCatch m
825 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
827 K.toParserK $ D.teeWith f (K.fromParserK p1) (K.fromParserK p2)
829-- | Like 'teeWith' but ends parsing and zips the results, if available,
830-- whenever the first parser ends.
834{-# INLINE teeWithFst #-}
835teeWithFst :: MonadCatch m
836 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
838 K.toParserK $ D.teeWithFst f (K.fromParserK p1) (K.fromParserK p2)
840-- | Like 'teeWith' but ends parsing and zips the results, if available,
841-- whenever any of the parsers ends or fails.
845{-# INLINE teeWithMin #-}
846teeWithMin :: MonadCatch m
847 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
849 K.toParserK $ D.teeWithMin f (K.fromParserK p1) (K.fromParserK p2)
851-- | Sequential alternative. Apply the input to the first parser and return the
852-- result if the parser succeeds. If the first parser fails then backtrack and
853-- apply the same input to the second parser and return the result.
855-- Note: This implementation is not lazy in the second argument. The following
858-- >>> Stream.parse (Parser.satisfy (> 0) `Parser.alt` undefined) $ Stream.fromList [1..10]
861-- Compare with 'Alternative' instance method '<|>'. This implementation allows
862-- stream fusion but has quadratic complexity. This can fuse with other
863-- operations and can be much faster than 'Alternative' instance for small
864-- number (less than 8) of alternatives.
869alt :: MonadCatch m => Parser m x a -> Parser m x a -> Parser m x a
870alt p1 p2 = K.toParserK $ D.alt (K.fromParserK p1) (K.fromParserK p2)
872-- | Shortest alternative. Apply both parsers in parallel but choose the result
873-- from the one which consumed least input i.e. take the shortest succeeding
878{-# INLINE shortest #-}
879shortest :: MonadCatch m
880 => Parser m x a -> Parser m x a -> Parser m x a
881shortest p1 p2 = K.toParserK $ D.shortest (K.fromParserK p1) (K.fromParserK p2)
883-- | Longest alternative. Apply both parsers in parallel but choose the result
884-- from the one which consumed more input i.e. take the longest succeeding
889{-# INLINE longest #-}
890longest :: MonadCatch m
891 => Parser m x a -> Parser m x a -> Parser m x a
892longest p1 p2 = K.toParserK $ D.longest (K.fromParserK p1) (K.fromParserK p2)
894-- | Run a parser without consuming the input.
898{-# INLINE lookAhead #-}
899lookAhead :: MonadCatch m => Parser m a b -> Parser m a b
900lookAhead p = K.toParserK $ D.lookAhead $ K.fromParserK p
902-- | Takes at-most @n@ input elements.
904-- * Stops - when the collecting parser stops.
905-- * Fails - when the collecting parser fails.
907-- >>> Stream.parse (Parser.takeP 4 (Parser.takeEQ 2 Fold.toList)) $ Stream.fromList [1, 2, 3, 4, 5]
910-- >>> Stream.parse (Parser.takeP 4 (Parser.takeEQ 5 Fold.toList)) $ Stream.fromList [1, 2, 3, 4, 5]
911-- *** Exception: ParseError "takeEQ: Expecting exactly 5 elements, input terminated on 4"
915takeP :: MonadCatch m => Int -> Parser m a b -> Parser m a b
916takeP i p = K.toParserK $ D.takeP i $ K.fromParserK p
918-------------------------------------------------------------------------------
920-------------------------------------------------------------------------------
922-- To deinterleave we can chain two parsers one behind the other. The input is
923-- given to the first parser and the input definitively rejected by the first
924-- parser is given to the second parser.
926-- We can either have the parsers themselves buffer the input or use the shared
927-- global buffer to hold it until none of the parsers need it. When the first
928-- parser returns Skip (i.e. rewind) we let the second parser consume the
929-- rejected input and when it is done we move the cursor forward to the first
930-- parser again. This will require a "move forward" command as well.
932-- To implement grep we can use three parsers, one to find the pattern, one
933-- to store the context behind the pattern and one to store the context in
934-- front of the pattern. When a match occurs we need to emit the accumulator of
935-- all the three parsers. One parser can count the line numbers to provide the
938-- | Apply two parsers alternately to an input stream. The input stream is
939-- considered an interleaving of two patterns. The two parsers represent the
942-- This undoes a "gintercalate" of two streams.
946{-# INLINE deintercalate #-}
949 Fold m a y -> Parser m x a
950 -> Fold m b z -> Parser m x b
952deintercalate = undefined
954-------------------------------------------------------------------------------
955-- Sequential Collection
956-------------------------------------------------------------------------------
958-- | @concatSequence f t@ collects sequential parses of parsers in the
959-- container @t@ using the fold @f@. Fails if the input ends or any of the
962-- This is same as 'Data.Traversable.sequence' but more efficient.
966{-# INLINE concatSequence #-}
969 Fold m b c -> t (Parser m a b) -> Parser m a c
970concatSequence _f _p = undefined
972-- | Map a 'Parser' returning function on the result of a 'Parser'.
974-- Compare with 'Monad' instance method '>>='. This implementation allows
975-- stream fusion but has quadratic complexity. This can fuse with other
976-- operations and can be much faster than 'Monad' instance for small number
977-- (less than 8) of compositions.
981{-# INLINE concatMap #-}
982concatMap :: MonadCatch m
983 => (b -> Parser m a c) -> Parser m a b -> Parser m a c
984concatMap f p = K.toParserK $ D.concatMap (K.fromParserK . f) (K.fromParserK p)
986-------------------------------------------------------------------------------
987-- Alternative Collection
988-------------------------------------------------------------------------------
990-- | @choice parsers@ applies the @parsers@ in order and returns the first
993-- This is same as 'asum' but more efficient.
999 (Functor t, Foldable t, MonadCatch m) => t (Parser m a b) -> Parser m a b
1000choice ps = K.toParserK $ D.choice $ K.fromParserK <$> ps
1002-------------------------------------------------------------------------------
1003-- Sequential Repetition
1004-------------------------------------------------------------------------------
1007-- TODO "many" is essentially a Fold because it cannot fail. So it can be
1008-- downgraded to a Fold. Or we can make the return type a Fold instead and
1009-- upgrade that to a parser when needed.
1011-- | Like 'many' but uses a 'Parser' instead of a 'Fold' to collect the
1012-- results. Parsing stops or fails if the collecting parser stops or fails.
1017manyP :: -- MonadCatch m =>
1018 Parser m a b -> Parser m b c -> Parser m a c
1019manyP _p _f = undefined -- K.toParserK $ D.manyP (K.fromParserK p) f
1021-- | Collect zero or more parses. Apply the supplied parser repeatedly on the
1022-- input stream and push the parse results to a downstream fold.
1024-- Stops: when the downstream fold stops or the parser fails.
1025-- Fails: never, produces zero or more results.
1027-- Compare with 'Control.Applicative.many'.
1032many :: MonadCatch m => Parser m a b -> Fold m b c -> Parser m a c
1033many p f = K.toParserK $ D.many (K.fromParserK p) f
1034-- many = countBetween 0 maxBound
1036-- Note: many1 would perhaps be a better name for this and consistent with
1037-- other names like takeWhile1. But we retain the name "some" for
1040-- | Collect one or more parses. Apply the supplied parser repeatedly on the
1041-- input stream and push the parse results to a downstream fold.
1043-- Stops: when the downstream fold stops or the parser fails.
1044-- Fails: if it stops without producing a single result.
1046-- @some fld parser = manyP (takeGE 1 fld) parser@
1048-- Compare with 'Control.Applicative.some'.
1053some :: MonadCatch m => Parser m a b -> Fold m b c -> Parser m a c
1054some p f = K.toParserK $ D.some (K.fromParserK p) f
1055-- some p f = manyP p (takeGE 1 f)
1056-- many = countBetween 1 maxBound
1058-- | @countBetween m n f p@ collects between @m@ and @n@ sequential parses of
1059-- parser @p@ using the fold @f@. Stop after collecting @n@ results. Fails if
1060-- the input ends or the parser fails before @m@ results are collected.
1064{-# INLINE countBetween #-}
1067 Int -> Int -> Parser m a b -> Fold m b c -> Parser m a c
1068countBetween _m _n _p = undefined
1069-- countBetween m n p f = manyP (takeBetween m n f) p
1071-- | @count n f p@ collects exactly @n@ sequential parses of parser @p@ using
1072-- the fold @f@. Fails if the input ends or the parser fails before @n@
1073-- results are collected.
1080 Int -> Parser m a b -> Fold m b c -> Parser m a c
1081count n = countBetween n n
1082-- count n p f = manyP (takeEQ n f) p
1084-- | Like 'manyTill' but uses a 'Parser' to collect the results instead of a
1085-- 'Fold'. Parsing stops or fails if the collecting parser stops or fails.
1087-- We can implemnent parsers like the following using 'manyTillP':
1090-- countBetweenTill m n f p = manyTillP (takeBetween m n f) p
1095{-# INLINE manyTillP #-}
1096manyTillP :: -- MonadCatch m =>
1097 Parser m a b -> Parser m a x -> Parser m b c -> Parser m a c
1098manyTillP _p1 _p2 _f = undefined
1099 -- K.toParserK $ D.manyTillP (K.fromParserK p1) (K.fromParserK p2) f
1101-- | @manyTill f collect test@ tries the parser @test@ on the input, if @test@
1102-- fails it backtracks and tries @collect@, after @collect@ succeeds @test@ is
1103-- tried again and so on. The parser stops when @test@ succeeds. The output of
1104-- @test@ is discarded and the output of @collect@ is accumulated by the
1105-- supplied fold. The parser fails if @collect@ fails.
1107-- Stops when the fold @f@ stops.
1111{-# INLINE manyTill #-}
1112manyTill :: MonadCatch m
1113 => Parser m a b -> Parser m a x -> Fold m b c -> Parser m a c
1115 K.toParserK $ D.manyTill f (K.fromParserK p1) (K.fromParserK p2)
1117-- | @manyThen f collect recover@ repeats the parser @collect@ on the input and
1118-- collects the output in the supplied fold. If the the parser @collect@ fails,
1119-- parser @recover@ is run until it stops and then we start repeating the
1120-- parser @collect@ again. The parser fails if the recovery parser fails.
1122-- For example, this can be used to find a key frame in a video stream after an
1127{-# INLINE manyThen #-}
1128manyThen :: -- (Foldable t, MonadCatch m) =>
1129 Parser m a b -> Parser m a x -> Fold m b c -> Parser m a c
1130manyThen _parser _recover _f = undefined
1132-------------------------------------------------------------------------------
1133-- Interleaving a collection of parsers
1134-------------------------------------------------------------------------------
1136-- | Apply a collection of parsers to an input stream in a round robin fashion.
1137-- Each parser is applied until it stops and then we repeat starting with the
1138-- the first parser again.
1142{-# INLINE roundRobin #-}
1143roundRobin :: -- (Foldable t, MonadCatch m) =>
1144 t (Parser m a b) -> Fold m b c -> Parser m a c
1145roundRobin _ps _f = undefined
1147-------------------------------------------------------------------------------
1148-- Repeated Alternatives
1149-------------------------------------------------------------------------------
1151-- | Keep trying a parser up to a maximum of @n@ failures. When the parser
1152-- fails the input consumed till now is dropped and the new instance is tried
1153-- on the fresh input.
1157{-# INLINE retryMaxTotal #-}
1158retryMaxTotal :: -- (MonadCatch m) =>
1159 Int -> Parser m a b -> Fold m b c -> Parser m a c
1160retryMaxTotal _n _p _f = undefined
1162-- | Like 'retryMaxTotal' but aborts after @n@ successive failures.
1166{-# INLINE retryMaxSuccessive #-}
1167retryMaxSuccessive :: -- (MonadCatch m) =>
1168 Int -> Parser m a b -> Fold m b c -> Parser m a c
1169retryMaxSuccessive _n _p _f = undefined
1171-- | Keep trying a parser until it succeeds. When the parser fails the input
1172-- consumed till now is dropped and the new instance is tried on the fresh
1178retry :: -- (MonadCatch m) =>
1179 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