    -----------------------------------------------------------------------------
    --
    -- Module      :  Control.Monad.ListM
    -- Copyright   :
    -- License     :  AllRightsReserved
    --
    -- Maintainer  :
    -- Stability   :
    -- Portability :
    --
    -- |
    --
    -----------------------------------------------------------------------------

    module Control.Monad.ListM (
      mapMP
    , filterMP
    , intersperseM
    , intercalateM
    , foldM1
    , joinMap
    , joinMapM
    , anyM
    , allM
    , scanM
    , mapAccumM
    , iterateM
    , takeM
    , dropM
    , splitAtM
    , takeWhileM
    , dropWhileM
    , spanM
    , breakM
    , elemM
    , notElemM
    , lookupM
    , findM
    , partitionM
    , elemIndexM
    , elemIndicesM
    , findIndexM
    , findIndicesM
    , zipWithM3
    , zipWithM4
    , zipWithM5
    , zipWithM6
    , nubM
    , nubByM
    , deleteM
    , deleteByM
    , deleteFirstsM
    , deleteFirstsByM
    , unionM
    , unionByM
    , intersectM
    , intersectByM
    , groupM
    , groupByM
    , sortM
    , sortByM
    , insertM
    , insertByM
    , maximumM
    , maximumByM
    , minimumM
    , minimumByM
    ) where

    import qualified Prelude
    import Prelude hiding (error, mapM, sequence, and, or)

    import Control.Monad hiding (mapM, sequence)
    import Data.Foldable (or, and)
    import Data.List (zip4, zip5, zip6)
    import Data.Maybe (isJust)
    import Data.Traversable (Traversable, mapM, sequence)

    infixr 5 !, !!!

    error :: String -> String -> a
    error :: forall a. String -> String -> a
    error String
    func String
    msg = String -> a
    forall a. HasCallStack => String -> a
    Prelude.error (String -> a) -> String -> a
    forall a b. (a -> b) -> a -> b
    $ String
    "Control.Monad.ListM." String -> String -> String
    forall a. [a] -> [a] -> [a]
    ++ String
    func String -> String -> String
    forall a. [a] -> [a] -> [a]
    ++ String
    ": " String -> String -> String
    forall a. [a] -> [a] -> [a]
    ++ String
    msg

    notM :: (Monad m) => Bool -> m Bool
    notM :: forall (m :: * -> *). Monad m => Bool -> m Bool
    notM = Bool -> m Bool
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (Bool -> m Bool) -> (Bool -> Bool) -> Bool -> m Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Bool -> Bool
    not

    eqM :: (Eq a, Monad m) => a -> a -> m Bool
    eqM :: forall a (m :: * -> *). (Eq a, Monad m) => a -> a -> m Bool
    eqM a
    x a
    y = Bool -> m Bool
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (Bool -> m Bool) -> Bool -> m Bool
    forall a b. (a -> b) -> a -> b
    $ a
    x a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == a
    y

    compareM :: (Ord a, Monad m) => a -> a -> m Ordering
    compareM :: forall a (m :: * -> *). (Ord a, Monad m) => a -> a -> m Ordering
    compareM a
    x a
    y = Ordering -> m Ordering
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (Ordering -> m Ordering) -> Ordering -> m Ordering
    forall a b. (a -> b) -> a -> b
    $ a -> a -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare a
    x a
    y

    (!) :: (MonadPlus p) => a -> p a -> p a
    a
    x ! :: forall (p :: * -> *) a. MonadPlus p => a -> p a -> p a
    ! p a
    y = a -> p a
    forall a. a -> p a
    forall (m :: * -> *) a. Monad m => a -> m a
    return a
    x p a -> p a -> p a
    forall a. p a -> p a -> p a
    forall (m :: * -> *) a. MonadPlus m => m a -> m a -> m a
    `mplus` p a
    y

    (!!!) :: (MonadPlus p) => [a] -> p a -> p a
    !!! :: forall (p :: * -> *) a. MonadPlus p => [a] -> p a -> p a
    (!!!) = (p a -> [a] -> p a) -> [a] -> p a -> p a
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip ((p a -> [a] -> p a) -> [a] -> p a -> p a)
    -> (p a -> [a] -> p a) -> [a] -> p a -> p a
    forall a b. (a -> b) -> a -> b
    $ (a -> p a -> p a) -> p a -> [a] -> p 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 -> p a -> p a
    forall (p :: * -> *) a. MonadPlus p => a -> p a -> p a
    (!)

    uncurry3 :: (a -> b -> c -> d) -> ((a, b, c) -> d)
    uncurry3 :: forall a b c d. (a -> b -> c -> d) -> (a, b, c) -> d
    uncurry3 a -> b -> c -> d
    f (a
    x, b
    y, c
    z) = a -> b -> c -> d
    f a
    x b
    y c
    z

    uncurry4 :: (a -> b -> c -> d -> e) -> ((a, b, c, d) -> e)
    uncurry4 :: forall a b c d e. (a -> b -> c -> d -> e) -> (a, b, c, d) -> e
    uncurry4 a -> b -> c -> d -> e
    f (a
    x, b
    y, c
    z, d
    w) = a -> b -> c -> d -> e
    f a
    x b
    y c
    z d
    w

    uncurry5 :: (a -> b -> c -> d -> e -> f) -> ((a, b, c, d, e) -> f)
    uncurry5 :: forall a b c d e f.
    (a -> b -> c -> d -> e -> f) -> (a, b, c, d, e) -> f
    uncurry5 a -> b -> c -> d -> e -> f
    f (a
    x, b
    y, c
    z, d
    w, e
    s) = a -> b -> c -> d -> e -> f
    f a
    x b
    y c
    z d
    w e
    s

    uncurry6 :: (a -> b -> c -> d -> e -> f -> g) -> ((a, b, c, d, e, f) -> g)
    uncurry6 :: forall a b c d e f g.
    (a -> b -> c -> d -> e -> f -> g) -> (a, b, c, d, e, f) -> g
    uncurry6 a -> b -> c -> d -> e -> f -> g
    f (a
    x, b
    y, c
    z, d
    w, e
    s, f
    t) = a -> b -> c -> d -> e -> f -> g
    f a
    x b
    y c
    z d
    w e
    s f
    t

    mapMP :: (Monad m, MonadPlus p) => (a -> m b) -> [a] -> m (p b)
    mapMP :: forall (m :: * -> *) (p :: * -> *) a b.
    (Monad m, MonadPlus p) =>
    (a -> m b) -> [a] -> m (p b)
    mapMP a -> m b
    _ [] = p b -> m (p b)
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return p b
    forall a. p a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero
    mapMP a -> m b
    f (a
    x:[a]
    xs) = do
      y <- a -> m b
    f a
    x
      liftM (y!) $ mapMP f xs

    filterMP :: (Monad m, MonadPlus p) => (a -> m Bool) -> [a] -> m (p a)
    filterMP :: forall (m :: * -> *) (p :: * -> *) a.
    (Monad m, MonadPlus p) =>
    (a -> m Bool) -> [a] -> m (p a)
    filterMP a -> m Bool
    _ [] = p a -> m (p a)
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return p a
    forall a. p a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero
    filterMP a -> m Bool
    p (a
    x:[a]
    xs) = do
      bool <- a -> m Bool
    p a
    x
      if bool
        then liftM (x!) $ filterMP p xs
        else filterMP p xs

    intersperseM :: (Monad m, MonadPlus p) => m a -> [a] -> m (p a)
    intersperseM :: forall (m :: * -> *) (p :: * -> *) a.
    (Monad m, MonadPlus p) =>
    m a -> [a] -> m (p a)
    intersperseM m a
    _ [] = p a -> m (p a)
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return p a
    forall a. p a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero
    intersperseM m a
    _ [a
    x] = p a -> m (p a)
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (p a -> m (p a)) -> p a -> m (p a)
    forall a b. (a -> b) -> a -> b
    $ a -> p a
    forall a. a -> p a
    forall (m :: * -> *) a. Monad m => a -> m a
    return a
    x
    intersperseM m a
    m (a
    x:[a]
    ys) = do
      z <- m a
    m
      liftM ([x, z] !!!) $ intersperseM m ys

    intercalateM :: (Monad m, MonadPlus p) => m (p a) -> [p a] -> m (p a)
    intercalateM :: forall (m :: * -> *) (p :: * -> *) a.
    (Monad m, MonadPlus p) =>
    m (p a) -> [p a] -> m (p a)
    intercalateM m (p a)
    m = (p (p a) -> p a) -> m (p (p a)) -> m (p a)
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM p (p a) -> p a
    forall (m :: * -> *) a. Monad m => m (m a) -> m a
    join (m (p (p a)) -> m (p a))
    -> ([p a] -> m (p (p a))) -> [p a] -> m (p a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . m (p a) -> [p a] -> m (p (p a))
    forall (m :: * -> *) (p :: * -> *) a.
    (Monad m, MonadPlus p) =>
    m a -> [a] -> m (p a)
    intersperseM m (p a)
    m

    foldM1 :: (Monad m) => (a -> a -> m a) -> [a] -> m a
    foldM1 :: forall (m :: * -> *) a. Monad m => (a -> a -> m a) -> [a] -> m a
    foldM1 a -> a -> m a
    _ [] = String -> String -> m a
    forall a. String -> String -> a
    error String
    "foldM1" String
    "empty list"
    foldM1 a -> a -> m a
    f (a
    x:[a]
    xs) = (a -> a -> m a) -> a -> [a] -> m a
    forall (t :: * -> *) (m :: * -> *) b a.
    (Foldable t, Monad m) =>
    (b -> a -> m b) -> b -> t a -> m b
    foldM a -> a -> m a
    f a
    x [a]
    xs

    joinMap :: (Monad m) => (a -> m b) -> m a -> m b
    joinMap :: forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
    joinMap a -> m b
    f = m (m b) -> m b
    forall (m :: * -> *) a. Monad m => m (m a) -> m a
    join (m (m b) -> m b) -> (m a -> m (m b)) -> m a -> m b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> m b) -> m a -> m (m b)
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM a -> m b
    f

    joinMapM :: (Monad m, MonadPlus p) => (a -> m (p b)) -> [a] -> m (p b)
    joinMapM :: forall (m :: * -> *) (p :: * -> *) a b.
    (Monad m, MonadPlus p) =>
    (a -> m (p b)) -> [a] -> m (p b)
    joinMapM a -> m (p b)
    f = (p (p b) -> p b) -> m (p (p b)) -> m (p b)
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM p (p b) -> p b
    forall (m :: * -> *) a. Monad m => m (m a) -> m a
    join (m (p (p b)) -> m (p b)) -> ([a] -> m (p (p b))) -> [a] -> m (p b)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> m (p b)) -> [a] -> m (p (p b))
    forall (m :: * -> *) (p :: * -> *) a b.
    (Monad m, MonadPlus p) =>
    (a -> m b) -> [a] -> m (p b)
    mapMP a -> m (p b)
    f

    anyM :: (Monad m, Traversable t) => (a -> m Bool) -> t a -> m Bool
    anyM :: forall (m :: * -> *) (t :: * -> *) a.
    (Monad m, Traversable t) =>
    (a -> m Bool) -> t a -> m Bool
    anyM a -> m Bool
    p = (t Bool -> Bool) -> m (t Bool) -> m Bool
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM t Bool -> Bool
    forall (t :: * -> *). Foldable t => t Bool -> Bool
    or (m (t Bool) -> m Bool) -> (t a -> m (t Bool)) -> t a -> m Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> m Bool) -> t a -> m (t Bool)
    forall (t :: * -> *) (m :: * -> *) a b.
    (Traversable t, Monad m) =>
    (a -> m b) -> t a -> m (t b)
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> t a -> m (t b)
    mapM a -> m Bool
    p

    allM :: (Monad m, Traversable t) => (a -> m Bool) -> t a -> m Bool
    allM :: forall (m :: * -> *) (t :: * -> *) a.
    (Monad m, Traversable t) =>
    (a -> m Bool) -> t a -> m Bool
    allM a -> m Bool
    p = (t Bool -> Bool) -> m (t Bool) -> m Bool
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM t Bool -> Bool
    forall (t :: * -> *). Foldable t => t Bool -> Bool
    and (m (t Bool) -> m Bool) -> (t a -> m (t Bool)) -> t a -> m Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> m Bool) -> t a -> m (t Bool)
    forall (t :: * -> *) (m :: * -> *) a b.
    (Traversable t, Monad m) =>
    (a -> m b) -> t a -> m (t b)
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> t a -> m (t b)
    mapM a -> m Bool
    p

    scanM :: (Monad m, MonadPlus p) => (a -> b -> m a) -> a -> [b] -> m (p a)
    scanM :: forall (m :: * -> *) (p :: * -> *) a b.
    (Monad m, MonadPlus p) =>
    (a -> b -> m a) -> a -> [b] -> m (p a)
    scanM a -> b -> m a
    _ a
    z [] =  p a -> m (p a)
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (p a -> m (p a)) -> p a -> m (p a)
    forall a b. (a -> b) -> a -> b
    $ a -> p a
    forall a. a -> p a
    forall (m :: * -> *) a. Monad m => a -> m a
    return a
    z
    scanM a -> b -> m a
    f a
    z (b
    x:[b]
    xs) = do
      z' <- a -> b -> m a
    f a
    z b
    x
      liftM (z!) $ scanM f z' xs

    mapAccumM :: (Monad m, MonadPlus p) => (acc -> x -> m (acc, y)) -> acc -> [x] -> m (acc, p y)
    mapAccumM :: forall (m :: * -> *) (p :: * -> *) acc x y.
    (Monad m, MonadPlus p) =>
    (acc -> x -> m (acc, y)) -> acc -> [x] -> m (acc, p y)
    mapAccumM acc -> x -> m (acc, y)
    _ acc
    z [] = (acc, p y) -> m (acc, p y)
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (acc
    z, p y
    forall a. p a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero)
    mapAccumM acc -> x -> m (acc, y)
    f acc
    z (x
    x:[x]
    xs) = do
      (z', y) <- acc -> x -> m (acc, y)
    f acc
    z x
    x
      (z'', ys) <- mapAccumM f z' xs
      return (z'', y!ys)

    iterateM :: (Monad m, MonadPlus p) => (a -> m a) -> a -> m (p a)
    iterateM :: forall (m :: * -> *) (p :: * -> *) a.
    (Monad m, MonadPlus p) =>
    (a -> m a) -> a -> m (p a)
    iterateM a -> m a
    f a
    x = do
      x' <- a -> m a
    f a
    x
      liftM (x!) $ iterateM f x'

    takeM :: (Integral i, Monad m, MonadPlus p) => i -> [m a] -> m (p a)
    takeM :: forall i (m :: * -> *) (p :: * -> *) a.
    (Integral i, Monad m, MonadPlus p) =>
    i -> [m a] -> m (p a)
    takeM i
    _ [] = p a -> m (p a)
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return p a
    forall a. p a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero
    takeM i
    n (m a
    m:[m a]
    ms)
      | i
    n i -> i -> Bool
    forall a. Ord a => a -> a -> Bool
    <= i
    0 = p a -> m (p a)
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return p a
    forall a. p a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero
      | Bool
    otherwise = m a
    m m a -> (a -> m (p a)) -> m (p 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 -> (p a -> p a) -> m (p a) -> m (p a)
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM (a
    xa -> p a -> p a
    forall (p :: * -> *) a. MonadPlus p => a -> p a -> p a
    !) (m (p a) -> m (p a)) -> m (p a) -> m (p a)
    forall a b. (a -> b) -> a -> b
    $ i -> [m a] -> m (p a)
    forall i (m :: * -> *) (p :: * -> *) a.
    (Integral i, Monad m, MonadPlus p) =>
    i -> [m a] -> m (p a)
    takeM (i
    ni -> i -> i
    forall a. Num a => a -> a -> a
    -i
    1) [m a]
    ms

    dropM :: (Integral i, Monad m) => i -> [m a] -> m [a]
    dropM :: forall i (m :: * -> *) a.
    (Integral i, Monad m) =>
    i -> [m a] -> m [a]
    dropM i
    _ [] = [a] -> m [a]
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return []
    dropM i
    n (m a
    m:[m a]
    ms)
      | i
    n i -> i -> Bool
    forall a. Ord a => a -> a -> Bool
    <= i
    0 = [m a] -> m [a]
    forall (t :: * -> *) (m :: * -> *) a.
    (Traversable t, Monad m) =>
    t (m a) -> m (t a)
    forall (m :: * -> *) a. Monad m => [m a] -> m [a]
    sequence ([m a] -> m [a]) -> [m a] -> m [a]
    forall a b. (a -> b) -> a -> b
    $ m a
    mm a -> [m a] -> [m a]
    forall a. a -> [a] -> [a]
    :[m a]
    ms
      | Bool
    otherwise = m a
    m m a -> 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
    >> i -> [m a] -> m [a]
    forall i (m :: * -> *) a.
    (Integral i, Monad m) =>
    i -> [m a] -> m [a]
    dropM (i
    ni -> i -> i
    forall a. Num a => a -> a -> a
    -i
    1) [m a]
    ms

    splitAtM :: (Integral i, Monad m, MonadPlus p) => i -> [m a] -> m (p a, [a])
    splitAtM :: forall i (m :: * -> *) (p :: * -> *) a.
    (Integral i, Monad m, MonadPlus p) =>
    i -> [m a] -> m (p a, [a])
    splitAtM i
    _ [] = (p a, [a]) -> m (p a, [a])
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (p a
    forall a. p a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero, [])
    splitAtM i
    n (m a
    m:[m a]
    ms)
      | i
    n i -> i -> Bool
    forall a. Ord a => a -> a -> Bool
    <= i
    0 = do
          ys <- [m a] -> m [a]
    forall (t :: * -> *) (m :: * -> *) a.
    (Traversable t, Monad m) =>
    t (m a) -> m (t a)
    forall (m :: * -> *) a. Monad m => [m a] -> m [a]
    sequence ([m a] -> m [a]) -> [m a] -> m [a]
    forall a b. (a -> b) -> a -> b
    $ m a
    mm a -> [m a] -> [m a]
    forall a. a -> [a] -> [a]
    :[m a]
    ms
          return (mzero, ys)
      | Bool
    otherwise = do
          x <- m a
    m
          (xs, ys) <- splitAtM (n-1) ms
          return (x!xs, ys)

    takeWhileM :: (Monad m, MonadPlus p) => (a -> m Bool) -> [a] -> m (p a)
    takeWhileM :: forall (m :: * -> *) (p :: * -> *) a.
    (Monad m, MonadPlus p) =>
    (a -> m Bool) -> [a] -> m (p a)
    takeWhileM a -> m Bool
    _ [] = p a -> m (p a)
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return p a
    forall a. p a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero
    takeWhileM a -> m Bool
    p (a
    x:[a]
    xs) = do
      bool <- a -> m Bool
    p a
    x
      if bool
        then liftM (x!) $ takeWhileM p xs
        else return mzero

    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
      bool <- a -> m Bool
    p a
    x
      if bool
        then dropWhileM p xs
        else return $ x:xs

    spanM :: (Monad m, MonadPlus p) => (a -> m Bool) -> [a] -> m (p a, [a])
    spanM :: forall (m :: * -> *) (p :: * -> *) a.
    (Monad m, MonadPlus p) =>
    (a -> m Bool) -> [a] -> m (p a, [a])
    spanM a -> m Bool
    _ [] = (p a, [a]) -> m (p a, [a])
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (p a
    forall a. p a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero, [])
    spanM a -> m Bool
    p (a
    x:[a]
    xs) = do
      bool <- a -> m Bool
    p a
    x
      if bool
        then do
          (ys, zs) <- spanM p xs
          return (x!ys, zs)
        else return (mzero, x:xs)

    breakM :: (Monad m, MonadPlus p) => (a -> m Bool) -> [a] -> m (p a, [a])
    breakM :: forall (m :: * -> *) (p :: * -> *) a.
    (Monad m, MonadPlus p) =>
    (a -> m Bool) -> [a] -> m (p a, [a])
    breakM a -> m Bool
    p = (a -> m Bool) -> [a] -> m (p a, [a])
    forall (m :: * -> *) (p :: * -> *) a.
    (Monad m, MonadPlus p) =>
    (a -> m Bool) -> [a] -> m (p a, [a])
    spanM ((a -> m Bool) -> [a] -> m (p a, [a]))
    -> (a -> m Bool) -> [a] -> m (p a, [a])
    forall a b. (a -> b) -> a -> b
    $ Bool -> m Bool
    forall (m :: * -> *). Monad m => Bool -> m Bool
    notM (Bool -> m Bool) -> (a -> m Bool) -> a -> m Bool
    forall (m :: * -> *) b c a.
    Monad m =>
    (b -> m c) -> (a -> m b) -> a -> m c
    <=< a -> m Bool
    p

    elemM :: (Eq a, Monad m) => a -> [a] -> m Bool
    elemM :: forall a (m :: * -> *). (Eq a, Monad m) => a -> [a] -> m Bool
    elemM a
    x [a]
    xs = do
      idx <- a -> [a] -> m (Maybe Int)
    forall a i (m :: * -> *) (p :: * -> *).
    (Eq a, Integral i, Monad m, MonadPlus p) =>
    a -> [a] -> m (p i)
    elemIndexM a
    x [a]
    xs
      let _ = idx :: Maybe Int
      return $ isJust idx

    notElemM :: (Eq a, Monad m) => a -> [a] -> m Bool
    notElemM :: forall a (m :: * -> *). (Eq a, Monad m) => a -> [a] -> m Bool
    notElemM a
    x = Bool -> m Bool
    forall (m :: * -> *). Monad m => Bool -> m Bool
    notM (Bool -> m Bool) -> ([a] -> m Bool) -> [a] -> m Bool
    forall (m :: * -> *) b c a.
    Monad m =>
    (b -> m c) -> (a -> m b) -> a -> m c
    <=< a -> [a] -> m Bool
    forall a (m :: * -> *). (Eq a, Monad m) => a -> [a] -> m Bool
    elemM a
    x

    lookupM :: (Eq a, Monad m, MonadPlus p) => a -> [m (a, b)] -> m (p b)
    lookupM :: forall a (m :: * -> *) (p :: * -> *) b.
    (Eq a, Monad m, MonadPlus p) =>
    a -> [m (a, b)] -> m (p b)
    lookupM a
    _ [] = p b -> m (p b)
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return p b
    forall a. p a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero
    lookupM a
    x (m (a, b)
    m:[m (a, b)]
    ms) = do
      (k, v) <- m (a, b)
    m
      if x == k
        then return $ return v
        else lookupM x ms

    findM :: (Monad m, MonadPlus p) => (a -> m Bool) -> [a] -> m (p a)
    findM :: forall (m :: * -> *) (p :: * -> *) a.
    (Monad m, MonadPlus p) =>
    (a -> m Bool) -> [a] -> m (p a)
    findM a -> m Bool
    _ [] = p a -> m (p a)
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return p a
    forall a. p a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero
    findM a -> m Bool
    p (a
    x:[a]
    xs) = do
      bool <- a -> m Bool
    p a
    x
      if bool
        then return $ return x
        else findM p xs

    partitionM :: (Monad m, MonadPlus p) => (a -> m Bool) -> [a] -> m (p a, [a])
    partitionM :: forall (m :: * -> *) (p :: * -> *) a.
    (Monad m, MonadPlus p) =>
    (a -> m Bool) -> [a] -> m (p a, [a])
    partitionM a -> m Bool
    _ [] = (p a, [a]) -> m (p a, [a])
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (p a
    forall a. p a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero, [])
    partitionM a -> m Bool
    p (a
    x:[a]
    xs) = do
      bool <- a -> m Bool
    p a
    x
      if bool
        then do
          (ys, zs) <- partitionM p xs
          return (x!ys, zs)
        else return (mzero, x:xs)

    elemIndexM :: (Eq a, Integral i, Monad m, MonadPlus p) => a -> [a] -> m (p i)
    elemIndexM :: forall a i (m :: * -> *) (p :: * -> *).
    (Eq a, Integral i, Monad m, MonadPlus p) =>
    a -> [a] -> m (p i)
    elemIndexM a
    x = (a -> m Bool) -> [a] -> m (p i)
    forall i (m :: * -> *) (p :: * -> *) a.
    (Integral i, Monad m, MonadPlus p) =>
    (a -> m Bool) -> [a] -> m (p i)
    findIndexM ((a -> m Bool) -> [a] -> m (p i))
    -> (a -> m Bool) -> [a] -> m (p i)
    forall a b. (a -> b) -> a -> b
    $ a -> a -> m Bool
    forall a (m :: * -> *). (Eq a, Monad m) => a -> a -> m Bool
    eqM a
    x

    elemIndicesM :: (Eq a, Integral i, Monad m, MonadPlus p) => a -> [a] -> m (p i)
    elemIndicesM :: forall a i (m :: * -> *) (p :: * -> *).
    (Eq a, Integral i, Monad m, MonadPlus p) =>
    a -> [a] -> m (p i)
    elemIndicesM a
    x = (a -> m Bool) -> [a] -> m (p i)
    forall i (m :: * -> *) (p :: * -> *) a.
    (Integral i, Monad m, MonadPlus p) =>
    (a -> m Bool) -> [a] -> m (p i)
    findIndicesM ((a -> m Bool) -> [a] -> m (p i))
    -> (a -> m Bool) -> [a] -> m (p i)
    forall a b. (a -> b) -> a -> b
    $ a -> a -> m Bool
    forall a (m :: * -> *). (Eq a, Monad m) => a -> a -> m Bool
    eqM a
    x

    findIndexM :: (Integral i, Monad m, MonadPlus p) => (a -> m Bool) -> [a] -> m (p i)
    findIndexM :: forall i (m :: * -> *) (p :: * -> *) a.
    (Integral i, Monad m, MonadPlus p) =>
    (a -> m Bool) -> [a] -> m (p i)
    findIndexM a -> m Bool
    p = (p (i, a) -> p i) -> m (p (i, a)) -> m (p i)
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM (((i, a) -> i) -> p (i, a) -> p i
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM (i, a) -> i
    forall a b. (a, b) -> a
    fst) (m (p (i, a)) -> m (p i))
    -> ([a] -> m (p (i, a))) -> [a] -> m (p i)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ((i, a) -> m Bool) -> [(i, a)] -> m (p (i, a))
    forall (m :: * -> *) (p :: * -> *) a.
    (Monad m, MonadPlus p) =>
    (a -> m Bool) -> [a] -> m (p a)
    findM (a -> m Bool
    p (a -> m Bool) -> ((i, a) -> a) -> (i, a) -> m Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (i, a) -> a
    forall a b. (a, b) -> b
    snd) ([(i, a)] -> m (p (i, a)))
    -> ([a] -> [(i, a)]) -> [a] -> m (p (i, a))
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [i] -> [a] -> [(i, a)]
    forall a b. [a] -> [b] -> [(a, b)]
    zip [i
    0..]

    findIndicesM :: (Integral i, Monad m, MonadPlus p) => (a -> m Bool) -> [a] -> m (p i)
    findIndicesM :: forall i (m :: * -> *) (p :: * -> *) a.
    (Integral i, Monad m, MonadPlus p) =>
    (a -> m Bool) -> [a] -> m (p i)
    findIndicesM a -> m Bool
    p = (p (i, a) -> p i) -> m (p (i, a)) -> m (p i)
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM (((i, a) -> i) -> p (i, a) -> p i
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM (i, a) -> i
    forall a b. (a, b) -> a
    fst) (m (p (i, a)) -> m (p i))
    -> ([a] -> m (p (i, a))) -> [a] -> m (p i)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ((i, a) -> m Bool) -> [(i, a)] -> m (p (i, a))
    forall (m :: * -> *) (p :: * -> *) a.
    (Monad m, MonadPlus p) =>
    (a -> m Bool) -> [a] -> m (p a)
    filterMP (a -> m Bool
    p (a -> m Bool) -> ((i, a) -> a) -> (i, a) -> m Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (i, a) -> a
    forall a b. (a, b) -> b
    snd) ([(i, a)] -> m (p (i, a)))
    -> ([a] -> [(i, a)]) -> [a] -> m (p (i, a))
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [i] -> [a] -> [(i, a)]
    forall a b. [a] -> [b] -> [(a, b)]
    zip [i
    0..]

    zipWithM3 :: (Monad m, MonadPlus p) => (a -> b -> c -> m d) -> [a] -> [b] -> [c] -> m (p d)
    zipWithM3 :: forall (m :: * -> *) (p :: * -> *) a b c d.
    (Monad m, MonadPlus p) =>
    (a -> b -> c -> m d) -> [a] -> [b] -> [c] -> m (p d)
    zipWithM3 a -> b -> c -> m d
    f [a]
    xs [b]
    ys = ((a, b, c) -> m d) -> [(a, b, c)] -> m (p d)
    forall (m :: * -> *) (p :: * -> *) a b.
    (Monad m, MonadPlus p) =>
    (a -> m b) -> [a] -> m (p b)
    mapMP ((a -> b -> c -> m d) -> (a, b, c) -> m d
    forall a b c d. (a -> b -> c -> d) -> (a, b, c) -> d
    uncurry3 a -> b -> c -> m d
    f) ([(a, b, c)] -> m (p d)) -> ([c] -> [(a, b, c)]) -> [c] -> m (p d)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [a] -> [b] -> [c] -> [(a, b, c)]
    forall a b c. [a] -> [b] -> [c] -> [(a, b, c)]
    zip3 [a]
    xs [b]
    ys

    zipWithM4 :: (Monad m, MonadPlus p) => (a -> b -> c -> d -> m e) -> [a] -> [b] -> [c] -> [d] -> m (p e)
    zipWithM4 :: forall (m :: * -> *) (p :: * -> *) a b c d e.
    (Monad m, MonadPlus p) =>
    (a -> b -> c -> d -> m e) -> [a] -> [b] -> [c] -> [d] -> m (p e)
    zipWithM4 a -> b -> c -> d -> m e
    f [a]
    xs [b]
    ys [c]
    zs = ((a, b, c, d) -> m e) -> [(a, b, c, d)] -> m (p e)
    forall (m :: * -> *) (p :: * -> *) a b.
    (Monad m, MonadPlus p) =>
    (a -> m b) -> [a] -> m (p b)
    mapMP ((a -> b -> c -> d -> m e) -> (a, b, c, d) -> m e
    forall a b c d e. (a -> b -> c -> d -> e) -> (a, b, c, d) -> e
    uncurry4 a -> b -> c -> d -> m e
    f) ([(a, b, c, d)] -> m (p e))
    -> ([d] -> [(a, b, c, d)]) -> [d] -> m (p e)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [a] -> [b] -> [c] -> [d] -> [(a, b, c, d)]
    forall a b c d. [a] -> [b] -> [c] -> [d] -> [(a, b, c, d)]
    zip4 [a]
    xs [b]
    ys [c]
    zs

    zipWithM5 :: (Monad m, MonadPlus p) => (a -> b -> c -> d -> e -> m f) -> [a] -> [b] -> [c] -> [d] -> [e] -> m (p f)
    zipWithM5 :: forall (m :: * -> *) (p :: * -> *) a b c d e f.
    (Monad m, MonadPlus p) =>
    (a -> b -> c -> d -> e -> m f)
    -> [a] -> [b] -> [c] -> [d] -> [e] -> m (p f)
    zipWithM5 a -> b -> c -> d -> e -> m f
    f [a]
    xs [b]
    ys [c]
    zs [d]
    ws = ((a, b, c, d, e) -> m f) -> [(a, b, c, d, e)] -> m (p f)
    forall (m :: * -> *) (p :: * -> *) a b.
    (Monad m, MonadPlus p) =>
    (a -> m b) -> [a] -> m (p b)
    mapMP ((a -> b -> c -> d -> e -> m f) -> (a, b, c, d, e) -> m f
    forall a b c d e f.
    (a -> b -> c -> d -> e -> f) -> (a, b, c, d, e) -> f
    uncurry5 a -> b -> c -> d -> e -> m f
    f) ([(a, b, c, d, e)] -> m (p f))
    -> ([e] -> [(a, b, c, d, e)]) -> [e] -> m (p f)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [a] -> [b] -> [c] -> [d] -> [e] -> [(a, b, c, d, e)]
    forall a b c d e.
    [a] -> [b] -> [c] -> [d] -> [e] -> [(a, b, c, d, e)]
    zip5 [a]
    xs [b]
    ys [c]
    zs [d]
    ws

    zipWithM6 :: (Monad m, MonadPlus p) => (a -> b -> c -> d -> e -> f -> m g) -> [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> m (p g)
    zipWithM6 :: forall (m :: * -> *) (p :: * -> *) a b c d e f g.
    (Monad m, MonadPlus p) =>
    (a -> b -> c -> d -> e -> f -> m g)
    -> [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> m (p g)
    zipWithM6 a -> b -> c -> d -> e -> f -> m g
    f [a]
    xs [b]
    ys [c]
    zs [d]
    ws [e]
    ss = ((a, b, c, d, e, f) -> m g) -> [(a, b, c, d, e, f)] -> m (p g)
    forall (m :: * -> *) (p :: * -> *) a b.
    (Monad m, MonadPlus p) =>
    (a -> m b) -> [a] -> m (p b)
    mapMP ((a -> b -> c -> d -> e -> f -> m g) -> (a, b, c, d, e, f) -> m g
    forall a b c d e f g.
    (a -> b -> c -> d -> e -> f -> g) -> (a, b, c, d, e, f) -> g
    uncurry6 a -> b -> c -> d -> e -> f -> m g
    f) ([(a, b, c, d, e, f)] -> m (p g))
    -> ([f] -> [(a, b, c, d, e, f)]) -> [f] -> m (p g)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [(a, b, c, d, e, f)]
    forall a b c d e f.
    [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [(a, b, c, d, e, f)]
    zip6 [a]
    xs [b]
    ys [c]
    zs [d]
    ws [e]
    ss

    nubM :: (Eq a, Monad m, MonadPlus p) => [a] -> m (p a)
    nubM :: forall a (m :: * -> *) (p :: * -> *).
    (Eq a, Monad m, MonadPlus p) =>
    [a] -> m (p a)
    nubM = (a -> a -> m Bool) -> [a] -> m (p a)
    forall (m :: * -> *) (p :: * -> *) a.
    (Monad m, MonadPlus p) =>
    (a -> a -> m Bool) -> [a] -> m (p a)
    nubByM a -> a -> m Bool
    forall a (m :: * -> *). (Eq a, Monad m) => a -> a -> m Bool
    eqM

    nubByM :: (Monad m, MonadPlus p) => (a -> a -> m Bool) -> [a] -> m (p a)
    nubByM :: forall (m :: * -> *) (p :: * -> *) a.
    (Monad m, MonadPlus p) =>
    (a -> a -> m Bool) -> [a] -> m (p a)
    nubByM a -> a -> m Bool
    _ [] = p a -> m (p a)
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return p a
    forall a. p a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero
    nubByM a -> a -> m Bool
    eq (a
    x:[a]
    xs) = (p a -> p a) -> m (p a) -> m (p a)
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM (a
    xa -> p a -> p a
    forall (p :: * -> *) a. MonadPlus p => a -> p a -> p a
    !) (m (p a) -> m (p a)) -> m (p a) -> m (p a)
    forall a b. (a -> b) -> a -> b
    $ (a -> m Bool) -> [a] -> m [a]
    forall (m :: * -> *) a.
    Applicative m =>
    (a -> m Bool) -> [a] -> m [a]
    filterM (Bool -> m Bool
    forall (m :: * -> *). Monad m => Bool -> m Bool
    notM (Bool -> m Bool) -> (a -> m Bool) -> a -> m Bool
    forall (m :: * -> *) b c a.
    Monad m =>
    (b -> m c) -> (a -> m b) -> a -> m c
    <=< a -> a -> m Bool
    eq a
    x) [a]
    xs m [a] -> ([a] -> m (p a)) -> m (p 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 -> a -> m Bool) -> [a] -> m (p a)
    forall (m :: * -> *) (p :: * -> *) a.
    (Monad m, MonadPlus p) =>
    (a -> a -> m Bool) -> [a] -> m (p a)
    nubByM a -> a -> m Bool
    eq

    deleteM :: (Eq a, Monad m) => a -> [a] -> m [a]
    deleteM :: forall a (m :: * -> *). (Eq a, Monad m) => a -> [a] -> m [a]
    deleteM = (a -> a -> m Bool) -> a -> [a] -> m [a]
    forall (m :: * -> *) a.
    Monad m =>
    (a -> a -> m Bool) -> a -> [a] -> m [a]
    deleteByM a -> a -> m Bool
    forall a (m :: * -> *). (Eq a, Monad m) => a -> a -> m Bool
    eqM

    deleteByM :: (Monad m) => (a -> a -> m Bool) -> a -> [a] -> m [a]
    deleteByM :: forall (m :: * -> *) a.
    Monad m =>
    (a -> a -> m Bool) -> a -> [a] -> m [a]
    deleteByM a -> a -> m Bool
    _ a
    _ [] = [a] -> m [a]
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return []
    deleteByM a -> a -> m Bool
    eq a
    x (a
    y:[a]
    ys) = do
      bool <- a -> a -> m Bool
    eq a
    x a
    y
      if bool
        then return ys
        else liftM (y:) $ deleteByM eq x ys

    deleteFirstsM :: (Eq a, Monad m) => [a] -> [a] -> m [a]
    deleteFirstsM :: forall a (m :: * -> *). (Eq a, Monad m) => [a] -> [a] -> m [a]
    deleteFirstsM = (a -> a -> m Bool) -> [a] -> [a] -> m [a]
    forall (m :: * -> *) a.
    Monad m =>
    (a -> a -> m Bool) -> [a] -> [a] -> m [a]
    deleteFirstsByM a -> a -> m Bool
    forall a (m :: * -> *). (Eq a, Monad m) => a -> a -> m Bool
    eqM

    deleteFirstsByM :: (Monad m) => (a -> a -> m Bool) -> [a] -> [a] -> m [a]
    deleteFirstsByM :: forall (m :: * -> *) a.
    Monad m =>
    (a -> a -> m Bool) -> [a] -> [a] -> m [a]
    deleteFirstsByM a -> a -> m Bool
    _ [a]
    xs [] = [a] -> m [a]
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return [a]
    xs
    deleteFirstsByM a -> a -> m Bool
    eq [a]
    xs (a
    y:[a]
    ys) = do
      xs' <- (a -> a -> m Bool) -> a -> [a] -> m [a]
    forall (m :: * -> *) a.
    Monad m =>
    (a -> a -> m Bool) -> a -> [a] -> m [a]
    deleteByM a -> a -> m Bool
    eq a
    y [a]
    xs
      deleteFirstsByM eq xs' ys

    unionM :: (Eq a, Monad m) => [a] -> [a] -> m [a]
    unionM :: forall a (m :: * -> *). (Eq a, Monad m) => [a] -> [a] -> m [a]
    unionM = (a -> a -> m Bool) -> [a] -> [a] -> m [a]
    forall (m :: * -> *) a.
    Monad m =>
    (a -> a -> m Bool) -> [a] -> [a] -> m [a]
    unionByM a -> a -> m Bool
    forall a (m :: * -> *). (Eq a, Monad m) => a -> a -> m Bool
    eqM

    unionByM :: (Monad m) => (a -> a -> m Bool) -> [a] -> [a] -> m [a]
    unionByM :: forall (m :: * -> *) a.
    Monad m =>
    (a -> a -> m Bool) -> [a] -> [a] -> m [a]
    unionByM a -> a -> m Bool
    eq [a]
    ys [a]
    xs = do
      ys' <- (a -> a -> m Bool) -> [a] -> m [a]
    forall (m :: * -> *) (p :: * -> *) a.
    (Monad m, MonadPlus p) =>
    (a -> a -> m Bool) -> [a] -> m (p a)
    nubByM a -> a -> m Bool
    eq [a]
    ys
      ys'' <- foldM (flip $ deleteByM eq) ys' xs
      return $ xs ++ ys''

    intersectM :: (Eq a, Monad m, MonadPlus p) => [a] -> [a] -> m (p a)
    intersectM :: forall a (m :: * -> *) (p :: * -> *).
    (Eq a, Monad m, MonadPlus p) =>
    [a] -> [a] -> m (p a)
    intersectM = (a -> a -> m Bool) -> [a] -> [a] -> m (p a)
    forall (m :: * -> *) (p :: * -> *) a.
    (Monad m, MonadPlus p) =>
    (a -> a -> m Bool) -> [a] -> [a] -> m (p a)
    intersectByM a -> a -> m Bool
    forall a (m :: * -> *). (Eq a, Monad m) => a -> a -> m Bool
    eqM

    intersectByM :: (Monad m, MonadPlus p) => (a -> a -> m Bool) -> [a] -> [a] -> m (p a)
    intersectByM :: forall (m :: * -> *) (p :: * -> *) a.
    (Monad m, MonadPlus p) =>
    (a -> a -> m Bool) -> [a] -> [a] -> m (p a)
    intersectByM a -> a -> m Bool
    _ [] [a]
    _ = p a -> m (p a)
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return p a
    forall a. p a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero
    intersectByM a -> a -> m Bool
    _ [a]
    _ [] = p a -> m (p a)
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return p a
    forall a. p a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero
    intersectByM a -> a -> m Bool
    eq (a
    x:[a]
    xs) [a]
    ys = do
      bool <- (a -> m Bool) -> [a] -> m Bool
    forall (m :: * -> *) (t :: * -> *) a.
    (Monad m, Traversable t) =>
    (a -> m Bool) -> t a -> m Bool
    anyM (a -> a -> m Bool
    eq a
    x) [a]
    ys
      if bool
        then liftM (x!) $ intersectByM eq xs ys
        else intersectByM eq xs ys

    groupM :: (Eq a, Monad m, MonadPlus p, MonadPlus q) => [a] -> m (p (q a))
    groupM :: forall a (m :: * -> *) (p :: * -> *) (q :: * -> *).
    (Eq a, Monad m, MonadPlus p, MonadPlus q) =>
    [a] -> m (p (q a))
    groupM = (a -> a -> m Bool) -> [a] -> m (p (q a))
    forall (m :: * -> *) (p :: * -> *) (q :: * -> *) a.
    (Monad m, MonadPlus p, MonadPlus q) =>
    (a -> a -> m Bool) -> [a] -> m (p (q a))
    groupByM a -> a -> m Bool
    forall a (m :: * -> *). (Eq a, Monad m) => a -> a -> m Bool
    eqM

    groupByM :: (Monad m, MonadPlus p, MonadPlus q) => (a -> a -> m Bool) -> [a] -> m (p (q a))
    groupByM :: forall (m :: * -> *) (p :: * -> *) (q :: * -> *) a.
    (Monad m, MonadPlus p, MonadPlus q) =>
    (a -> a -> m Bool) -> [a] -> m (p (q a))
    groupByM a -> a -> m Bool
    _ [] = p (q a) -> m (p (q a))
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return p (q a)
    forall a. p a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero
    groupByM a -> a -> m Bool
    eq (a
    x:[a]
    xs) = do
      (ys, zs) <- (a -> m Bool) -> [a] -> m (q a, [a])
    forall (m :: * -> *) (p :: * -> *) a.
    (Monad m, MonadPlus p) =>
    (a -> m Bool) -> [a] -> m (p a, [a])
    spanM (a -> a -> m Bool
    eq a
    x) [a]
    xs
      liftM ((x!ys)!) $ groupByM eq zs

    sortM :: (Ord a, Monad m) => [a] -> m [a]
    sortM :: forall a (m :: * -> *). (Ord a, Monad m) => [a] -> m [a]
    sortM = (a -> a -> m Ordering) -> [a] -> m [a]
    forall (m :: * -> *) a.
    Monad m =>
    (a -> a -> m Ordering) -> [a] -> m [a]
    sortByM a -> a -> m Ordering
    forall a (m :: * -> *). (Ord a, Monad m) => a -> a -> m Ordering
    compareM

    sortByM :: (Monad m) => (a -> a -> m Ordering) -> [a] -> m [a]
    sortByM :: forall (m :: * -> *) a.
    Monad m =>
    (a -> a -> m Ordering) -> [a] -> m [a]
    sortByM a -> a -> m Ordering
    cmp = [[a]] -> m [a]
    mergeAll ([[a]] -> m [a]) -> ([a] -> m [[a]]) -> [a] -> m [a]
    forall (m :: * -> *) b c a.
    Monad m =>
    (b -> m c) -> (a -> m b) -> a -> m c
    <=< [a] -> m [[a]]
    sequences
      where
        sequences :: [a] -> m [[a]]
    sequences (a
    a:a
    b:[a]
    xs) = do
          ord <- a -> a -> m Ordering
    cmp a
    a a
    b
          case ord of
            Ordering
    GT -> a -> [a] -> [a] -> m [[a]]
    descending a
    b [a
    a] [a]
    xs
            Ordering
    _ -> a -> ([a] -> [a]) -> [a] -> m [[a]]
    ascending a
    b (a
    aa -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :) [a]
    xs
        sequences [a]
    xs = [[a]] -> m [[a]]
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return [[a]
    xs]

        descending :: a -> [a] -> [a] -> m [[a]]
    descending a
    a [a]
    as cs :: [a]
    cs@(a
    b:[a]
    bs) = do
          ord <- a -> a -> m Ordering
    cmp a
    a a
    b
          case ord of
            Ordering
    GT -> a -> [a] -> [a] -> m [[a]]
    descending a
    b (a
    aa -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    as) [a]
    bs
            Ordering
    _ -> ([[a]] -> [[a]]) -> m [[a]] -> m [[a]]
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM ((a
    aa -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    as) [a] -> [[a]] -> [[a]]
    forall a. a -> [a] -> [a]
    :) (m [[a]] -> m [[a]]) -> m [[a]] -> m [[a]]
    forall a b. (a -> b) -> a -> b
    $ [a] -> m [[a]]
    sequences [a]
    cs
        descending a
    a [a]
    as [a]
    bs = ([[a]] -> [[a]]) -> m [[a]] -> m [[a]]
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM ((a
    aa -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    as) [a] -> [[a]] -> [[a]]
    forall a. a -> [a] -> [a]
    :) (m [[a]] -> m [[a]]) -> m [[a]] -> m [[a]]
    forall a b. (a -> b) -> a -> b
    $ [a] -> m [[a]]
    sequences [a]
    bs

        ascending :: a -> ([a] -> [a]) -> [a] -> m [[a]]
    ascending a
    a [a] -> [a]
    as cs :: [a]
    cs@(a
    b:[a]
    bs) = do
          ord <- a -> a -> m Ordering
    cmp a
    a a
    b
          case ord of
            Ordering
    GT -> ([[a]] -> [[a]]) -> m [[a]] -> m [[a]]
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM ([a] -> [a]
    as [a
    a] [a] -> [[a]] -> [[a]]
    forall a. a -> [a] -> [a]
    :) (m [[a]] -> m [[a]]) -> m [[a]] -> m [[a]]
    forall a b. (a -> b) -> a -> b
    $ [a] -> m [[a]]
    sequences [a]
    cs
            Ordering
    _ -> a -> ([a] -> [a]) -> [a] -> m [[a]]
    ascending a
    b (\[a]
    ys -> [a] -> [a]
    as (a
    aa -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    ys)) [a]
    bs
        ascending a
    a [a] -> [a]
    as [a]
    bs = ([[a]] -> [[a]]) -> m [[a]] -> m [[a]]
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM ([a] -> [a]
    as [a
    a] [a] -> [[a]] -> [[a]]
    forall a. a -> [a] -> [a]
    :) (m [[a]] -> m [[a]]) -> m [[a]] -> m [[a]]
    forall a b. (a -> b) -> a -> b
    $ [a] -> m [[a]]
    sequences [a]
    bs

        mergeAll :: [[a]] -> m [a]
    mergeAll [[a]
    x] = [a] -> m [a]
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return [a]
    x
        mergeAll [[a]]
    xs = [[a]] -> m [a]
    mergeAll ([[a]] -> m [a]) -> m [[a]] -> m [a]
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
    =<< ([[a]] -> m [[a]]
    mergePairs [[a]]
    xs)

        mergePairs :: [[a]] -> m [[a]]
    mergePairs ([a]
    a:[a]
    b:[[a]]
    xs) = ([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 (:) ([a] -> [a] -> m [a]
    merge [a]
    a [a]
    b) (m [[a]] -> m [[a]]) -> m [[a]] -> m [[a]]
    forall a b. (a -> b) -> a -> b
    $ [[a]] -> m [[a]]
    mergePairs [[a]]
    xs
        mergePairs [[a]]
    xs = [[a]] -> m [[a]]
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return [[a]]
    xs

        merge :: [a] -> [a] -> m [a]
    merge as :: [a]
    as@(a
    a:[a]
    as') bs :: [a]
    bs@(a
    b:[a]
    bs') = do
          ord <- a -> a -> m Ordering
    cmp a
    a a
    b
          case ord of
            Ordering
    GT -> ([a] -> [a]) -> m [a] -> m [a]
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM (a
    b a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :) (m [a] -> m [a]) -> m [a] -> m [a]
    forall a b. (a -> b) -> a -> b
    $ [a] -> [a] -> m [a]
    merge [a]
    as  [a]
    bs'
            Ordering
    _ -> ([a] -> [a]) -> m [a] -> m [a]
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM (a
    a a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :) (m [a] -> m [a]) -> m [a] -> m [a]
    forall a b. (a -> b) -> a -> b
    $ [a] -> [a] -> m [a]
    merge [a]
    as' [a]
    bs
        merge [] [a]
    bs = [a] -> m [a]
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return [a]
    bs
        merge [a]
    as [] = [a] -> m [a]
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return [a]
    as

    insertM :: (Ord a, Monad m) => a -> [a] -> m [a]
    insertM :: forall a (m :: * -> *). (Ord a, Monad m) => a -> [a] -> m [a]
    insertM = (a -> a -> m Ordering) -> a -> [a] -> m [a]
    forall (m :: * -> *) a.
    Monad m =>
    (a -> a -> m Ordering) -> a -> [a] -> m [a]
    insertByM a -> a -> m Ordering
    forall a (m :: * -> *). (Ord a, Monad m) => a -> a -> m Ordering
    compareM

    insertByM :: (Monad m) => (a -> a -> m Ordering) -> a -> [a] -> m [a]
    insertByM :: forall (m :: * -> *) a.
    Monad m =>
    (a -> a -> m Ordering) -> a -> [a] -> m [a]
    insertByM a -> a -> m Ordering
    _ a
    x [] = [a] -> m [a]
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return [a
    x]
    insertByM a -> a -> m Ordering
    cmp a
    x (a
    y:[a]
    ys) = do
      ordering <- a -> a -> m Ordering
    cmp a
    x a
    y
      case ordering of
        Ordering
    GT -> ([a] -> [a]) -> m [a] -> m [a]
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM (a
    ya -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :) (m [a] -> m [a]) -> m [a] -> m [a]
    forall a b. (a -> b) -> a -> b
    $ (a -> a -> m Ordering) -> a -> [a] -> m [a]
    forall (m :: * -> *) a.
    Monad m =>
    (a -> a -> m Ordering) -> a -> [a] -> m [a]
    insertByM a -> a -> m Ordering
    cmp a
    x [a]
    ys
        Ordering
    _ -> [a] -> m [a]
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ([a] -> m [a]) -> [a] -> m [a]
    forall a b. (a -> b) -> a -> b
    $ a
    xa -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :a
    ya -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    ys

    maximumM :: (Ord a, Monad m) => [a] -> m a
    maximumM :: forall a (m :: * -> *). (Ord a, Monad m) => [a] -> m a
    maximumM [] = String -> String -> m a
    forall a. String -> String -> a
    error String
    "maximumM" String
    "empty list"
    maximumM [a]
    xs = (a -> a -> m Ordering) -> [a] -> m a
    forall (m :: * -> *) a.
    Monad m =>
    (a -> a -> m Ordering) -> [a] -> m a
    maximumByM a -> a -> m Ordering
    forall a (m :: * -> *). (Ord a, Monad m) => a -> a -> m Ordering
    compareM [a]
    xs

    maximumByM :: (Monad m) => (a -> a -> m Ordering) -> [a] -> m a
    maximumByM :: forall (m :: * -> *) a.
    Monad m =>
    (a -> a -> m Ordering) -> [a] -> m a
    maximumByM a -> a -> m Ordering
    _ [] = String -> String -> m a
    forall a. String -> String -> a
    error String
    "maximumByM" String
    "empty list"
    maximumByM a -> a -> m Ordering
    cmp [a]
    xs = (a -> a -> m a) -> [a] -> m a
    forall (m :: * -> *) a. Monad m => (a -> a -> m a) -> [a] -> m a
    foldM1 a -> a -> m a
    maxByM [a]
    xs
      where
        maxByM :: a -> a -> m a
    maxByM a
    x a
    y = do
          ordering <- a -> a -> m Ordering
    cmp a
    x a
    y
          return $ case ordering of
            Ordering
    GT -> a
    x
            Ordering
    _ -> a
    y

    minimumM :: (Ord a, Monad m) => [a] -> m a
    minimumM :: forall a (m :: * -> *). (Ord a, Monad m) => [a] -> m a
    minimumM [] = String -> String -> m a
    forall a. String -> String -> a
    error String
    "minimumM" String
    "empty list"
    minimumM [a]
    xs = (a -> a -> m Ordering) -> [a] -> m a
    forall (m :: * -> *) a.
    Monad m =>
    (a -> a -> m Ordering) -> [a] -> m a
    minimumByM a -> a -> m Ordering
    forall a (m :: * -> *). (Ord a, Monad m) => a -> a -> m Ordering
    compareM [a]
    xs

    minimumByM :: (Monad m) => (a -> a -> m Ordering) -> [a] -> m a
    minimumByM :: forall (m :: * -> *) a.
    Monad m =>
    (a -> a -> m Ordering) -> [a] -> m a
    minimumByM a -> a -> m Ordering
    _ [] = String -> String -> m a
    forall a. String -> String -> a
    error String
    "minimumByM" String
    "empty list"
    minimumByM a -> a -> m Ordering
    cmp [a]
    xs = (a -> a -> m a) -> [a] -> m a
    forall (m :: * -> *) a. Monad m => (a -> a -> m a) -> [a] -> m a
    foldM1 a -> a -> m a
    minByM [a]
    xs
      where
        minByM :: a -> a -> m a
    minByM a
    x a
    y = do
          ordering <- a -> a -> m Ordering
    cmp a
    x a
    y
          return $ case ordering of
            Ordering
    GT -> a
    y
            Ordering
    _ -> a
    x