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
85 -- | Parsers chained in series, if one parser terminates the composition
88 -- | Grab a sequence of input elements without inspecting them
90 -- , take -- takeBetween 0 n
91 , takeEQ -- takeBetween n n
92 , takeGE -- takeBetween n maxBound
95 -- Grab a sequence of input elements by inspecting them
110 -- Quoting and Escaping
114 -- Words and grouping
118 , groupByRollingEither
123 -- , prefixOf -- match any prefix of a given string
124 -- , suffixOf -- match any suffix of a given string
125 -- , infixOf -- match any substring of a given string
128 -- Second order parsers (parsers using parsers)
129 -- * Binary Combinators
131 -- ** Sequential Applicative
135 -- ** Parallel Applicatives
139 -- , teeTill -- like manyTill but parallel
141 -- ** Sequential Interleaving
142 -- Use two folds, run a primary parser, its rejected values go to the
146 -- ** Sequential Alternative
149 -- ** Parallel Alternatives
154 -- * N-ary Combinators
155 -- ** Sequential Collection
159 -- ** Sequential Repetition
171 -- | TODO: traditional implmentations of these may be of limited use. For
172 -- example, consider parsing lines separated by @\\r\\n@. The main parser
173 -- will have to detect and exclude the sequence @\\r\\n@ anyway so that we
174 -- can apply the "sep" parser.
176 -- We can instead implement these as special cases of deintercalate.
190 -- | A simple and stupid impl would be to just convert the stream to an
191 -- array and give the array reference to all consumers. The array can be
192 -- grown on demand by any consumer and truncated when nonbody needs it.
194 -- ** Distribute to collection
195 -- ** Distribute to repetition
197 -- ** Interleaved collection
204 -- ** Collection of Alternatives
210 -- , fastestN -- first N successful in time
211 -- , choiceN -- first N successful in position
213 , choice -- first successful in position
215 -- ** Repeated Alternatives
222import Control.Applicative ((<|>))
223import Control.Monad.Catch (MonadCatch, MonadThrow)
224import Data.Functor (($>))
226 ( any, all, dropWhile, take, takeWhile, sequence, concatMap, maybe, either
229import Streamly.Internal.Data.Fold.Type (Fold(..))
230import Streamly.Internal.Data.Parser.ParserK.Type (Parser)
232import qualified Streamly.Internal.Data.Fold.Type as FL
233import qualified Streamly.Internal.Data.Parser.ParserD as D
234import qualified Streamly.Internal.Data.Parser.ParserK.Type as K
239-- >>> :set -package streamly
240-- >>> import Prelude hiding (any, all, dropWhile, take, takeWhile, sequence, concatMap, maybe, either, filter)
241-- >>> import qualified Streamly.Prelude as Stream
242-- >>> import qualified Streamly.Internal.Data.Stream.IsStream as Stream (parse, parseMany)
243-- >>> import qualified Streamly.Data.Fold as Fold
244-- >>> import qualified Streamly.Internal.Data.Parser as Parser
246-------------------------------------------------------------------------------
247-- Downgrade a parser to a Fold
248-------------------------------------------------------------------------------
250-- | Make a 'Fold' from a 'Parser'. The fold just throws an exception if the
251-- parser fails or tries to backtrack.
253-- This can be useful in combinators that accept a Fold and we know that a
254-- Parser cannot fail or failure exception is acceptable as there is no way to
260toFold :: MonadThrow m => Parser m a b -> Fold m a b
261toFold p = D.toFold $ D.fromParserK p
263-------------------------------------------------------------------------------
264-- Upgrade folds to parses
265-------------------------------------------------------------------------------
267-- | Make a 'Parser' from a 'Fold'.
271{-# INLINE fromFold #-}
272fromFold :: MonadCatch m => Fold m a b -> Parser m a b
273fromFold = D.toParserK . D.fromFold
275-------------------------------------------------------------------------------
276-- Terminating but not failing folds
277-------------------------------------------------------------------------------
279-- This is the dual of stream "fromPure".
281-- | A parser that always yields a pure value without consuming any input.
285{-# INLINE [3] fromPure #-}
286fromPure :: MonadCatch m => b -> Parser m a b
287fromPure = D.toParserK . D.fromPure
288{-# RULES "fromPure fallback to CPS" [2]
289 forall a. D.toParserK (D.fromPure a) = K.fromPure a #-}
291-- This is the dual of stream "fromEffect".
293-- | A parser that always yields the result of an effectful action without
294-- consuming any input.
298{-# INLINE fromEffect #-}
299fromEffect :: MonadCatch m => m b -> Parser m a b
300fromEffect = K.fromEffect -- D.toParserK . D.fromEffect
302-- This is the dual of "nil".
304-- | A parser that always fails with an error message without consuming
309{-# INLINE [3] die #-}
310die :: MonadCatch m => String -> Parser m a b
311die = D.toParserK . D.die
312{-# RULES "die fallback to CPS" [2]
313 forall a. D.toParserK (D.die a) = K.die a #-}
315-- This is the dual of "nilM".
317-- | A parser that always fails with an effectful error message and without
318-- consuming any input.
323dieM :: MonadCatch m => m String -> Parser m a b
324dieM = D.toParserK . D.dieM
326-------------------------------------------------------------------------------
328-------------------------------------------------------------------------------
330-- | @lmap f parser@ maps the function @f@ on the input of the parser.
332-- >>> Stream.parse (Parser.lmap (\x -> x * x) (Parser.fromFold Fold.sum)) (Stream.enumerateFromTo 1 100)
335-- > lmap = Parser.lmapM return
339lmap :: MonadCatch m => (a -> b) -> Parser m b r -> Parser m a r
340lmap f p = D.toParserK $ D.lmap f $ D.fromParserK p
342-- | @lmapM f parser@ maps the monadic function @f@ on the input of the parser.
346lmapM :: MonadCatch m => (a -> m b) -> Parser m b r -> Parser m a r
347lmapM f p = D.toParserK $ D.lmapM f $ D.fromParserK p
349-- | Include only those elements that pass a predicate.
351-- >>> Stream.parse (Parser.filter (> 5) (Parser.fromFold Fold.sum)) $ Stream.fromList [1..10]
356filter :: MonadCatch m => (a -> Bool) -> Parser m a b -> Parser m a b
357filter f p = D.toParserK $ D.filter f $ D.fromParserK p
359-------------------------------------------------------------------------------
361-------------------------------------------------------------------------------
363-- | Peek the head element of a stream, without consuming it. Fails if it
364-- encounters end of input.
366-- >>> Stream.parse ((,) <$> Parser.peek <*> Parser.satisfy (> 0)) $ Stream.fromList [1]
370-- peek = lookAhead (satisfy True)
376peek :: MonadCatch m => Parser m a a
377peek = D.toParserK D.peek
379-- | Succeeds if we are at the end of input, fails otherwise.
381-- >>> Stream.parse ((,) <$> Parser.satisfy (> 0) <*> Parser.eof) $ Stream.fromList [1]
387eof :: MonadCatch m => Parser m a ()
388eof = D.toParserK D.eof
390-- | Returns the next element if it passes the predicate, fails otherwise.
392-- >>> Stream.parse (Parser.satisfy (== 1)) $ Stream.fromList [1,0,1]
397{-# INLINE satisfy #-}
398satisfy :: MonadCatch m => (a -> Bool) -> Parser m a a
399satisfy = D.toParserK . D.satisfy
401-- | Consume one element from the head of the stream. Fails if it encounters
404-- >>> one = Parser.satisfy $ const True
409one :: MonadCatch m => Parser m a a
410one = satisfy $ const True
412-- | Match a specific element.
414-- >>> element x = Parser.satisfy (== x)
416{-# INLINE element #-}
417element :: (MonadCatch m, Eq a) => a -> Parser m a a
418element x = satisfy (== x)
420-- | Match anything other than the supplied element.
422-- >>> except x = Parser.satisfy (/= x)
425except :: (MonadCatch m, Eq a) => a -> Parser m a a
426except x = satisfy (/= x)
428-- | Match any one of the elements in the supplied list.
430-- >>> oneOf xs = Parser.satisfy (`elem` xs)
432-- When performance matters a pattern matching predicate could be more
433-- efficient than a list:
444-- GHC may use a binary search instead of linear search in the list.
445-- Alternatively, you can also use an array instead of list for storage and
449oneOf :: (MonadCatch m, Eq a) => [a] -> Parser m a a
450oneOf xs = satisfy (`elem` xs)
452-- | See performance notes in 'oneOf'.
454-- >>> noneOf xs = Parser.satisfy (`notElem` xs)
457noneOf :: (MonadCatch m, Eq a) => [a] -> Parser m a a
458noneOf xs = satisfy (`notElem` xs)
460-- | Return the next element of the input. Returns 'Nothing'
461-- on end of input. Also known as 'head'.
466next :: MonadCatch m => Parser m a (Maybe a)
467next = D.toParserK D.next
469-- | Map a 'Maybe' returning function on the next element in the stream. The
470-- parser fails if the function returns 'Nothing' otherwise returns the 'Just'
476maybe :: MonadCatch m => (a -> Maybe b) -> Parser m a b
477maybe = D.toParserK . D.maybe
479-- | Map an 'Either' returning function on the next element in the stream. If
480-- the function returns 'Left err', the parser fails with the error message
481-- @err@ otherwise returns the 'Right' value.
486either :: MonadCatch m => (a -> Either String b) -> Parser m a b
487either = D.toParserK . D.either
489-------------------------------------------------------------------------------
491-------------------------------------------------------------------------------
493-- | @takeBetween m n@ takes a minimum of @m@ and a maximum of @n@ input
494-- elements and folds them using the supplied fold.
496-- Stops after @n@ elements.
497-- Fails if the stream ends before @m@ elements could be taken.
503-- takeBetween' low high ls = Stream.parse prsr (Stream.fromList ls)
504-- where prsr = Parser.takeBetween low high Fold.toList
509-- >>> takeBetween' 2 4 [1, 2, 3, 4, 5]
512-- >>> takeBetween' 2 4 [1, 2]
515-- >>> takeBetween' 2 4 [1]
516-- *** Exception: ParseError "takeBetween: Expecting alteast 2 elements, got 1"
518-- >>> takeBetween' 0 0 [1, 2]
521-- >>> takeBetween' 0 1 []
524-- @takeBetween@ is the most general take operation, other take operations can
525-- be defined in terms of takeBetween. For example:
528-- take = takeBetween 0 n -- equivalent of take
529-- take1 = takeBetween 1 n -- equivalent of takeLE1
530-- takeEQ = takeBetween n n
531-- takeGE = takeBetween n maxBound
536{-# INLINE takeBetween #-}
537takeBetween :: MonadCatch m =>
538 Int -> Int -> Fold m a b -> Parser m a b
539takeBetween m n = D.toParserK . D.takeBetween m n
541-- | Stops after taking exactly @n@ input elements.
543-- * Stops - after consuming @n@ elements.
544-- * Fails - if the stream or the collecting fold ends before it can collect
545-- exactly @n@ elements.
547-- >>> Stream.parse (Parser.takeEQ 4 Fold.toList) $ Stream.fromList [1,0,1]
548-- *** Exception: ParseError "takeEQ: Expecting exactly 4 elements, input terminated on 3"
553takeEQ :: MonadCatch m => Int -> Fold m a b -> Parser m a b
554takeEQ n = D.toParserK . D.takeEQ n
556-- | Take at least @n@ input elements, but can collect more.
558-- * Stops - when the collecting fold stops.
559-- * Fails - if the stream or the collecting fold ends before producing @n@
562-- >>> Stream.parse (Parser.takeGE 4 Fold.toList) $ Stream.fromList [1,0,1]
563-- *** Exception: ParseError "takeGE: Expecting at least 4 elements, input terminated on 3"
565-- >>> Stream.parse (Parser.takeGE 4 Fold.toList) $ Stream.fromList [1,0,1,0,1]
571takeGE :: MonadCatch m => Int -> Fold m a b -> Parser m a b
572takeGE n = D.toParserK . D.takeGE n
574-------------------------------------------------------------------------------
575-- Take until a condition
576-------------------------------------------------------------------------------
579-- Note: This is called @takeWhileP@ and @munch@ in some parser libraries.
581-- | Like 'takeWhile' but uses a 'Parser' instead of a 'Fold' to collect the
582-- input. The combinator stops when the condition fails or if the collecting
585-- This is a generalized version of takeWhile, for example 'takeWhile1' can be
586-- implemented in terms of this:
589-- takeWhile1 cond p = takeWhile cond (takeBetween 1 maxBound p)
592-- Stops: when the condition fails or the collecting parser stops.
593-- Fails: when the collecting parser fails.
597{-# INLINE takeWhileP #-}
598takeWhileP :: -- MonadCatch m =>
599 (a -> Bool) -> Parser m a b -> Parser m a b
600takeWhileP _cond = undefined -- D.toParserK . D.takeWhileP cond
602-- | Collect stream elements until an element fails the predicate. The element
603-- on which the predicate fails is returned back to the input stream.
605-- * Stops - when the predicate fails or the collecting fold stops.
608-- >>> Stream.parse (Parser.takeWhile (== 0) Fold.toList) $ Stream.fromList [0,0,1,0,1]
611-- We can implement a @breakOn@ using 'takeWhile':
614-- breakOn p = takeWhile (not p)
619{-# INLINE takeWhile #-}
620takeWhile :: MonadCatch m => (a -> Bool) -> Fold m a b -> Parser m a b
621takeWhile cond = D.toParserK . D.takeWhile cond
623-- | Like 'takeWhile' but takes at least one element otherwise fails.
627{-# INLINE takeWhile1 #-}
628takeWhile1 :: MonadCatch m => (a -> Bool) -> Fold m a b -> Parser m a b
629takeWhile1 cond = D.toParserK . D.takeWhile1 cond
631-- | Drain the input as long as the predicate succeeds, running the effects and
632-- discarding the results.
634-- This is also called @skipWhile@ in some parsing libraries.
638{-# INLINE dropWhile #-}
639dropWhile :: MonadCatch m => (a -> Bool) -> Parser m a ()
640dropWhile p = takeWhile p FL.drain
642-------------------------------------------------------------------------------
644-------------------------------------------------------------------------------
646-- | @sliceSepByP cond parser@ parses a slice of the input using @parser@ until
647-- @cond@ succeeds or the parser stops.
649-- This is a generalized slicing parser which can be used to implement other
653-- sliceSepByMax cond n p = sliceSepByP cond (take n p)
654-- sliceSepByBetween cond m n p = sliceSepByP cond (takeBetween m n p)
659{-# INLINE sliceSepByP #-}
662 (a -> Bool) -> Parser m a b -> Parser m a b
663sliceSepByP cond = D.toParserK . D.sliceSepByP cond . D.fromParserK
665-- | Like 'sliceSepBy' but does not drop the separator element, instead
666-- separator is emitted as a separate element in the output.
669{-# INLINE sliceSepWith #-}
670sliceSepWith :: -- MonadCatch m =>
671 (a -> Bool) -> Fold m a b -> Parser m a b
672sliceSepWith _cond = undefined -- D.toParserK . D.sliceSepBy cond
674-- | Collect stream elements until an elements passes the predicate, return the
675-- last element on which the predicate succeeded back to the input stream. If
676-- the predicate succeeds on the first element itself then the parser does not
677-- terminate there. The succeeding element in the leading position
678-- is treated as a prefix separator which is kept in the output segment.
680-- * Stops - when the predicate succeeds in non-leading position.
683-- S.splitWithPrefix pred f = S.parseMany (PR.sliceBeginWith pred f)
688-- sliceBeginWithOdd ls = Stream.parse prsr (Stream.fromList ls)
689-- where prsr = Parser.sliceBeginWith odd Fold.toList
693-- >>> sliceBeginWithOdd [2, 4, 6, 3]
694-- *** Exception: sliceBeginWith : slice begins with an element which fails the predicate
697-- >>> sliceBeginWithOdd [3, 5, 7, 4]
700-- >>> sliceBeginWithOdd [3, 4, 6, 8, 5]
703-- >>> sliceBeginWithOdd []
708{-# INLINE sliceBeginWith #-}
711 (a -> Bool) -> Fold m a b -> Parser m a b
712sliceBeginWith cond = D.toParserK . D.sliceBeginWith cond
714-------------------------------------------------------------------------------
715-- Quoting and Escaping
716-------------------------------------------------------------------------------
718-- | Like 'sliceSepBy' but the separator elements can be escaped using an
719-- escape char determined by the second predicate.
722{-# INLINE escapedSliceSepBy #-}
723escapedSliceSepBy :: -- MonadCatch m =>
724 (a -> Bool) -> (a -> Bool) -> Fold m a b -> Parser m a b
725escapedSliceSepBy _cond _esc = undefined
726 -- D.toParserK . D.escapedSliceSepBy cond esc
728-- | @escapedFrameBy begin end escape@ parses a string framed using @begin@ and
729-- @end@ as the frame begin and end marker elements and @escape@ as an escaping
730-- element to escape the occurrence of the framing elements within the frame.
731-- Nested frames are allowed, but nesting is removed when parsing.
736-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello}"
739-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello {world}}"
742-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello \\{world\\}}"
745-- > Stream.parse (Parser.escapedFrameBy (== '{') (== '}') (== '\\') Fold.toList) $ Stream.fromList "{hello {world}"
746-- ParseError "Unterminated '{'"
751{-# INLINE escapedFrameBy #-}
752escapedFrameBy :: -- MonadCatch m =>
753 (a -> Bool) -> (a -> Bool) -> (a -> Bool) -> Fold m a b -> Parser m a b
754escapedFrameBy _begin _end _escape _p = undefined
755 -- D.toParserK . D.frameBy begin end escape p
757-------------------------------------------------------------------------------
759-------------------------------------------------------------------------------
761-- Note we can also get words using something like:
762-- sepBy FL.toList (takeWhile (not . p) Fold.toList) (dropWhile p)
764-- But that won't be as efficient and ergonomic.
766-- | Like 'splitOn' but strips leading, trailing, and repeated separators.
767-- Therefore, @".a..b."@ having '.' as the separator would be parsed as
768-- @["a","b"]@. In other words, its like parsing words from whitespace
771-- * Stops - when it finds a word separator after a non-word element
775-- S.wordsBy pred f = S.parseMany (PR.wordBy pred f)
779wordBy :: MonadCatch m => (a -> Bool) -> Fold m a b -> Parser m a b
780wordBy f = D.toParserK . D.wordBy f
782-- | Given an input stream @[a,b,c,...]@ and a comparison function @cmp@, the
783-- parser assigns the element @a@ to the first group, then if @a \`cmp` b@ is
784-- 'True' @b@ is also assigned to the same group. If @a \`cmp` c@ is 'True'
785-- then @c@ is also assigned to the same group and so on. When the comparison
786-- fails the parser is terminated. Each group is folded using the 'Fold' @f@ and
787-- the result of the fold is the result of the parser.
789-- * Stops - when the comparison fails.
795-- . Stream.parseMany (Parser.groupBy eq Fold.toList)
799-- >>> runGroupsBy (<) []
802-- >>> runGroupsBy (<) [1]
805-- >>> runGroupsBy (<) [3, 5, 4, 1, 2, 0]
806-- [[3,5,4],[1,2],[0]]
810{-# INLINE groupBy #-}
811groupBy :: MonadCatch m => (a -> a -> Bool) -> Fold m a b -> Parser m a b
812groupBy eq = D.toParserK . D.groupBy eq
814-- | Unlike 'groupBy' this combinator performs a rolling comparison of two
815-- successive elements in the input stream. Assuming the input stream
816-- is @[a,b,c,...]@ and the comparison function is @cmp@, the parser
817-- first assigns the element @a@ to the first group, then if @a \`cmp` b@ is
818-- 'True' @b@ is also assigned to the same group. If @b \`cmp` c@ is 'True'
819-- then @c@ is also assigned to the same group and so on. When the comparison
820-- fails the parser is terminated. Each group is folded using the 'Fold' @f@ and
821-- the result of the fold is the result of the parser.
823-- * Stops - when the comparison fails.
827-- runGroupsByRolling eq =
829-- . Stream.parseMany (Parser.groupByRolling eq Fold.toList)
833-- >>> runGroupsByRolling (<) []
836-- >>> runGroupsByRolling (<) [1]
839-- >>> runGroupsByRolling (<) [3, 5, 4, 1, 2, 0]
840-- [[3,5],[4],[1,2],[0]]
844{-# INLINE groupByRolling #-}
845groupByRolling :: MonadCatch m => (a -> a -> Bool) -> Fold m a b -> Parser m a b
846groupByRolling eq = D.toParserK . D.groupByRolling eq
848-- | Like 'groupByRolling', but if the predicate is 'True' then collects using
849-- the first fold as long as the predicate holds 'True', if the predicate is
850-- 'False' collects using the second fold as long as it remains 'False'.
851-- Returns 'Left' for the first case and 'Right' for the second case.
853-- For example, if we want to detect sorted sequences in a stream, both
854-- ascending and descending cases we can use 'groupByRollingEither (<=)
855-- Fold.toList Fold.toList'.
858{-# INLINE groupByRollingEither #-}
859groupByRollingEither :: MonadCatch m =>
860 (a -> a -> Bool) -> Fold m a b -> Fold m a c -> Parser m a (Either b c)
861groupByRollingEither eq f1 = D.toParserK . D.groupByRollingEither eq f1
863-- XXX Use a stream instead of a list so that we can use any container type.
865-- | Match the given sequence of elements using the given comparison function.
867-- >>> Stream.parse (Parser.eqBy (==) "string") $ Stream.fromList "string"
869-- >>> Stream.parse (Parser.eqBy (==) "mismatch") $ Stream.fromList "match"
870-- *** Exception: ParseError "eqBy: failed, yet to match 7 elements"
875eqBy :: MonadCatch m => (a -> a -> Bool) -> [a] -> Parser m a ()
876eqBy cmp = D.toParserK . D.eqBy cmp
878-- | Match the input sequence with the supplied list and return it if
883list :: (MonadCatch m, Eq a) => [a] -> Parser m a [a]
884list xs = eqBy (==) xs $> xs
886-------------------------------------------------------------------------------
888-------------------------------------------------------------------------------
890-- | Sequential parser application. Apply two parsers sequentially to an input
891-- stream. The input is provided to the first parser, when it is done the
892-- remaining input is provided to the second parser. If both the parsers
893-- succeed their outputs are combined using the supplied function. The
894-- operation fails if any of the parsers fail.
896-- Note: This is a parsing dual of appending streams using
897-- 'Streamly.Prelude.serial', it splits the streams using two parsers and zips
900-- This implementation is strict in the second argument, therefore, the
901-- following will fail:
903-- >>> Stream.parse (Parser.serialWith const (Parser.satisfy (> 0)) undefined) $ Stream.fromList [1]
904-- *** Exception: Prelude.undefined
907-- Compare with 'Applicative' instance method '<*>'. This implementation allows
908-- stream fusion but has quadratic complexity. This can fuse with other
909-- operations and can be faster than 'Applicative' instance for small number
910-- (less than 8) of compositions.
912-- Many combinators can be expressed using @serialWith@ and other parser
913-- primitives. Some common idioms are described below,
916-- span :: (a -> Bool) -> Fold m a b -> Fold m a b -> Parser m a b
917-- span pred f1 f2 = serialWith (,) ('takeWhile' pred f1) ('fromFold' f2)
921-- spanBy :: (a -> a -> Bool) -> Fold m a b -> Fold m a b -> Parser m a b
922-- spanBy eq f1 f2 = serialWith (,) ('groupBy' eq f1) ('fromFold' f2)
926-- spanByRolling :: (a -> a -> Bool) -> Fold m a b -> Fold m a b -> Parser m a b
927-- spanByRolling eq f1 f2 = serialWith (,) ('groupByRolling' eq f1) ('fromFold' f2)
932{-# INLINE serialWith #-}
933serialWith :: MonadCatch m
934 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
936 D.toParserK $ D.serialWith f (D.fromParserK p1) (D.fromParserK p2)
938-- | Sequential parser application ignoring the output of the first parser.
939-- Apply two parsers sequentially to an input stream. The input is provided to
940-- the first parser, when it is done the remaining input is provided to the
941-- second parser. The output of the parser is the output of the second parser.
942-- The operation fails if any of the parsers fail.
944-- This implementation is strict in the second argument, therefore, the
945-- following will fail:
947-- >>> Stream.parse (Parser.split_ (Parser.satisfy (> 0)) undefined) $ Stream.fromList [1]
948-- *** Exception: Prelude.undefined
951-- Compare with 'Applicative' instance method '*>'. This implementation allows
952-- stream fusion but has quadratic complexity. This can fuse with other
953-- operations, and can be faster than 'Applicative' instance for small
954-- number (less than 8) of compositions.
959split_ :: MonadCatch m => Parser m x a -> Parser m x b -> Parser m x b
960split_ p1 p2 = D.toParserK $ D.split_ (D.fromParserK p1) (D.fromParserK p2)
962-- | @teeWith f p1 p2@ distributes its input to both @p1@ and @p2@ until both
963-- of them succeed or anyone of them fails and combines their output using @f@.
964-- The parser succeeds if both the parsers succeed.
968{-# INLINE teeWith #-}
969teeWith :: MonadCatch m
970 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
972 D.toParserK $ D.teeWith f (D.fromParserK p1) (D.fromParserK p2)
974-- | Like 'teeWith' but ends parsing and zips the results, if available,
975-- whenever the first parser ends.
979{-# INLINE teeWithFst #-}
980teeWithFst :: MonadCatch m
981 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
983 D.toParserK $ D.teeWithFst f (D.fromParserK p1) (D.fromParserK p2)
985-- | Like 'teeWith' but ends parsing and zips the results, if available,
986-- whenever any of the parsers ends or fails.
990{-# INLINE teeWithMin #-}
991teeWithMin :: MonadCatch m
992 => (a -> b -> c) -> Parser m x a -> Parser m x b -> Parser m x c
994 D.toParserK $ D.teeWithMin f (D.fromParserK p1) (D.fromParserK p2)
996-- | Sequential alternative. Apply the input to the first parser and return the
997-- result if the parser succeeds. If the first parser fails then backtrack and
998-- apply the same input to the second parser and return the result.
1000-- Note: This implementation is not lazy in the second argument. The following
1003-- >>> Stream.parse (Parser.satisfy (> 0) `Parser.alt` undefined) $ Stream.fromList [1..10]
1006-- Compare with 'Alternative' instance method '<|>'. This implementation allows
1007-- stream fusion but has quadratic complexity. This can fuse with other
1008-- operations and can be much faster than 'Alternative' instance for small
1009-- number (less than 8) of alternatives.
1014alt :: MonadCatch m => Parser m x a -> Parser m x a -> Parser m x a
1015alt p1 p2 = D.toParserK $ D.alt (D.fromParserK p1) (D.fromParserK p2)
1017-- | Shortest alternative. Apply both parsers in parallel but choose the result
1018-- from the one which consumed least input i.e. take the shortest succeeding
1023{-# INLINE shortest #-}
1024shortest :: MonadCatch m
1025 => Parser m x a -> Parser m x a -> Parser m x a
1026shortest p1 p2 = D.toParserK $ D.shortest (D.fromParserK p1) (D.fromParserK p2)
1028-- | Longest alternative. Apply both parsers in parallel but choose the result
1029-- from the one which consumed more input i.e. take the longest succeeding
1034{-# INLINE longest #-}
1035longest :: MonadCatch m
1036 => Parser m x a -> Parser m x a -> Parser m x a
1037longest p1 p2 = D.toParserK $ D.longest (D.fromParserK p1) (D.fromParserK p2)
1039-- | Run a parser without consuming the input.
1043{-# INLINE lookAhead #-}
1044lookAhead :: MonadCatch m => Parser m a b -> Parser m a b
1045lookAhead p = D.toParserK $ D.lookAhead $ D.fromParserK p
1047-- | Takes at-most @n@ input elements.
1049-- * Stops - when the collecting parser stops.
1050-- * Fails - when the collecting parser fails.
1052-- >>> Stream.parse (Parser.takeP 4 (Parser.takeEQ 2 Fold.toList)) $ Stream.fromList [1, 2, 3, 4, 5]
1055-- >>> Stream.parse (Parser.takeP 4 (Parser.takeEQ 5 Fold.toList)) $ Stream.fromList [1, 2, 3, 4, 5]
1056-- *** Exception: ParseError "takeEQ: Expecting exactly 5 elements, input terminated on 4"
1060takeP :: MonadCatch m => Int -> Parser m a b -> Parser m a b
1061takeP i p = D.toParserK $ D.takeP i $ D.fromParserK p
1063-------------------------------------------------------------------------------
1064-- Sequential Collection
1065-------------------------------------------------------------------------------
1067-- | @concatSequence f t@ collects sequential parses of parsers in the
1068-- container @t@ using the fold @f@. Fails if the input ends or any of the
1071-- This is same as 'Data.Traversable.sequence' but more efficient.
1075{-# INLINE concatSequence #-}
1078 Fold m b c -> t (Parser m a b) -> Parser m a c
1079concatSequence _f _p = undefined
1081-- | Map a 'Parser' returning function on the result of a 'Parser'.
1083-- Compare with 'Monad' instance method '>>='. This implementation allows
1084-- stream fusion but has quadratic complexity. This can fuse with other
1085-- operations and can be much faster than 'Monad' instance for small number
1086-- (less than 8) of compositions.
1090{-# INLINE concatMap #-}
1091concatMap :: MonadCatch m
1092 => (b -> Parser m a c) -> Parser m a b -> Parser m a c
1093concatMap f p = D.toParserK $ D.concatMap (D.fromParserK . f) (D.fromParserK p)
1095-------------------------------------------------------------------------------
1096-- Alternative Collection
1097-------------------------------------------------------------------------------
1099-- | @choice parsers@ applies the @parsers@ in order and returns the first
1102-- This is same as 'asum' but more efficient.
1106{-# INLINE choice #-}
1108 (Functor t, Foldable t, MonadCatch m) => t (Parser m a b) -> Parser m a b
1109choice ps = D.toParserK $ D.choice $ D.fromParserK <$> ps
1111-------------------------------------------------------------------------------
1112-- Sequential Repetition
1113-------------------------------------------------------------------------------
1116-- TODO "many" is essentially a Fold because it cannot fail. So it can be
1117-- downgraded to a Fold. Or we can make the return type a Fold instead and
1118-- upgrade that to a parser when needed.
1120-- | Like 'many' but uses a 'Parser' instead of a 'Fold' to collect the
1121-- results. Parsing stops or fails if the collecting parser stops or fails.
1126manyP :: -- MonadCatch m =>
1127 Parser m a b -> Parser m b c -> Parser m a c
1128manyP _p _f = undefined -- D.toParserK $ D.manyP (D.fromParserK p) f
1130-- | Collect zero or more parses. Apply the supplied parser repeatedly on the
1131-- input stream and push the parse results to a downstream fold.
1133-- Stops: when the downstream fold stops or the parser fails.
1134-- Fails: never, produces zero or more results.
1136-- Compare with 'Control.Applicative.many'.
1141many :: MonadCatch m => Parser m a b -> Fold m b c -> Parser m a c
1142many p f = D.toParserK $ D.many (D.fromParserK p) f
1143-- many = countBetween 0 maxBound
1145-- Note: many1 would perhaps be a better name for this and consistent with
1146-- other names like takeWhile1. But we retain the name "some" for
1149-- | Collect one or more parses. Apply the supplied parser repeatedly on the
1150-- input stream and push the parse results to a downstream fold.
1152-- Stops: when the downstream fold stops or the parser fails.
1153-- Fails: if it stops without producing a single result.
1155-- @some fld parser = manyP (takeGE 1 fld) parser@
1157-- Compare with 'Control.Applicative.some'.
1162some :: MonadCatch m => Parser m a b -> Fold m b c -> Parser m a c
1163some p f = D.toParserK $ D.some (D.fromParserK p) f
1164-- some p f = manyP p (takeGE 1 f)
1165-- many = countBetween 1 maxBound
1167-- | @countBetween m n f p@ collects between @m@ and @n@ sequential parses of
1168-- parser @p@ using the fold @f@. Stop after collecting @n@ results. Fails if
1169-- the input ends or the parser fails before @m@ results are collected.
1173{-# INLINE countBetween #-}
1176 Int -> Int -> Parser m a b -> Fold m b c -> Parser m a c
1177countBetween _m _n _p = undefined
1178-- countBetween m n p f = manyP (takeBetween m n f) p
1180-- | @count n f p@ collects exactly @n@ sequential parses of parser @p@ using
1181-- the fold @f@. Fails if the input ends or the parser fails before @n@
1182-- results are collected.
1189 Int -> Parser m a b -> Fold m b c -> Parser m a c
1190count n = countBetween n n
1191-- count n p f = manyP (takeEQ n f) p
1193-- | Like 'manyTill' but uses a 'Parser' to collect the results instead of a
1194-- 'Fold'. Parsing stops or fails if the collecting parser stops or fails.
1196-- We can implemnent parsers like the following using 'manyTillP':
1199-- countBetweenTill m n f p = manyTillP (takeBetween m n f) p
1204{-# INLINE manyTillP #-}
1205manyTillP :: -- MonadCatch m =>
1206 Parser m a b -> Parser m a x -> Parser m b c -> Parser m a c
1207manyTillP _p1 _p2 _f = undefined
1208 -- D.toParserK $ D.manyTillP (D.fromParserK p1) (D.fromParserK p2) f
1210-- | @manyTill f collect test@ tries the parser @test@ on the input, if @test@
1211-- fails it backtracks and tries @collect@, after @collect@ succeeds @test@ is
1212-- tried again and so on. The parser stops when @test@ succeeds. The output of
1213-- @test@ is discarded and the output of @collect@ is accumulated by the
1214-- supplied fold. The parser fails if @collect@ fails.
1216-- Stops when the fold @f@ stops.
1220{-# INLINE manyTill #-}
1221manyTill :: MonadCatch m
1222 => Parser m a b -> Parser m a x -> Fold m b c -> Parser m a c
1224 D.toParserK $ D.manyTill f (D.fromParserK p1) (D.fromParserK p2)
1226-- | @manyThen f collect recover@ repeats the parser @collect@ on the input and
1227-- collects the output in the supplied fold. If the the parser @collect@ fails,
1228-- parser @recover@ is run until it stops and then we start repeating the
1229-- parser @collect@ again. The parser fails if the recovery parser fails.
1231-- For example, this can be used to find a key frame in a video stream after an
1236{-# INLINE manyThen #-}
1237manyThen :: -- (Foldable t, MonadCatch m) =>
1238 Parser m a b -> Parser m a x -> Fold m b c -> Parser m a c
1239manyThen _parser _recover _f = undefined
1241-------------------------------------------------------------------------------
1243-------------------------------------------------------------------------------
1245-- To deinterleave we can chain two parsers one behind the other. The input is
1246-- given to the first parser and the input definitively rejected by the first
1247-- parser is given to the second parser.
1249-- We can either have the parsers themselves buffer the input or use the shared
1250-- global buffer to hold it until none of the parsers need it. When the first
1251-- parser returns Skip (i.e. rewind) we let the second parser consume the
1252-- rejected input and when it is done we move the cursor forward to the first
1253-- parser again. This will require a "move forward" command as well.
1255-- To implement grep we can use three parsers, one to find the pattern, one
1256-- to store the context behind the pattern and one to store the context in
1257-- front of the pattern. When a match occurs we need to emit the accumulator of
1258-- all the three parsers. One parser can count the line numbers to provide the
1261-- | Apply two parsers alternately to an input stream. The input stream is
1262-- considered an interleaving of two patterns. The two parsers represent the
1265-- This undoes a "gintercalate" of two streams.
1269{-# INLINE deintercalate #-}
1272 Fold m a y -> Parser m x a
1273 -> Fold m b z -> Parser m x b
1274 -> Parser m x (y, z)
1275deintercalate = undefined
1277-- | Parse items separated by a separator parsed by the supplied parser. At
1278-- least one item must be present for the parser to succeed.
1279{-# INLINE sepBy1 #-}
1280sepBy1 :: MonadCatch m =>
1281 Fold m b c -> Parser m a b -> Parser m a x -> Parser m a c
1282sepBy1 sink p sep = do
1284 f <- fromEffect $ FL.initialize sink
1285 f1 <- fromEffect $ FL.snoc f x
1288-- | sepBy1 or empty, does not fail.
1290sepBy :: (MonadCatch m, Monoid c) =>
1291 Fold m b c -> Parser m a b -> Parser m a x -> Parser m a c
1292sepBy sink p sep = sepBy1 sink p sep <|> return mempty
1294-------------------------------------------------------------------------------
1295-- Interleaving a collection of parsers
1296-------------------------------------------------------------------------------
1298-- | Apply a collection of parsers to an input stream in a round robin fashion.
1299-- Each parser is applied until it stops and then we repeat starting with the
1300-- the first parser again.
1304{-# INLINE roundRobin #-}
1305roundRobin :: -- (Foldable t, MonadCatch m) =>
1306 t (Parser m a b) -> Fold m b c -> Parser m a c
1307roundRobin _ps _f = undefined
1309-------------------------------------------------------------------------------
1310-- Repeated Alternatives
1311-------------------------------------------------------------------------------
1313-- | Keep trying a parser up to a maximum of @n@ failures. When the parser
1314-- fails the input consumed till now is dropped and the new instance is tried
1315-- on the fresh input.
1319{-# INLINE retryMaxTotal #-}
1320retryMaxTotal :: -- (MonadCatch m) =>
1321 Int -> Parser m a b -> Fold m b c -> Parser m a c
1322retryMaxTotal _n _p _f = undefined
1324-- | Like 'retryMaxTotal' but aborts after @n@ successive failures.
1328{-# INLINE retryMaxSuccessive #-}
1329retryMaxSuccessive :: -- (MonadCatch m) =>
1330 Int -> Parser m a b -> Fold m b c -> Parser m a c
1331retryMaxSuccessive _n _p _f = undefined
1333-- | Keep trying a parser until it succeeds. When the parser fails the input
1334-- consumed till now is dropped and the new instance is tried on the fresh
1340retry :: -- (MonadCatch m) =>
1341 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