    {-# LANGUAGE BangPatterns #-}

    -- |
    -- Module      :  Control.Monad.Combinators
    -- Copyright   :  © 2017–present Mark Karpov
    -- License     :  BSD 3 clause
    --
    -- Maintainer  :  Mark Karpov <markkarpov92@gmail.com>
    -- Stability   :  experimental
    -- Portability :  portable
    --
    -- The module provides more efficient versions of the combinators from
    -- "Control.Applicative.Combinators" defined in terms of 'Monad' and
    -- 'MonadPlus' instead of 'Control.Applicative.Applicative' and
    -- 'Control.Applicative.Alternative'. When there is no difference in
    -- performance we just re-export the combinators from
    -- "Control.Applicative.Combinators".
    --
    -- @since 0.4.0
    module Control.Monad.Combinators
      ( -- * Re-exports from "Control.Applicative"
        (C.<|>),
        -- $assocbo
        C.optional,
        -- $optional
        C.empty,
        -- $empty

        -- * Original combinators
        C.between,
        C.choice,
        count,
        count',
        C.eitherP,
        endBy,
        endBy1,
        many,
        manyTill,
        manyTill_,
        some,
        someTill,
        someTill_,
        C.option,
        sepBy,
        sepBy1,
        sepEndBy,
        sepEndBy1,
        skipMany,
        skipSome,
        skipCount,
        skipManyTill,
        skipSomeTill,
      )
    where

    import qualified Control.Applicative.Combinators as C
    import Control.Monad

    ----------------------------------------------------------------------------
    -- Re-exports from "Control.Applicative"

    -- $assocbo
    --
    -- This combinator implements choice. The parser @p 'C.<|>' q@ first applies
    -- @p@. If it succeeds, the value of @p@ is returned. If @p@ fails, parser
    -- @q@ is tried.

    -- $optional
    --
    -- @'C.optional' p@ tries to apply the parser @p@. It will parse @p@ or
    -- 'Nothing'. It only fails if @p@ fails after consuming input. On success
    -- result of @p@ is returned inside of 'Just', on failure 'Nothing' is
    -- returned.
    --
    -- See also: 'C.option'.

    -- $empty
    --
    -- This parser fails unconditionally without providing any information about
    -- the cause of the failure.

    ----------------------------------------------------------------------------
    -- Original combinators

    -- | @'count' n p@ parses @n@ occurrences of @p@. If @n@ is smaller or equal
    -- to zero, the parser equals to @'return' []@. Returns a list of @n@
    -- values.
    --
    -- See also: 'skipCount', 'count''.
    count :: Monad m => Int -> m a -> m [a]
    count :: forall (m :: * -> *) a. Monad m => Int -> m a -> m [a]
    count Int
    n' m a
    p = ([a] -> [a]) -> Int -> m [a]
    forall {t} {c}. (Ord t, Num t) => ([a] -> c) -> t -> m c
    go [a] -> [a]
    forall a. a -> a
    id Int
    n'
      where
        go :: ([a] -> c) -> t -> m c
    go [a] -> c
    f !t
    n =
          if t
    n t -> t -> Bool
    forall a. Ord a => a -> a -> Bool
    <= t
    0
            then c -> m c
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ([a] -> c
    f [])
            else do
              x <- m a
    p
              go (f . (x :)) (n - 1)
    {-# INLINE count #-}

    -- | @'count'' m n p@ parses from @m@ to @n@ occurrences of @p@. If @n@ is
    -- not positive or @m > n@, the parser equals to @'return' []@. Returns a
    -- list of parsed values.
    --
    -- Please note that @m@ /may/ be negative, in this case effect is the same
    -- as if it were equal to zero.
    --
    -- See also: 'skipCount', 'count'.
    count' :: MonadPlus m => Int -> Int -> m a -> m [a]
    count' :: forall (m :: * -> *) a. MonadPlus m => Int -> Int -> m a -> m [a]
    count' Int
    m' Int
    n' m a
    p =
      if Int
    n' Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > Int
    0 Bool -> Bool -> Bool
    && Int
    n' Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Int
    m'
        then ([a] -> [a]) -> Int -> m [a]
    forall {t} {b}. (Ord t, Num t) => ([a] -> b) -> t -> m b
    gom [a] -> [a]
    forall a. a -> a
    id Int
    m'
        else [a] -> m [a]
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return []
      where
        gom :: ([a] -> b) -> t -> m b
    gom [a] -> b
    f !t
    m =
          if t
    m t -> t -> Bool
    forall a. Ord a => a -> a -> Bool
    > t
    0
            then do
              x <- m a
    p
              gom (f . (x :)) (m - 1)
            else ([a] -> b) -> Int -> m b
    forall {t} {b}. (Ord t, Num t) => ([a] -> b) -> t -> m b
    god [a] -> b
    f (if Int
    m' Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    <= Int
    0 then Int
    n' else Int
    n' Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    m')
        god :: ([a] -> c) -> t -> m c
    god [a] -> c
    f !t
    d =
          if t
    d t -> t -> Bool
    forall a. Ord a => a -> a -> Bool
    > t
    0
            then do
              r <- m a -> m (Maybe a)
    forall (f :: * -> *) a. Alternative f => f a -> f (Maybe a)
    C.optional m a
    p
              case r of
                Maybe a
    Nothing -> c -> m c
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ([a] -> c
    f [])
                Just a
    x -> ([a] -> c) -> t -> m c
    god ([a] -> c
    f ([a] -> c) -> ([a] -> [a]) -> [a] -> c
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a
    x a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :)) (t
    d t -> t -> t
    forall a. Num a => a -> a -> a
    - t
    1)
            else c -> m c
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ([a] -> c
    f [])
    {-# INLINE count' #-}

    -- | @'endBy' p sep@ parses /zero/ or more occurrences of @p@, separated and
    -- ended by @sep@. Returns a list of values returned by @p@.
    --
    -- > cStatements = cStatement `endBy` semicolon
    endBy :: MonadPlus m => m a -> m sep -> m [a]
    endBy :: forall (m :: * -> *) a sep. MonadPlus m => m a -> m sep -> m [a]
    endBy m a
    p m sep
    sep = m a -> m [a]
    forall (m :: * -> *) a. MonadPlus m => m a -> m [a]
    many (m a
    p m a -> (a -> m a) -> m a
    forall a b. m a -> (a -> m b) -> m b
    forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
    >>= \a
    x -> a
    x a -> m sep -> m a
    forall a b. a -> m b -> m a
    forall (f :: * -> *) a b. Functor f => a -> f b -> f a
    <$ m sep
    sep)
    {-# INLINE endBy #-}

    -- | @'endBy1' p sep@ parses /one/ or more occurrences of @p@, separated and
    -- ended by @sep@. Returns a list of values returned by @p@.
    endBy1 :: MonadPlus m => m a -> m sep -> m [a]
    endBy1 :: forall (m :: * -> *) a sep. MonadPlus m => m a -> m sep -> m [a]
    endBy1 m a
    p m sep
    sep = m a -> m [a]
    forall (m :: * -> *) a. MonadPlus m => m a -> m [a]
    some (m a
    p m a -> (a -> m a) -> m a
    forall a b. m a -> (a -> m b) -> m b
    forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
    >>= \a
    x -> a
    x a -> m sep -> m a
    forall a b. a -> m b -> m a
    forall (f :: * -> *) a b. Functor f => a -> f b -> f a
    <$ m sep
    sep)
    {-# INLINE endBy1 #-}

    -- | @'many' p@ applies the parser @p@ /zero/ or more times and returns a
    -- list of the values returned by @p@.
    --
    -- > identifier = (:) <$> letter <*> many (alphaNumChar <|> char '_')
    many :: MonadPlus m => m a -> m [a]
    many :: forall (m :: * -> *) a. MonadPlus m => m a -> m [a]
    many m a
    p = ([a] -> [a]) -> m [a]
    forall {c}. ([a] -> c) -> m c
    go [a] -> [a]
    forall a. a -> a
    id
      where
        go :: ([a] -> c) -> m c
    go [a] -> c
    f = do
          r <- m a -> m (Maybe a)
    forall (f :: * -> *) a. Alternative f => f a -> f (Maybe a)
    C.optional m a
    p
          case r of
            Maybe a
    Nothing -> c -> m c
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ([a] -> c
    f [])
            Just a
    x -> ([a] -> c) -> m c
    go ([a] -> c
    f ([a] -> c) -> ([a] -> [a]) -> [a] -> c
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a
    x a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :))
    {-# INLINE many #-}

    -- | @'manyTill' p end@ applies parser @p@ /zero/ or more times until parser
    -- @end@ succeeds. Returns the list of values returned by @p@. __Note__ that
    -- @end@ result is consumed and lost. Use 'manyTill_' if you wish to keep
    -- it.
    --
    -- See also: 'skipMany', 'skipManyTill'.
    manyTill :: MonadPlus m => m a -> m end -> m [a]
    manyTill :: forall (m :: * -> *) a sep. MonadPlus m => m a -> m sep -> m [a]
    manyTill m a
    p m end
    end = ([a], end) -> [a]
    forall a b. (a, b) -> a
    fst (([a], end) -> [a]) -> m ([a], end) -> m [a]
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> m a -> m end -> m ([a], end)
    forall (m :: * -> *) a end.
    MonadPlus m =>
    m a -> m end -> m ([a], end)
    manyTill_ m a
    p m end
    end
    {-# INLINE manyTill #-}

    -- | @'manyTill_' p end@ applies parser @p@ /zero/ or more times until
    -- parser @end@ succeeds. Returns the list of values returned by @p@ and the
    -- @end@ result. Use 'manyTill' if you have no need in the result of the
    -- @end@.
    --
    -- See also: 'skipMany', 'skipManyTill'.
    --
    -- @since 1.2.0
    manyTill_ :: MonadPlus m => m a -> m end -> m ([a], end)
    manyTill_ :: forall (m :: * -> *) a end.
    MonadPlus m =>
    m a -> m end -> m ([a], end)
    manyTill_ m a
    p m end
    end = ([a] -> [a]) -> m ([a], end)
    forall {c}. ([a] -> c) -> m (c, end)
    go [a] -> [a]
    forall a. a -> a
    id
      where
        go :: ([a] -> c) -> m (c, end)
    go [a] -> c
    f = do
          done <- m end -> m (Maybe end)
    forall (f :: * -> *) a. Alternative f => f a -> f (Maybe a)
    C.optional m end
    end
          case done of
            Just end
    done' -> (c, end) -> m (c, end)
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ([a] -> c
    f [], end
    done')
            Maybe end
    Nothing -> do
              x <- m a
    p
              go (f . (x :))
    {-# INLINE manyTill_ #-}

    -- | @'some' p@ applies the parser @p@ /one/ or more times and returns a
    -- list of the values returned by @p@.
    --
    -- > word = some letter
    some :: MonadPlus m => m a -> m [a]
    some :: forall (m :: * -> *) a. MonadPlus m => m a -> m [a]
    some m a
    p = (a -> [a] -> [a]) -> m a -> m [a] -> m [a]
    forall (m :: * -> *) a1 a2 r.
    Monad m =>
    (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
    liftM2 (:) m a
    p (m a -> m [a]
    forall (m :: * -> *) a. MonadPlus m => m a -> m [a]
    many m a
    p)
    {-# INLINE some #-}

    -- | @'someTill' p end@ works similarly to @'manyTill' p end@, but @p@
    -- should succeed at least once. __Note__ that @end@ result is consumed and
    -- lost. Use 'someTill_' if you wish to keep it.
    --
    -- > someTill p end = liftM2 (:) p (manyTill p end)
    --
    -- See also: 'skipSome', 'skipSomeTill'.
    someTill :: MonadPlus m => m a -> m end -> m [a]
    someTill :: forall (m :: * -> *) a sep. MonadPlus m => m a -> m sep -> m [a]
    someTill m a
    p m end
    end = (a -> [a] -> [a]) -> m a -> m [a] -> m [a]
    forall (m :: * -> *) a1 a2 r.
    Monad m =>
    (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
    liftM2 (:) m a
    p (m a -> m end -> m [a]
    forall (m :: * -> *) a sep. MonadPlus m => m a -> m sep -> m [a]
    manyTill m a
    p m end
    end)
    {-# INLINE someTill #-}

    -- | @'someTill_' p end@ works similarly to @'manyTill_' p end@, but @p@
    -- should succeed at least once. Use 'someTill' if you have no need in the
    -- result of the @end@.
    --
    -- See also: 'skipSome', 'skipSomeTill'.
    --
    -- @since 1.2.0
    someTill_ :: MonadPlus m => m a -> m end -> m ([a], end)
    someTill_ :: forall (m :: * -> *) a end.
    MonadPlus m =>
    m a -> m end -> m ([a], end)
    someTill_ m a
    p m end
    end = (a -> ([a], end) -> ([a], end))
    -> m a -> m ([a], end) -> m ([a], end)
    forall (m :: * -> *) a1 a2 r.
    Monad m =>
    (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
    liftM2 (\a
    x ([a]
    xs, end
    y) -> (a
    x a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    : [a]
    xs, end
    y)) m a
    p (m a -> m end -> m ([a], end)
    forall (m :: * -> *) a end.
    MonadPlus m =>
    m a -> m end -> m ([a], end)
    manyTill_ m a
    p m end
    end)
    {-# INLINE someTill_ #-}

    -- | @'sepBy' p sep@ parses /zero/ or more occurrences of @p@, separated by
    -- @sep@. Returns a list of values returned by @p@.
    --
    -- > commaSep p = p `sepBy` comma
    sepBy :: MonadPlus m => m a -> m sep -> m [a]
    sepBy :: forall (m :: * -> *) a sep. MonadPlus m => m a -> m sep -> m [a]
    sepBy m a
    p m sep
    sep = do
      r <- m a -> m (Maybe a)
    forall (f :: * -> *) a. Alternative f => f a -> f (Maybe a)
    C.optional m a
    p
      case r of
        Maybe a
    Nothing -> [a] -> m [a]
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return []
        Just a
    x -> (a
    x a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :) ([a] -> [a]) -> m [a] -> m [a]
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> m a -> m [a]
    forall (m :: * -> *) a. MonadPlus m => m a -> m [a]
    many (m sep
    sep m sep -> m a -> m a
    forall a b. m a -> m b -> m b
    forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
    >> m a
    p)
    {-# INLINE sepBy #-}

    -- | @'sepBy1' p sep@ parses /one/ or more occurrences of @p@, separated by
    -- @sep@. Returns a list of values returned by @p@.
    sepBy1 :: MonadPlus m => m a -> m sep -> m [a]
    sepBy1 :: forall (m :: * -> *) a sep. MonadPlus m => m a -> m sep -> m [a]
    sepBy1 m a
    p m sep
    sep = do
      x <- m a
    p
      (x :) <$> many (sep >> p)
    {-# INLINE sepBy1 #-}

    -- | @'sepEndBy' p sep@ parses /zero/ or more occurrences of @p@, separated
    -- and optionally ended by @sep@. Returns a list of values returned by @p@.
    sepEndBy :: MonadPlus m => m a -> m sep -> m [a]
    sepEndBy :: forall (m :: * -> *) a sep. MonadPlus m => m a -> m sep -> m [a]
    sepEndBy m a
    p m sep
    sep = ([a] -> [a]) -> m [a]
    forall {c}. ([a] -> c) -> m c
    go [a] -> [a]
    forall a. a -> a
    id
      where
        go :: ([a] -> c) -> m c
    go [a] -> c
    f = do
          r <- m a -> m (Maybe a)
    forall (f :: * -> *) a. Alternative f => f a -> f (Maybe a)
    C.optional m a
    p
          case r of
            Maybe a
    Nothing -> c -> m c
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ([a] -> c
    f [])
            Just a
    x -> do
              more <- Bool -> m Bool -> m Bool
    forall (m :: * -> *) a. Alternative m => a -> m a -> m a
    C.option Bool
    False (Bool
    True Bool -> m sep -> m Bool
    forall a b. a -> m b -> m a
    forall (f :: * -> *) a b. Functor f => a -> f b -> f a
    <$ m sep
    sep)
              if more
                then go (f . (x :))
                else return (f [x])
    {-# INLINE sepEndBy #-}

    -- | @'sepEndBy1' p sep@ parses /one/ or more occurrences of @p@, separated
    -- and optionally ended by @sep@. Returns a list of values returned by @p@.
    sepEndBy1 :: MonadPlus m => m a -> m sep -> m [a]
    sepEndBy1 :: forall (m :: * -> *) a sep. MonadPlus m => m a -> m sep -> m [a]
    sepEndBy1 m a
    p m sep
    sep = do
      x <- m a
    p
      more <- C.option False (True <$ sep)
      if more
        then (x :) <$> sepEndBy p sep
        else return [x]
    {-# INLINE sepEndBy1 #-}

    -- | @'skipMany' p@ applies the parser @p@ /zero/ or more times, skipping
    -- its result.
    --
    -- See also: 'manyTill', 'skipManyTill'.
    skipMany :: MonadPlus m => m a -> m ()
    skipMany :: forall (m :: * -> *) a. MonadPlus m => m a -> m ()
    skipMany m a
    p = m ()
    go
      where
        go :: m ()
    go = do
          more <- Bool -> m Bool -> m Bool
    forall (m :: * -> *) a. Alternative m => a -> m a -> m a
    C.option Bool
    False (Bool
    True Bool -> m a -> m Bool
    forall a b. a -> m b -> m a
    forall (f :: * -> *) a b. Functor f => a -> f b -> f a
    <$ m a
    p)
          when more go
    {-# INLINE skipMany #-}

    -- | @'skipSome' p@ applies the parser @p@ /one/ or more times, skipping its
    -- result.
    --
    -- See also: 'someTill', 'skipSomeTill'.
    skipSome :: MonadPlus m => m a -> m ()
    skipSome :: forall (m :: * -> *) a. MonadPlus m => m a -> m ()
    skipSome m a
    p = m a
    p m a -> m () -> m ()
    forall a b. m a -> m b -> m b
    forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
    >> m a -> m ()
    forall (m :: * -> *) a. MonadPlus m => m a -> m ()
    skipMany m a
    p
    {-# INLINE skipSome #-}

    -- | @'skipCount' n p@ parses @n@ occurrences of @p@, skipping its result.
    -- If @n@ is smaller or equal to zero, the parser equals to @'return' ()@.
    --
    -- See also: 'count', 'count''.
    skipCount :: Monad m => Int -> m a -> m ()
    skipCount :: forall (m :: * -> *) a. Monad m => Int -> m a -> m ()
    skipCount Int
    n' m a
    p = Int -> m ()
    forall {t}. (Ord t, Num t) => t -> m ()
    go Int
    n'
      where
        go :: t -> m ()
    go !t
    n =
          Bool -> m () -> m ()
    forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
    unless (t
    n t -> t -> Bool
    forall a. Ord a => a -> a -> Bool
    <= t
    0) (m () -> m ()) -> m () -> m ()
    forall a b. (a -> b) -> a -> b
    $
            m a
    p m a -> m () -> m ()
    forall a b. m a -> m b -> m b
    forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
    >> t -> m ()
    go (t
    n t -> t -> t
    forall a. Num a => a -> a -> a
    - t
    1)
    {-# INLINE skipCount #-}

    -- | @'skipManyTill' p end@ applies the parser @p@ /zero/ or more times
    -- skipping results until parser @end@ succeeds. Result parsed by @end@ is
    -- then returned.
    --
    -- See also: 'manyTill', 'skipMany'.
    skipManyTill :: MonadPlus m => m a -> m end -> m end
    skipManyTill :: forall (m :: * -> *) a end. MonadPlus m => m a -> m end -> m end
    skipManyTill m a
    p m end
    end = m end
    go
      where
        go :: m end
    go = do
          r <- m end -> m (Maybe end)
    forall (f :: * -> *) a. Alternative f => f a -> f (Maybe a)
    C.optional m end
    end
          case r of
            Maybe end
    Nothing -> m a
    p m a -> m end -> m end
    forall a b. m a -> m b -> m b
    forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
    >> m end
    go
            Just end
    x -> end -> m end
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return end
    x
    {-# INLINE skipManyTill #-}

    -- | @'skipSomeTill' p end@ applies the parser @p@ /one/ or more times
    -- skipping results until parser @end@ succeeds. Result parsed by @end@ is
    -- then returned.
    --
    -- See also: 'someTill', 'skipSome'.
    skipSomeTill :: MonadPlus m => m a -> m end -> m end
    skipSomeTill :: forall (m :: * -> *) a end. MonadPlus m => m a -> m end -> m end
    skipSomeTill m a
    p m end
    end = m a
    p m a -> m end -> m end
    forall a b. m a -> m b -> m b
    forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
    >> m a -> m end -> m end
    forall (m :: * -> *) a end. MonadPlus m => m a -> m end -> m end
    skipManyTill m a
    p m end
    end
    {-# INLINE skipSomeTill #-}