    {-# LANGUAGE CPP #-}

    -- |A collection of loop operators for use in monads (mostly in stateful ones).
    --
    -- There is a general naming pattern for many of these:
    -- Functions with names ending in _ discard the results of the loop body
    -- as in the standard Prelude 'mapM' functions.
    --
    -- Functions with names ending in ' collect their results into 'MonadPlus'
    -- containers.  Note that any short-circuit effect that those types'
    -- 'MonadPlus' instances may provide in a lazy context (such as the instance
    -- for 'Maybe') will _not_ cause execution to short-circuit in these loops.
    --
    -- Functions with names ending in neither of those will generally return
    -- just plain old lists.

    module Control.Monad.Loops
            ( module Control.Monad.Loops
            ) where

    import Control.Monad

    import Control.Exception
    import Control.Concurrent

    #ifndef base4
    #define SomeException Exception
    #endif

    -- possibly-useful addition? :
    -- concatMapM :: (Monad m, Traversable f, Monoid w) => (a -> m w) -> (f a) -> m w

    -- would also like to implement an "interleavable" version of forkMapM (probably
    -- using something other than a list in the return) that can effectively handle
    -- very large or even infinite input lists.

    -- |Like 'mapM', but run all the actions in parallel threads, collecting up
    -- the results and returning them all.  Does not return until all actions finish.
    forkMapM :: (a -> IO b) -> [a] -> IO [Either SomeException b]
    forkMapM :: forall a b. (a -> IO b) -> [a] -> IO [Either SomeException b]
    forkMapM a -> IO b
    f [a]
    xs = do
            mvars <- [a]
    -> (a -> IO (MVar (Either SomeException b)))
    -> IO [MVar (Either SomeException b)]
    forall (t :: * -> *) (m :: * -> *) a b.
    (Traversable t, Monad m) =>
    t a -> (a -> m b) -> m (t b)
    forM [a]
    xs ((a -> IO (MVar (Either SomeException b)))
     -> IO [MVar (Either SomeException b)])
    -> (a -> IO (MVar (Either SomeException b)))
    -> IO [MVar (Either SomeException b)]
    forall a b. (a -> b) -> a -> b
    $ \a
    x -> do
                    mvar <- IO (MVar (Either SomeException b))
    forall a. IO (MVar a)
    newEmptyMVar
                    forkIO $ do
                            result <- handle (return . Left) $ do
                                    y <- f x
                                    return (Right y)
                            putMVar mvar result
                    return mvar

            mapM takeMVar mvars

    -- | like 'forkMapM' but without bothering to keep the return values
    forkMapM_ :: (a -> IO b) -> [a] -> IO [Maybe SomeException]
    forkMapM_ :: forall a b. (a -> IO b) -> [a] -> IO [Maybe SomeException]
    forkMapM_ a -> IO b
    f [a]
    xs = do
            mvars <- [a]
    -> (a -> IO (MVar (Maybe SomeException)))
    -> IO [MVar (Maybe SomeException)]
    forall (t :: * -> *) (m :: * -> *) a b.
    (Traversable t, Monad m) =>
    t a -> (a -> m b) -> m (t b)
    forM [a]
    xs ((a -> IO (MVar (Maybe SomeException)))
     -> IO [MVar (Maybe SomeException)])
    -> (a -> IO (MVar (Maybe SomeException)))
    -> IO [MVar (Maybe SomeException)]
    forall a b. (a -> b) -> a -> b
    $ \a
    x -> do
                    mvar <- IO (MVar (Maybe SomeException))
    forall a. IO (MVar a)
    newEmptyMVar
                    forkIO $ do
                            -- in base >=4, need to nail down the type of 'handle'
                            let handleAny :: (SomeException -> IO a) -> IO a -> IO a
                                handleAny = (SomeException -> IO a) -> IO a -> IO a
    forall e a. Exception e => (e -> IO a) -> IO a -> IO a
    handle
                            result <- handleAny (return . Just) $ do
                                    f x
                                    return Nothing
                            putMVar mvar result
                    return mvar

            mapM takeMVar mvars

    -- | like 'forkMapM_' but not even bothering to track success or failure
    -- of the child threads.  Still waits for them all though.
    forkMapM__ :: (a -> IO b) -> [a] -> IO ()
    forkMapM__ :: forall a b. (a -> IO b) -> [a] -> IO ()
    forkMapM__ a -> IO b
    f [a]
    xs = do
            mvars <- [a] -> (a -> IO (MVar ())) -> IO [MVar ()]
    forall (t :: * -> *) (m :: * -> *) a b.
    (Traversable t, Monad m) =>
    t a -> (a -> m b) -> m (t b)
    forM [a]
    xs ((a -> IO (MVar ())) -> IO [MVar ()])
    -> (a -> IO (MVar ())) -> IO [MVar ()]
    forall a b. (a -> b) -> a -> b
    $ \a
    x -> do
                    mvar <- IO (MVar ())
    forall a. IO (MVar a)
    newEmptyMVar
                    forkIO $ do
                            -- in base >=4, need to nail down the type of 'handle'
                            let handleAny :: (SomeException -> IO a) -> IO a -> IO a
                                handleAny = (SomeException -> IO a) -> IO a -> IO a
    forall e a. Exception e => (e -> IO a) -> IO a -> IO a
    handle
                            handleAny (\SomeException
    _ -> () -> IO ()
    forall a. a -> IO a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ()) $ do
                                    f x
                                    return ()
                            putMVar mvar ()
                    return mvar

            mapM_ takeMVar mvars

    {-# SPECIALIZE whileM  :: IO Bool -> IO a -> IO [a] #-}
    {-# SPECIALIZE whileM' :: Monad m => m Bool -> m a -> m [a] #-}
    {-# SPECIALIZE whileM' :: IO Bool -> IO a -> IO [a] #-}
    {-# SPECIALIZE whileM_ :: IO Bool -> IO a -> IO () #-}

    -- |Execute an action repeatedly as long as the given boolean expression
    -- returns True.  The condition is evaluated before the loop body.
    -- Collects the results into a list.
    whileM :: Monad m => m Bool -> m a -> m [a]
    whileM :: forall (m :: * -> *) a. Monad m => m Bool -> m a -> m [a]
    whileM = m Bool -> m a -> m [a]
    forall (m :: * -> *) (f :: * -> *) a.
    (Monad m, MonadPlus f) =>
    m Bool -> m a -> m (f a)
    whileM'

    -- |Execute an action repeatedly as long as the given boolean expression
    -- returns True. The condition is evaluated before the loop body.
    -- Collects the results into an arbitrary 'MonadPlus' value.
    whileM' :: (Monad m, MonadPlus f) => m Bool -> m a -> m (f a)
    whileM' :: forall (m :: * -> *) (f :: * -> *) a.
    (Monad m, MonadPlus f) =>
    m Bool -> m a -> m (f a)
    whileM' m Bool
    p m a
    f = m (f a)
    go
        where go :: m (f a)
    go = do
                x <- m Bool
    p
                if x
                    then do
                            x  <- f
                            xs <- go
                            return (return x `mplus` xs)
                    else return mzero

    -- |Execute an action repeatedly as long as the given boolean expression
    -- returns True.  The condition is evaluated before the loop body.
    -- Discards results.
    whileM_ :: (Monad m) => m Bool -> m a -> m ()
    whileM_ :: forall (m :: * -> *) a. Monad m => m Bool -> m a -> m ()
    whileM_ m Bool
    p m a
    f = m ()
    go
        where go :: m ()
    go = do
                x <- m Bool
    p
                if x
                    then f >> go
                    else return ()

    -- |Execute an action repeatedly until its result fails to satisfy a predicate,
    -- and return that result (discarding all others).
    iterateWhile :: Monad m => (a -> Bool) -> m a -> m a
    iterateWhile :: forall (m :: * -> *) a. Monad m => (a -> Bool) -> m a -> m a
    iterateWhile a -> Bool
    p = (a -> Bool) -> m a -> m a
    forall (m :: * -> *) a. Monad m => (a -> Bool) -> m a -> m a
    iterateUntil (Bool -> Bool
    not (Bool -> Bool) -> (a -> Bool) -> a -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> Bool
    p)

    {-# SPECIALIZE iterateM_ :: (a -> IO a) -> a -> IO b #-}
    -- |Execute an action forever, feeding the result of each execution as the
    -- input to the next.
    iterateM_ :: Monad m => (a -> m a) -> a -> m b
    iterateM_ :: forall (m :: * -> *) a b. Monad m => (a -> m a) -> a -> m b
    iterateM_ a -> m a
    f = a -> m b
    forall {b}. a -> m b
    g
        where g :: a -> m b
    g a
    x = a -> m a
    f a
    x m a -> (a -> m b) -> m b
    forall a b. m a -> (a -> m b) -> m b
    forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
    >>= a -> m b
    g

    {-# SPECIALIZE untilM  :: IO a -> IO Bool -> IO [a] #-}
    {-# SPECIALIZE untilM' :: Monad m => m a -> m Bool -> m [a] #-}
    {-# SPECIALIZE untilM' :: IO a -> IO Bool -> IO [a] #-}
    {-# SPECIALIZE untilM_ :: IO a -> IO Bool -> IO () #-}

    infixr 0 `untilM`
    infixr 0 `untilM'`
    infixr 0 `untilM_`
    infixr 0 `iterateUntilM`

    -- |Execute an action repeatedly until the condition expression returns True.
    -- The condition is evaluated after the loop body.  Collects results into a list.
    -- Parameters are arranged for infix usage.  eg. do {...} `untilM_` ...
    untilM :: Monad m => m a -> m Bool -> m [a]
    untilM :: forall (m :: * -> *) a. Monad m => m a -> m Bool -> m [a]
    untilM = m a -> m Bool -> m [a]
    forall (m :: * -> *) (f :: * -> *) a.
    (Monad m, MonadPlus f) =>
    m a -> m Bool -> m (f a)
    untilM'

    -- |Execute an action repeatedly until the condition expression returns True.
    -- The condition is evaluated after the loop body.  Collects results into a
    -- "MonadPlus" value.
    -- Parameters are arranged for infix usage.  eg. do {...} `untilM_` ...
    untilM' :: (Monad m, MonadPlus f) => m a -> m Bool -> m (f a)
    m a
    f untilM' :: forall (m :: * -> *) (f :: * -> *) a.
    (Monad m, MonadPlus f) =>
    m a -> m Bool -> m (f a)
    `untilM'` m Bool
    p = do
            x  <- m a
    f
            xs <- whileM' (liftM not p) f
            return (return x `mplus` xs)

    -- |Execute an action repeatedly until the condition expression returns True.
    -- The condition is evaluated after the loop body.  Discards results.
    -- Parameters are arranged for infix usage.  eg. do {...} `untilM_` ...
    untilM_ :: (Monad m) => m a -> m Bool -> m ()
    m a
    f untilM_ :: forall (m :: * -> *) a. Monad m => m a -> m Bool -> m ()
    `untilM_` m Bool
    p = m a
    f 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 Bool -> m a -> m ()
    forall (m :: * -> *) a. Monad m => m Bool -> m a -> m ()
    whileM_ ((Bool -> Bool) -> m Bool -> m Bool
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM Bool -> Bool
    not m Bool
    p) m a
    f

    -- | Analogue of @('Prelude.until')@
    -- Yields the result of applying f until p holds.
    iterateUntilM :: (Monad m) => (a -> Bool) -> (a -> m a) -> a -> m a
    iterateUntilM :: forall (m :: * -> *) a.
    Monad m =>
    (a -> Bool) -> (a -> m a) -> a -> m a
    iterateUntilM a -> Bool
    p a -> m a
    f a
    v
        | a -> Bool
    p a
    v       = a -> m a
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return a
    v
        | Bool
    otherwise = a -> m a
    f a
    v 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 -> Bool) -> (a -> m a) -> a -> m a
    forall (m :: * -> *) a.
    Monad m =>
    (a -> Bool) -> (a -> m a) -> a -> m a
    iterateUntilM a -> Bool
    p a -> m a
    f

    -- |Execute an action repeatedly until its result satisfies a predicate,
    -- and return that result (discarding all others).
    iterateUntil :: Monad m => (a -> Bool) -> m a -> m a
    iterateUntil :: forall (m :: * -> *) a. Monad m => (a -> Bool) -> m a -> m a
    iterateUntil a -> Bool
    p m a
    x = m a
    x 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 -> Bool) -> (a -> m a) -> a -> m a
    forall (m :: * -> *) a.
    Monad m =>
    (a -> Bool) -> (a -> m a) -> a -> m a
    iterateUntilM a -> Bool
    p (m a -> a -> m a
    forall a b. a -> b -> a
    const m a
    x)

    {-# SPECIALIZE whileJust  :: IO (Maybe a) -> (a -> IO b) -> IO [b] #-}
    {-# SPECIALIZE whileJust' :: Monad m => m (Maybe a) -> (a -> m b) -> m [b] #-}
    {-# SPECIALIZE whileJust' :: IO (Maybe a) -> (a -> IO b) -> IO [b] #-}
    {-# SPECIALIZE whileJust_ :: IO (Maybe a) -> (a -> IO b) -> IO () #-}

    -- |As long as the supplied "Maybe" expression returns "Just _", the loop
    -- body will be called and passed the value contained in the 'Just'.  Results
    -- are collected into a list.
    whileJust :: Monad m => m (Maybe a) -> (a -> m b) -> m [b]
    whileJust :: forall (m :: * -> *) a b.
    Monad m =>
    m (Maybe a) -> (a -> m b) -> m [b]
    whileJust = m (Maybe a) -> (a -> m b) -> m [b]
    forall (m :: * -> *) (f :: * -> *) a b.
    (Monad m, MonadPlus f) =>
    m (Maybe a) -> (a -> m b) -> m (f b)
    whileJust'

    -- |As long as the supplied "Maybe" expression returns "Just _", the loop
    -- body will be called and passed the value contained in the 'Just'.  Results
    -- are collected into an arbitrary MonadPlus container.
    whileJust' :: (Monad m, MonadPlus f) => m (Maybe a) -> (a -> m b) -> m (f b)
    whileJust' :: forall (m :: * -> *) (f :: * -> *) a b.
    (Monad m, MonadPlus f) =>
    m (Maybe a) -> (a -> m b) -> m (f b)
    whileJust' m (Maybe a)
    p a -> m b
    f = m (f b)
    go
        where go :: m (f b)
    go = do
                x <- m (Maybe a)
    p
                case x of
                    Maybe a
    Nothing -> f b -> m (f b)
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return f b
    forall a. f a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero
                    Just a
    x  -> do
                            x  <- a -> m b
    f a
    x
                            xs <- go
                            return (return x `mplus` xs)

    -- |As long as the supplied "Maybe" expression returns "Just _", the loop
    -- body will be called and passed the value contained in the 'Just'.  Results
    -- are discarded.
    whileJust_ :: (Monad m) => m (Maybe a) -> (a -> m b) -> m ()
    whileJust_ :: forall (m :: * -> *) a b.
    Monad m =>
    m (Maybe a) -> (a -> m b) -> m ()
    whileJust_ m (Maybe a)
    p a -> m b
    f = m ()
    go
        where go :: m ()
    go = do
                x <- m (Maybe a)
    p
                case x of
                    Maybe a
    Nothing -> () -> m ()
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ()
                    Just a
    x  -> do
                            a -> m b
    f a
    x
                            m ()
    go

    -- |Run the supplied "Maybe" computation repeatedly until it returns a
    -- value.  Returns that value.
    untilJust :: Monad m => m (Maybe a) -> m a
    untilJust :: forall (m :: * -> *) a. Monad m => m (Maybe a) -> m a
    untilJust m (Maybe a)
    m = m a
    go
        where
            go :: m a
    go = do
                x <- m (Maybe a)
    m
                case x of
                    Maybe a
    Nothing -> m a
    go
                    Just a
    x  -> a -> m a
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return a
    x

    {-# SPECIALIZE unfoldM  :: IO (Maybe a) -> IO [a] #-}
    {-# SPECIALIZE unfoldM' :: (Monad m) => m (Maybe a) -> m [a] #-}
    {-# SPECIALIZE unfoldM' :: IO (Maybe a) -> IO [a] #-}
    {-# SPECIALIZE unfoldM_ :: IO (Maybe a) -> IO () #-}

    -- |The supplied "Maybe" expression will be repeatedly called until it
    -- returns 'Nothing'.  All values returned are collected into a list.
    unfoldM :: (Monad m) => m (Maybe a) -> m [a]
    unfoldM :: forall (m :: * -> *) a. Monad m => m (Maybe a) -> m [a]
    unfoldM = m (Maybe a) -> m [a]
    forall (m :: * -> *) (f :: * -> *) a.
    (Monad m, MonadPlus f) =>
    m (Maybe a) -> m (f a)
    unfoldM'

    -- |The supplied "Maybe" expression will be repeatedly called until it
    -- returns 'Nothing'.  All values returned are collected into an arbitrary
    -- 'MonadPlus' thing.
    unfoldM' :: (Monad m, MonadPlus f) => m (Maybe a) -> m (f a)
    unfoldM' :: forall (m :: * -> *) (f :: * -> *) a.
    (Monad m, MonadPlus f) =>
    m (Maybe a) -> m (f a)
    unfoldM' m (Maybe a)
    m = m (Maybe a) -> (a -> m a) -> m (f a)
    forall (m :: * -> *) (f :: * -> *) a b.
    (Monad m, MonadPlus f) =>
    m (Maybe a) -> (a -> m b) -> m (f b)
    whileJust' m (Maybe a)
    m a -> m a
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return

    -- |The supplied "Maybe" expression will be repeatedly called until it
    -- returns 'Nothing'.  All values returned are discarded.
    unfoldM_ :: (Monad m) => m (Maybe a) -> m ()
    unfoldM_ :: forall (m :: * -> *) a. Monad m => m (Maybe a) -> m ()
    unfoldM_ m (Maybe a)
    m = m (Maybe a) -> (a -> m a) -> m ()
    forall (m :: * -> *) a b.
    Monad m =>
    m (Maybe a) -> (a -> m b) -> m ()
    whileJust_ m (Maybe a)
    m a -> m a
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return

    -- |Repeatedly evaluates the second argument until the value satisfies
    -- the given predicate, and returns a list of all values that satisfied the
    -- predicate.  Discards the final one (which failed the predicate).
    unfoldWhileM :: Monad m => (a -> Bool) -> m a -> m [a]
    unfoldWhileM :: forall (m :: * -> *) a. Monad m => (a -> Bool) -> m a -> m [a]
    unfoldWhileM a -> Bool
    p m a
    m = ([a] -> [a]) -> m [a]
    forall {b}. ([a] -> b) -> m b
    loop [a] -> [a]
    forall a. a -> a
    id
        where
            loop :: ([a] -> b) -> m b
    loop [a] -> b
    f = do
                x <- m a
    m
                if p x
                    then loop (f . (x:))
                    else return (f [])

    -- |Repeatedly evaluates the second argument until the value satisfies
    -- the given predicate, and returns a 'MonadPlus' collection of all values
    -- that satisfied the predicate.  Discards the final one (which failed the predicate).
    unfoldWhileM' :: (Monad m, MonadPlus f) => (a -> Bool) -> m a -> m (f a)
    unfoldWhileM' :: forall (m :: * -> *) (f :: * -> *) a.
    (Monad m, MonadPlus f) =>
    (a -> Bool) -> m a -> m (f a)
    unfoldWhileM' a -> Bool
    p m a
    m = f a -> m (f a)
    forall {m :: * -> *}. MonadPlus m => m a -> m (m a)
    loop f a
    forall a. f a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero
        where
            loop :: m a -> m (m a)
    loop m a
    xs = do
                x <- m a
    m
                if p x
                    then loop (xs `mplus` return x)
                    else return xs

    {-# SPECIALIZE unfoldrM  :: (a -> IO (Maybe (b,a))) -> a -> IO [b] #-}
    {-# SPECIALIZE unfoldrM' :: (Monad m) => (a -> m (Maybe (b,a))) -> a -> m [b] #-}
    {-# SPECIALIZE unfoldrM' :: (a -> IO (Maybe (b,a))) -> a -> IO [b] #-}

    -- |See 'Data.List.unfoldr'.  This is a monad-friendly version of that.
    unfoldrM :: (Monad m) => (a -> m (Maybe (b,a))) -> a -> m [b]
    unfoldrM :: forall (m :: * -> *) a b.
    Monad m =>
    (a -> m (Maybe (b, a))) -> a -> m [b]
    unfoldrM = (a -> m (Maybe (b, a))) -> a -> m [b]
    forall (m :: * -> *) (f :: * -> *) a b.
    (Monad m, MonadPlus f) =>
    (a -> m (Maybe (b, a))) -> a -> m (f b)
    unfoldrM'

    -- |See 'Data.List.unfoldr'.  This is a monad-friendly version of that, with a
    -- twist.  Rather than returning a list, it returns any MonadPlus type of your
    -- choice.
    unfoldrM' :: (Monad m, MonadPlus f) => (a -> m (Maybe (b,a))) -> a -> m (f b)
    unfoldrM' :: forall (m :: * -> *) (f :: * -> *) a b.
    (Monad m, MonadPlus f) =>
    (a -> m (Maybe (b, a))) -> a -> m (f b)
    unfoldrM' a -> m (Maybe (b, a))
    f = a -> m (f b)
    forall {m :: * -> *}. MonadPlus m => a -> m (m b)
    go
        where go :: a -> m (m b)
    go a
    z = do
                x <- a -> m (Maybe (b, a))
    f a
    z
                case x of
                    Maybe (b, a)
    Nothing         -> m b -> m (m b)
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return m b
    forall a. m a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero
                    Just (b
    x, a
    z')    -> do
                            xs <- a -> m (m b)
    go a
    z'
                            return (return x `mplus` xs)

    {-# SPECIALIZE concatM :: [a -> IO a] -> (a -> IO a) #-}

    -- |Compose a list of monadic actions into one action.  Composes using
    -- ('>=>') - that is, the output of each action is fed to the input of
    -- the one after it in the list.
    concatM :: (Monad m) => [a -> m a] -> (a -> m a)
    concatM :: forall (m :: * -> *) a. Monad m => [a -> m a] -> a -> m a
    concatM [a -> m a]
    fs = ((a -> m a) -> (a -> m a) -> a -> m a)
    -> (a -> m a) -> [a -> m a] -> a -> m a
    forall a b. (a -> b -> b) -> b -> [a] -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr (a -> m a) -> (a -> m a) -> a -> m a
    forall (m :: * -> *) a b c.
    Monad m =>
    (a -> m b) -> (b -> m c) -> a -> m c
    (>=>) a -> m a
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return [a -> m a]
    fs

    {-# SPECIALIZE andM :: [IO Bool] -> IO Bool #-}
    {-# SPECIALIZE orM  :: [IO Bool] -> IO Bool #-}

    -- |short-circuit 'and' for values of type Monad m => m Bool
    andM :: (Monad m) => [m Bool] -> m Bool
    andM :: forall (m :: * -> *). Monad m => [m Bool] -> m Bool
    andM []         = Bool -> m Bool
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return Bool
    True
    andM (m Bool
    p:[m Bool]
    ps)     = do
            q <- m Bool
    p
            if q
                    then andM ps
                    else return False

    -- |short-circuit 'or' for values of type Monad m => m Bool
    orM :: (Monad m) => [m Bool] -> m Bool
    orM :: forall (m :: * -> *). Monad m => [m Bool] -> m Bool
    orM []          = Bool -> m Bool
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return Bool
    False
    orM (m Bool
    p:[m Bool]
    ps)      = do
            q <- m Bool
    p
            if q
                    then return True
                    else orM ps

    {-# SPECIALIZE anyPM :: [a -> IO Bool] -> (a -> IO Bool) #-}
    {-# SPECIALIZE allPM :: [a -> IO Bool] -> (a -> IO Bool) #-}

    -- |short-circuit 'any' with a list of \"monadic predicates\".  Tests the
    -- value presented against each predicate in turn until one passes, then
    -- returns True without any further processing.  If none passes, returns False.
    anyPM :: (Monad m) => [a -> m Bool] -> (a -> m Bool)
    anyPM :: forall (m :: * -> *) a. Monad m => [a -> m Bool] -> a -> m Bool
    anyPM []     a
    _ = Bool -> m Bool
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return Bool
    False
    anyPM (a -> m Bool
    p:[a -> m Bool]
    ps) a
    x = do
            q <- a -> m Bool
    p a
    x
            if q
                    then return True
                    else anyPM ps x

    -- |short-circuit 'all' with a list of \"monadic predicates\".  Tests the value
    -- presented against each predicate in turn until one fails, then returns False.
    -- if none fail, returns True.
    allPM :: (Monad m) => [a -> m Bool] -> (a -> m Bool)
    allPM :: forall (m :: * -> *) a. Monad m => [a -> m Bool] -> a -> m Bool
    allPM []     a
    _ = Bool -> m Bool
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return Bool
    True
    allPM (a -> m Bool
    p:[a -> m Bool]
    ps) a
    x = do
            q <- a -> m Bool
    p a
    x
            if q
                    then allPM ps x
                    else return False

    {-# SPECIALIZE anyM :: (a -> IO Bool) -> [a] -> IO Bool #-}
    {-# SPECIALIZE allM :: (a -> IO Bool) -> [a] -> IO Bool #-}

    -- |short-circuit 'any' with a \"monadic predicate\".
    anyM :: (Monad m) => (a -> m Bool) -> [a] -> m Bool
    anyM :: forall (m :: * -> *) a. Monad m => (a -> m Bool) -> [a] -> m Bool
    anyM a -> m Bool
    _ []       = Bool -> m Bool
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return Bool
    False
    anyM a -> m Bool
    p (a
    x:[a]
    xs)   = do
            q <- a -> m Bool
    p a
    x
            if q
                    then return True
                    else anyM p xs

    -- |short-circuit 'all' with a \"monadic predicate\".
    allM :: (Monad m) => (a -> m Bool) -> [a] -> m Bool
    allM :: forall (m :: * -> *) a. Monad m => (a -> m Bool) -> [a] -> m Bool
    allM a -> m Bool
    _ []       = Bool -> m Bool
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return Bool
    True
    allM a -> m Bool
    p (a
    x:[a]
    xs)   = do
            q <- a -> m Bool
    p a
    x
            if q
                    then allM p xs
                    else return False

    -- | Monadic 'takeWhile'.
    takeWhileM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
    takeWhileM :: forall (m :: * -> *) a. Monad m => (a -> m Bool) -> [a] -> m [a]
    takeWhileM a -> m Bool
    _ []     = [a] -> m [a]
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return []
    takeWhileM a -> m Bool
    p (a
    x:[a]
    xs) = do
            q <- a -> m Bool
    p a
    x
            if q
                    then (takeWhileM p xs) >>= (return . (:) x)
                    else return []

    -- | Monadic 'dropWhile'.
    dropWhileM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
    dropWhileM :: forall (m :: * -> *) a. Monad m => (a -> m Bool) -> [a] -> m [a]
    dropWhileM a -> m Bool
    _ []     = [a] -> m [a]
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return []
    dropWhileM a -> m Bool
    p (a
    x:[a]
    xs) = do
            q <- a -> m Bool
    p a
    x
            if q
                    then dropWhileM p xs
                    else return (x:xs)

    -- |like 'dropWhileM' but trims both ends of the list.
    trimM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
    trimM :: forall (m :: * -> *) a. Monad m => (a -> m Bool) -> [a] -> m [a]
    trimM a -> m Bool
    p [a]
    xs = do
            xs <- (a -> m Bool) -> [a] -> m [a]
    forall (m :: * -> *) a. Monad m => (a -> m Bool) -> [a] -> m [a]
    dropWhileM a -> m Bool
    p [a]
    xs
            rxs <- dropWhileM p (reverse xs)
            return (reverse rxs)

    -- |return the first value from a list, if any, satisfying the given predicate.
    firstM :: (Monad m) => (a -> m Bool) -> [a] -> m (Maybe a)
    firstM :: forall (m :: * -> *) a.
    Monad m =>
    (a -> m Bool) -> [a] -> m (Maybe a)
    firstM a -> m Bool
    _ [] = Maybe a -> m (Maybe a)
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return Maybe a
    forall a. Maybe a
    Nothing
    firstM a -> m Bool
    p (a
    x:[a]
    xs) = do
            q <- a -> m Bool
    p a
    x
            if q
                    then return (Just x)
                    else firstM p xs

    {-# INLINE minimaOnByM #-}
    minimaOnByM :: Monad m => (a -> m b) -> (b -> b -> m Ordering) -> [a] -> m [a]
    minimaOnByM :: forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> (b -> b -> m Ordering) -> [a] -> m [a]
    minimaOnByM a -> m b
    _   b -> b -> m Ordering
    _ []     = [a] -> m [a]
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return []
    minimaOnByM a -> m b
    f b -> b -> m Ordering
    cmp (a
    x:[a]
    xs) = do
        fx<- a -> m b
    f a
    x
        loop (x:) fx xs
            where   loop :: ([a] -> [a]) -> b -> [a] -> m [a]
    loop [a] -> [a]
    ms b
    _ []           = [a] -> m [a]
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ([a] -> [a]
    ms [])
                    loop [a] -> [a]
    ms b
    fm (a
    x:[a]
    xs) = do
                        fx  <- a -> m b
    f a
    x
                        ord <- cmp fm fx
                        case ord of
                            Ordering
    LT -> ([a] -> [a]) -> b -> [a] -> m [a]
    loop [a] -> [a]
    ms          b
    fm [a]
    xs
                            Ordering
    EQ -> ([a] -> [a]) -> b -> [a] -> m [a]
    loop ([a] -> [a]
    ms ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a
    xa -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :)) b
    fm [a]
    xs
                            Ordering
    GT -> ([a] -> [a]) -> b -> [a] -> m [a]
    loop (a
    xa -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :)        b
    fx [a]
    xs

    {-# INLINE maximaOnByM #-}
    maximaOnByM :: Monad m => (a -> m b) -> (b -> b -> m Ordering) -> [a] -> m [a]
    maximaOnByM :: forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> (b -> b -> m Ordering) -> [a] -> m [a]
    maximaOnByM a -> m b
    f = (a -> m b) -> (b -> b -> m Ordering) -> [a] -> m [a]
    forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> (b -> b -> m Ordering) -> [a] -> m [a]
    minimaOnByM a -> m b
    f ((b -> b -> m Ordering) -> [a] -> m [a])
    -> ((b -> b -> m Ordering) -> b -> b -> m Ordering)
    -> (b -> b -> m Ordering)
    -> [a]
    -> m [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (b -> b -> m Ordering) -> b -> b -> m Ordering
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip

    minimaByM :: Monad m => (a -> a -> m Ordering) -> [a] -> m [a]
    minimaByM :: forall (m :: * -> *) a.
    Monad m =>
    (a -> a -> m Ordering) -> [a] -> m [a]
    minimaByM = (a -> m a) -> (a -> a -> m Ordering) -> [a] -> m [a]
    forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> (b -> b -> m Ordering) -> [a] -> m [a]
    minimaOnByM a -> m a
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return

    maximaByM :: Monad m => (a -> a -> m Ordering) -> [a] -> m [a]
    maximaByM :: forall (m :: * -> *) a.
    Monad m =>
    (a -> a -> m Ordering) -> [a] -> m [a]
    maximaByM = (a -> m a) -> (a -> a -> m Ordering) -> [a] -> m [a]
    forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> (b -> b -> m Ordering) -> [a] -> m [a]
    maximaOnByM a -> m a
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return

    minimaOnM :: (Monad m, Ord b) => (a -> m b) -> [a] -> m [a]
    minimaOnM :: forall (m :: * -> *) b a.
    (Monad m, Ord b) =>
    (a -> m b) -> [a] -> m [a]
    minimaOnM a -> m b
    f = (a -> m b) -> (b -> b -> m Ordering) -> [a] -> m [a]
    forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> (b -> b -> m Ordering) -> [a] -> m [a]
    minimaOnByM a -> m b
    f (\b
    x b
    y -> Ordering -> m Ordering
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (b -> b -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare b
    x b
    y))

    maximaOnM :: (Monad m, Ord b) => (a -> m b) -> [a] -> m [a]
    maximaOnM :: forall (m :: * -> *) b a.
    (Monad m, Ord b) =>
    (a -> m b) -> [a] -> m [a]
    maximaOnM a -> m b
    f = (a -> m b) -> (b -> b -> m Ordering) -> [a] -> m [a]
    forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> (b -> b -> m Ordering) -> [a] -> m [a]
    maximaOnByM a -> m b
    f (\b
    x b
    y -> Ordering -> m Ordering
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (b -> b -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare b
    x b
    y))

    {-# INLINE minimumOnByM #-}
    minimumOnByM :: Monad m => (a -> m b) -> (b -> b -> m Ordering) -> [a] -> m (Maybe a)
    minimumOnByM :: forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> (b -> b -> m Ordering) -> [a] -> m (Maybe a)
    minimumOnByM a -> m b
    _   b -> b -> m Ordering
    _ []     = Maybe a -> m (Maybe a)
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return Maybe a
    forall a. Maybe a
    Nothing
    minimumOnByM a -> m b
    f b -> b -> m Ordering
    cmp (a
    x:[a]
    xs) = do
        fx <- a -> m b
    f a
    x
        loop x fx xs
            where   loop :: a -> b -> [a] -> m (Maybe a)
    loop a
    m b
    _ []           = Maybe a -> m (Maybe a)
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (a -> Maybe a
    forall a. a -> Maybe a
    Just a
    m)
                    loop a
    m b
    fm (a
    x:[a]
    xs) = do
                        fx  <- a -> m b
    f a
    x
                        ord <- cmp fm fx
                        case ord of
                            Ordering
    LT -> a -> b -> [a] -> m (Maybe a)
    loop a
    m b
    fm [a]
    xs
                            Ordering
    EQ -> a -> b -> [a] -> m (Maybe a)
    loop a
    m b
    fm [a]
    xs
                            Ordering
    GT -> a -> b -> [a] -> m (Maybe a)
    loop a
    x b
    fx [a]
    xs

    {-# INLINE maximumOnByM #-}
    maximumOnByM :: Monad m => (a -> m b) -> (b -> b -> m Ordering) -> [a] -> m (Maybe a)
    maximumOnByM :: forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> (b -> b -> m Ordering) -> [a] -> m (Maybe a)
    maximumOnByM a -> m b
    f = (a -> m b) -> (b -> b -> m Ordering) -> [a] -> m (Maybe a)
    forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> (b -> b -> m Ordering) -> [a] -> m (Maybe a)
    minimumOnByM a -> m b
    f ((b -> b -> m Ordering) -> [a] -> m (Maybe a))
    -> ((b -> b -> m Ordering) -> b -> b -> m Ordering)
    -> (b -> b -> m Ordering)
    -> [a]
    -> m (Maybe a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (b -> b -> m Ordering) -> b -> b -> m Ordering
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip

    minimumByM :: Monad m => (a -> a -> m Ordering) -> [a] -> m (Maybe a)
    minimumByM :: forall (m :: * -> *) a.
    Monad m =>
    (a -> a -> m Ordering) -> [a] -> m (Maybe a)
    minimumByM = (a -> m a) -> (a -> a -> m Ordering) -> [a] -> m (Maybe a)
    forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> (b -> b -> m Ordering) -> [a] -> m (Maybe a)
    minimumOnByM a -> m a
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return

    maximumByM :: Monad m => (a -> a -> m Ordering) -> [a] -> m (Maybe a)
    maximumByM :: forall (m :: * -> *) a.
    Monad m =>
    (a -> a -> m Ordering) -> [a] -> m (Maybe a)
    maximumByM = (a -> m a) -> (a -> a -> m Ordering) -> [a] -> m (Maybe a)
    forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> (b -> b -> m Ordering) -> [a] -> m (Maybe a)
    maximumOnByM a -> m a
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return

    minimumOnM :: (Monad m, Ord b) => (a -> m b) -> [a] -> m (Maybe a)
    minimumOnM :: forall (m :: * -> *) b a.
    (Monad m, Ord b) =>
    (a -> m b) -> [a] -> m (Maybe a)
    minimumOnM a -> m b
    f = (a -> m b) -> (b -> b -> m Ordering) -> [a] -> m (Maybe a)
    forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> (b -> b -> m Ordering) -> [a] -> m (Maybe a)
    minimumOnByM a -> m b
    f (\b
    x b
    y -> Ordering -> m Ordering
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (b -> b -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare b
    x b
    y))

    maximumOnM :: (Monad m, Ord b) => (a -> m b) -> [a] -> m (Maybe a)
    maximumOnM :: forall (m :: * -> *) b a.
    (Monad m, Ord b) =>
    (a -> m b) -> [a] -> m (Maybe a)
    maximumOnM a -> m b
    f = (a -> m b) -> (b -> b -> m Ordering) -> [a] -> m (Maybe a)
    forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> (b -> b -> m Ordering) -> [a] -> m (Maybe a)
    maximumOnByM a -> m b
    f (\b
    x b
    y -> Ordering -> m Ordering
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (b -> b -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare b
    x b
    y))