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 :: String -> String -> a
error func :: String
func msg :: String
msg = String -> a
forall a. HasCallStack => String -> a
Prelude.error (String -> a) -> String -> a
forall a b. (a -> b) -> a -> b
$ "Control.Monad.ListM." String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
func String -> String -> String
forall a. [a] -> [a] -> [a]
++ ": " String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
msg
notM :: (Monad m) => Bool -> m Bool
notM :: Bool -> m Bool
notM = Bool -> m Bool
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 :: a -> a -> m Bool
eqM x :: a
x y :: a
y = Bool -> m Bool
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 :: a -> a -> m Ordering
compareM x :: a
x y :: a
y = Ordering -> m Ordering
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
x :: a
x ! :: a -> p a -> p a
! y :: p a
y = a -> p a
forall (m :: * -> *) a. Monad m => a -> m a
return a
x 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
!!! :: [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 (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (!)
uncurry3 :: (a -> b -> c -> d) -> ((a, b, c) -> d)
uncurry3 :: (a -> b -> c -> d) -> (a, b, c) -> d
uncurry3 f :: a -> b -> c -> d
f (x :: a
x, y :: b
y, z :: 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 :: (a -> b -> c -> d -> e) -> (a, b, c, d) -> e
uncurry4 f :: a -> b -> c -> d -> e
f (x :: a
x, y :: b
y, z :: c
z, w :: 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 :: (a -> b -> c -> d -> e -> f) -> (a, b, c, d, e) -> f
uncurry5 f :: a -> b -> c -> d -> e -> f
f (x :: a
x, y :: b
y, z :: c
z, w :: d
w, s :: 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 :: (a -> b -> c -> d -> e -> f -> g) -> (a, b, c, d, e, f) -> g
uncurry6 f :: a -> b -> c -> d -> e -> f -> g
f (x :: a
x, y :: b
y, z :: c
z, w :: d
w, s :: e
s, t :: 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 :: (a -> m b) -> [a] -> m (p b)
mapMP _ [] = p b -> m (p b)
forall (m :: * -> *) a. Monad m => a -> m a
return p b
forall (m :: * -> *) a. MonadPlus m => m a
mzero
mapMP f :: a -> m b
f (x :: a
x:xs :: [a]
xs) = do
b
y <- a -> m b
f a
x
(p b -> p b) -> m (p b) -> m (p b)
forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
liftM (b
yb -> p b -> p b
forall (p :: * -> *) a. MonadPlus p => a -> p a -> p a
!) (m (p b) -> m (p b)) -> m (p b) -> m (p b)
forall a b. (a -> b) -> a -> b
$ (a -> m b) -> [a] -> m (p b)
forall (m :: * -> *) (p :: * -> *) a b.
(Monad m, MonadPlus p) =>
(a -> m b) -> [a] -> m (p b)
mapMP a -> m b
f [a]
xs
filterMP :: (Monad m, MonadPlus p) => (a -> m Bool) -> [a] -> m (p a)
filterMP :: (a -> m Bool) -> [a] -> m (p a)
filterMP _ [] = p a -> m (p a)
forall (m :: * -> *) a. Monad m => a -> m a
return p a
forall (m :: * -> *) a. MonadPlus m => m a
mzero
filterMP p :: a -> m Bool
p (x :: a
x:xs :: [a]
xs) = do
Bool
bool <- a -> m Bool
p a
x
if Bool
bool
then (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 (p a)
forall (m :: * -> *) (p :: * -> *) a.
(Monad m, MonadPlus p) =>
(a -> m Bool) -> [a] -> m (p a)
filterMP a -> m Bool
p [a]
xs
else (a -> m Bool) -> [a] -> m (p a)
forall (m :: * -> *) (p :: * -> *) a.
(Monad m, MonadPlus p) =>
(a -> m Bool) -> [a] -> m (p a)
filterMP a -> m Bool
p [a]
xs
intersperseM :: (Monad m, MonadPlus p) => m a -> [a] -> m (p a)
intersperseM :: m a -> [a] -> m (p a)
intersperseM _ [] = p a -> m (p a)
forall (m :: * -> *) a. Monad m => a -> m a
return p a
forall (m :: * -> *) a. MonadPlus m => m a
mzero
intersperseM _ [x :: a
x] = p a -> m (p 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 (m :: * -> *) a. Monad m => a -> m a
return a
x
intersperseM m :: m a
m (x :: a
x:ys :: [a]
ys) = do
a
z <- m a
m
(p a -> p a) -> m (p a) -> m (p a)
forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
liftM ([a
x, a
z] [a] -> 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
$ m a -> [a] -> m (p a)
forall (m :: * -> *) (p :: * -> *) a.
(Monad m, MonadPlus p) =>
m a -> [a] -> m (p a)
intersperseM m a
m [a]
ys
intercalateM :: (Monad m, MonadPlus p) => m (p a) -> [p a] -> m (p a)
intercalateM :: m (p a) -> [p a] -> m (p a)
intercalateM m :: 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 :: (a -> a -> m a) -> [a] -> m a
foldM1 _ [] = String -> String -> m a
forall a. String -> String -> a
error "foldM1" "empty list"
foldM1 f :: a -> a -> m a
f (x :: a
x:xs :: [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 :: (a -> m b) -> m a -> m b
joinMap f :: 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 :: (a -> m (p b)) -> [a] -> m (p b)
joinMapM f :: 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 :: (a -> m Bool) -> t a -> m Bool
anyM p :: 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)
mapM a -> m Bool
p
allM :: (Monad m, Traversable t) => (a -> m Bool) -> t a -> m Bool
allM :: (a -> m Bool) -> t a -> m Bool
allM p :: 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)
mapM a -> m Bool
p
scanM :: (Monad m, MonadPlus p) => (a -> b -> m a) -> a -> [b] -> m (p a)
scanM :: (a -> b -> m a) -> a -> [b] -> m (p a)
scanM _ z :: a
z [] = p a -> m (p 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 (m :: * -> *) a. Monad m => a -> m a
return a
z
scanM f :: a -> b -> m a
f z :: a
z (x :: b
x:xs :: [b]
xs) = do
a
z' <- a -> b -> m a
f a
z b
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
za -> 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 -> b -> m a) -> a -> [b] -> m (p a)
forall (m :: * -> *) (p :: * -> *) a b.
(Monad m, MonadPlus p) =>
(a -> b -> m a) -> a -> [b] -> m (p a)
scanM a -> b -> m a
f a
z' [b]
xs
mapAccumM :: (Monad m, MonadPlus p) => (acc -> x -> m (acc, y)) -> acc -> [x] -> m (acc, p y)
mapAccumM :: (acc -> x -> m (acc, y)) -> acc -> [x] -> m (acc, p y)
mapAccumM _ z :: acc
z [] = (acc, p y) -> m (acc, p y)
forall (m :: * -> *) a. Monad m => a -> m a
return (acc
z, p y
forall (m :: * -> *) a. MonadPlus m => m a
mzero)
mapAccumM f :: acc -> x -> m (acc, y)
f z :: acc
z (x :: x
x:xs :: [x]
xs) = do
(z' :: acc
z', y :: y
y) <- acc -> x -> m (acc, y)
f acc
z x
x
(z'' :: acc
z'', ys :: p y
ys) <- (acc -> x -> m (acc, y)) -> acc -> [x] -> m (acc, p y)
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)
f acc
z' [x]
xs
(acc, p y) -> m (acc, p y)
forall (m :: * -> *) a. Monad m => a -> m a
return (acc
z'', y
yy -> p y -> p y
forall (p :: * -> *) a. MonadPlus p => a -> p a -> p a
!p y
ys)
iterateM :: (Monad m, MonadPlus p) => (a -> m a) -> a -> m (p a)
iterateM :: (a -> m a) -> a -> m (p a)
iterateM f :: a -> m a
f x :: a
x = do
a
x' <- a -> m a
f 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
$ (a -> m a) -> a -> m (p a)
forall (m :: * -> *) (p :: * -> *) a.
(Monad m, MonadPlus p) =>
(a -> m a) -> a -> m (p a)
iterateM a -> m a
f a
x'
takeM :: (Integral i, Monad m, MonadPlus p) => i -> [m a] -> m (p a)
takeM :: i -> [m a] -> m (p a)
takeM _ [] = p a -> m (p a)
forall (m :: * -> *) a. Monad m => a -> m a
return p a
forall (m :: * -> *) a. MonadPlus m => m a
mzero
takeM n :: i
n (m :: m a
m:ms :: [m a]
ms)
| i
n i -> i -> Bool
forall a. Ord a => a -> a -> Bool
<= 0 = p a -> m (p a)
forall (m :: * -> *) a. Monad m => a -> m a
return 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 (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \x :: 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
-1) [m a]
ms
dropM :: (Integral i, Monad m) => i -> [m a] -> m [a]
dropM :: i -> [m a] -> m [a]
dropM _ [] = [a] -> m [a]
forall (m :: * -> *) a. Monad m => a -> m a
return []
dropM n :: i
n (m :: m a
m:ms :: [m a]
ms)
| i
n i -> i -> Bool
forall a. Ord a => a -> a -> Bool
<= 0 = [m a] -> m [a]
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t 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 (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
-1) [m a]
ms
splitAtM :: (Integral i, Monad m, MonadPlus p) => i -> [m a] -> m (p a, [a])
splitAtM :: i -> [m a] -> m (p a, [a])
splitAtM _ [] = (p a, [a]) -> m (p a, [a])
forall (m :: * -> *) a. Monad m => a -> m a
return (p a
forall (m :: * -> *) a. MonadPlus m => m a
mzero, [])
splitAtM n :: i
n (m :: m a
m:ms :: [m a]
ms)
| i
n i -> i -> Bool
forall a. Ord a => a -> a -> Bool
<= 0 = do
[a]
ys <- [m a] -> m [a]
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t 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
(p a, [a]) -> m (p a, [a])
forall (m :: * -> *) a. Monad m => a -> m a
return (p a
forall (m :: * -> *) a. MonadPlus m => m a
mzero, [a]
ys)
| Bool
otherwise = do
a
x <- m a
m
(xs :: p a
xs, ys :: [a]
ys) <- i -> [m a] -> m (p a, [a])
forall i (m :: * -> *) (p :: * -> *) a.
(Integral i, Monad m, MonadPlus p) =>
i -> [m a] -> m (p a, [a])
splitAtM (i
ni -> i -> i
forall a. Num a => a -> a -> a
-1) [m a]
ms
(p a, [a]) -> m (p a, [a])
forall (m :: * -> *) a. Monad m => a -> m a
return (a
xa -> p a -> p a
forall (p :: * -> *) a. MonadPlus p => a -> p a -> p a
!p a
xs, [a]
ys)
takeWhileM :: (Monad m, MonadPlus p) => (a -> m Bool) -> [a] -> m (p a)
takeWhileM :: (a -> m Bool) -> [a] -> m (p a)
takeWhileM _ [] = p a -> m (p a)
forall (m :: * -> *) a. Monad m => a -> m a
return p a
forall (m :: * -> *) a. MonadPlus m => m a
mzero
takeWhileM p :: a -> m Bool
p (x :: a
x:xs :: [a]
xs) = do
Bool
bool <- a -> m Bool
p a
x
if Bool
bool
then (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 (p a)
forall (m :: * -> *) (p :: * -> *) a.
(Monad m, MonadPlus p) =>
(a -> m Bool) -> [a] -> m (p a)
takeWhileM a -> m Bool
p [a]
xs
else p a -> m (p a)
forall (m :: * -> *) a. Monad m => a -> m a
return p a
forall (m :: * -> *) a. MonadPlus m => m a
mzero
dropWhileM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
dropWhileM :: (a -> m Bool) -> [a] -> m [a]
dropWhileM _ [] = [a] -> m [a]
forall (m :: * -> *) a. Monad m => a -> m a
return []
dropWhileM p :: a -> m Bool
p (x :: a
x:xs :: [a]
xs) = do
Bool
bool <- a -> m Bool
p a
x
if Bool
bool
then (a -> m Bool) -> [a] -> m [a]
forall (m :: * -> *) a. Monad m => (a -> m Bool) -> [a] -> m [a]
dropWhileM a -> m Bool
p [a]
xs
else [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]
xs
spanM :: (Monad m, MonadPlus p) => (a -> m Bool) -> [a] -> m (p a, [a])
spanM :: (a -> m Bool) -> [a] -> m (p a, [a])
spanM _ [] = (p a, [a]) -> m (p a, [a])
forall (m :: * -> *) a. Monad m => a -> m a
return (p a
forall (m :: * -> *) a. MonadPlus m => m a
mzero, [])
spanM p :: a -> m Bool
p (x :: a
x:xs :: [a]
xs) = do
Bool
bool <- a -> m Bool
p a
x
if Bool
bool
then do
(ys :: p a
ys, zs :: [a]
zs) <- (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
p [a]
xs
(p a, [a]) -> m (p a, [a])
forall (m :: * -> *) a. Monad m => a -> m a
return (a
xa -> p a -> p a
forall (p :: * -> *) a. MonadPlus p => a -> p a -> p a
!p a
ys, [a]
zs)
else (p a, [a]) -> m (p a, [a])
forall (m :: * -> *) a. Monad m => a -> m a
return (p a
forall (m :: * -> *) a. MonadPlus m => m a
mzero, a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs)
breakM :: (Monad m, MonadPlus p) => (a -> m Bool) -> [a] -> m (p a, [a])
breakM :: (a -> m Bool) -> [a] -> m (p a, [a])
breakM p :: 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 :: a -> [a] -> m Bool
elemM x :: a
x xs :: [a]
xs = do
Maybe Int
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 Maybe Int
_ = Maybe Int
idx :: Maybe Int
Bool -> m Bool
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> m Bool) -> Bool -> m Bool
forall a b. (a -> b) -> a -> b
$ Maybe Int -> Bool
forall a. Maybe a -> Bool
isJust Maybe Int
idx
notElemM :: (Eq a, Monad m) => a -> [a] -> m Bool
notElemM :: a -> [a] -> m Bool
notElemM x :: 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 :: a -> [m (a, b)] -> m (p b)
lookupM _ [] = p b -> m (p b)
forall (m :: * -> *) a. Monad m => a -> m a
return p b
forall (m :: * -> *) a. MonadPlus m => m a
mzero
lookupM x :: a
x (m :: m (a, b)
m:ms :: [m (a, b)]
ms) = do
(k :: a
k, v :: b
v) <- m (a, b)
m
if a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
k
then p b -> m (p b)
forall (m :: * -> *) a. Monad m => a -> m a
return (p b -> m (p b)) -> p b -> m (p b)
forall a b. (a -> b) -> a -> b
$ b -> p b
forall (m :: * -> *) a. Monad m => a -> m a
return b
v
else a -> [m (a, b)] -> m (p b)
forall a (m :: * -> *) (p :: * -> *) b.
(Eq a, Monad m, MonadPlus p) =>
a -> [m (a, b)] -> m (p b)
lookupM a
x [m (a, b)]
ms
findM :: (Monad m, MonadPlus p) => (a -> m Bool) -> [a] -> m (p a)
findM :: (a -> m Bool) -> [a] -> m (p a)
findM _ [] = p a -> m (p a)
forall (m :: * -> *) a. Monad m => a -> m a
return p a
forall (m :: * -> *) a. MonadPlus m => m a
mzero
findM p :: a -> m Bool
p (x :: a
x:xs :: [a]
xs) = do
Bool
bool <- a -> m Bool
p a
x
if Bool
bool
then p a -> m (p 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 (m :: * -> *) a. Monad m => a -> m a
return a
x
else (a -> m Bool) -> [a] -> m (p a)
forall (m :: * -> *) (p :: * -> *) a.
(Monad m, MonadPlus p) =>
(a -> m Bool) -> [a] -> m (p a)
findM a -> m Bool
p [a]
xs
partitionM :: (Monad m, MonadPlus p) => (a -> m Bool) -> [a] -> m (p a, [a])
partitionM :: (a -> m Bool) -> [a] -> m (p a, [a])
partitionM _ [] = (p a, [a]) -> m (p a, [a])
forall (m :: * -> *) a. Monad m => a -> m a
return (p a
forall (m :: * -> *) a. MonadPlus m => m a
mzero, [])
partitionM p :: a -> m Bool
p (x :: a
x:xs :: [a]
xs) = do
Bool
bool <- a -> m Bool
p a
x
if Bool
bool
then do
(ys :: p a
ys, zs :: [a]
zs) <- (a -> m Bool) -> [a] -> m (p a, [a])
forall (m :: * -> *) (p :: * -> *) a.
(Monad m, MonadPlus p) =>
(a -> m Bool) -> [a] -> m (p a, [a])
partitionM a -> m Bool
p [a]
xs
(p a, [a]) -> m (p a, [a])
forall (m :: * -> *) a. Monad m => a -> m a
return (a
xa -> p a -> p a
forall (p :: * -> *) a. MonadPlus p => a -> p a -> p a
!p a
ys, [a]
zs)
else (p a, [a]) -> m (p a, [a])
forall (m :: * -> *) a. Monad m => a -> m a
return (p a
forall (m :: * -> *) a. MonadPlus m => m a
mzero, a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs)
elemIndexM :: (Eq a, Integral i, Monad m, MonadPlus p) => a -> [a] -> m (p i)
elemIndexM :: a -> [a] -> m (p i)
elemIndexM x :: 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 :: a -> [a] -> m (p i)
elemIndicesM x :: 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 :: (a -> m Bool) -> [a] -> m (p i)
findIndexM p :: 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 [0..]
findIndicesM :: (Integral i, Monad m, MonadPlus p) => (a -> m Bool) -> [a] -> m (p i)
findIndicesM :: (a -> m Bool) -> [a] -> m (p i)
findIndicesM p :: 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 [0..]
zipWithM3 :: (Monad m, MonadPlus p) => (a -> b -> c -> m d) -> [a] -> [b] -> [c] -> m (p d)
zipWithM3 :: (a -> b -> c -> m d) -> [a] -> [b] -> [c] -> m (p d)
zipWithM3 f :: a -> b -> c -> m d
f xs :: [a]
xs ys :: [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 :: (a -> b -> c -> d -> m e) -> [a] -> [b] -> [c] -> [d] -> m (p e)
zipWithM4 f :: a -> b -> c -> d -> m e
f xs :: [a]
xs ys :: [b]
ys zs :: [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 :: (a -> b -> c -> d -> e -> m f)
-> [a] -> [b] -> [c] -> [d] -> [e] -> m (p f)
zipWithM5 f :: a -> b -> c -> d -> e -> m f
f xs :: [a]
xs ys :: [b]
ys zs :: [c]
zs ws :: [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 :: (a -> b -> c -> d -> e -> f -> m g)
-> [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> m (p g)
zipWithM6 f :: a -> b -> c -> d -> e -> f -> m g
f xs :: [a]
xs ys :: [b]
ys zs :: [c]
zs ws :: [d]
ws ss :: [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 :: [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 :: (a -> a -> m Bool) -> [a] -> m (p a)
nubByM _ [] = p a -> m (p a)
forall (m :: * -> *) a. Monad m => a -> m a
return p a
forall (m :: * -> *) a. MonadPlus m => m a
mzero
nubByM eq :: a -> a -> m Bool
eq (x :: a
x:xs :: [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 (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 :: 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 :: (a -> a -> m Bool) -> a -> [a] -> m [a]
deleteByM _ _ [] = [a] -> m [a]
forall (m :: * -> *) a. Monad m => a -> m a
return []
deleteByM eq :: a -> a -> m Bool
eq x :: a
x (y :: a
y:ys :: [a]
ys) = do
Bool
bool <- a -> a -> m Bool
eq a
x a
y
if Bool
bool
then [a] -> m [a]
forall (m :: * -> *) a. Monad m => a -> m a
return [a]
ys
else ([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 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
x [a]
ys
deleteFirstsM :: (Eq a, Monad m) => [a] -> [a] -> m [a]
deleteFirstsM :: [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 :: (a -> a -> m Bool) -> [a] -> [a] -> m [a]
deleteFirstsByM _ xs :: [a]
xs [] = [a] -> m [a]
forall (m :: * -> *) a. Monad m => a -> m a
return [a]
xs
deleteFirstsByM eq :: a -> a -> m Bool
eq xs :: [a]
xs (y :: a
y:ys :: [a]
ys) = do
[a]
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
(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
eq [a]
xs' [a]
ys
unionM :: (Eq a, Monad m) => [a] -> [a] -> m [a]
unionM :: [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 :: (a -> a -> m Bool) -> [a] -> [a] -> m [a]
unionByM eq :: a -> a -> m Bool
eq ys :: [a]
ys xs :: [a]
xs = do
[a]
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
[a]
ys'' <- ([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]) -> [a] -> a -> m [a]
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((a -> [a] -> m [a]) -> [a] -> a -> m [a])
-> (a -> [a] -> m [a]) -> [a] -> a -> m [a]
forall a b. (a -> b) -> a -> b
$ (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]
ys' [a]
xs
[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]
xs [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
ys''
intersectM :: (Eq a, Monad m, MonadPlus p) => [a] -> [a] -> m (p a)
intersectM :: [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 :: (a -> a -> m Bool) -> [a] -> [a] -> m (p a)
intersectByM _ [] _ = p a -> m (p a)
forall (m :: * -> *) a. Monad m => a -> m a
return p a
forall (m :: * -> *) a. MonadPlus m => m a
mzero
intersectByM _ _ [] = p a -> m (p a)
forall (m :: * -> *) a. Monad m => a -> m a
return p a
forall (m :: * -> *) a. MonadPlus m => m a
mzero
intersectByM eq :: a -> a -> m Bool
eq (x :: a
x:xs :: [a]
xs) ys :: [a]
ys = do
Bool
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
bool
then (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 -> 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
eq [a]
xs [a]
ys
else (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
eq [a]
xs [a]
ys
groupM :: (Eq a, Monad m, MonadPlus p, MonadPlus q) => [a] -> m (p (q a))
groupM :: [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 :: (a -> a -> m Bool) -> [a] -> m (p (q a))
groupByM _ [] = p (q a) -> m (p (q a))
forall (m :: * -> *) a. Monad m => a -> m a
return p (q a)
forall (m :: * -> *) a. MonadPlus m => m a
mzero
groupByM eq :: a -> a -> m Bool
eq (x :: a
x:xs :: [a]
xs) = do
(ys :: q a
ys, zs :: [a]
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
(p (q a) -> p (q a)) -> m (p (q a)) -> m (p (q a))
forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
liftM ((a
xa -> q a -> q a
forall (p :: * -> *) a. MonadPlus p => a -> p a -> p a
!q a
ys)q a -> p (q a) -> p (q a)
forall (p :: * -> *) a. MonadPlus p => a -> p a -> p a
!) (m (p (q a)) -> m (p (q a))) -> m (p (q a)) -> m (p (q a))
forall a b. (a -> b) -> a -> b
$ (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
eq [a]
zs
sortM :: (Ord a, Monad m) => [a] -> m [a]
sortM :: [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 :: (a -> a -> m Ordering) -> [a] -> m [a]
sortByM cmp :: 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
b:xs :: [a]
xs) = do
Ordering
ord <- a -> a -> m Ordering
cmp a
a a
b
case Ordering
ord of
GT -> a -> [a] -> [a] -> m [[a]]
descending a
b [a
a] [a]
xs
_ -> a -> ([a] -> [a]) -> [a] -> m [[a]]
ascending a
b (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:) [a]
xs
sequences xs :: [a]
xs = [[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 :: [a]
as cs :: [a]
cs@(b :: a
b:bs :: [a]
bs) = do
Ordering
ord <- a -> a -> m Ordering
cmp a
a a
b
case Ordering
ord of
GT -> a -> [a] -> [a] -> m [[a]]
descending a
b (a
aa -> [a] -> [a]
forall a. 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
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]
as bs :: [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 as :: [a] -> [a]
as cs :: [a]
cs@(b :: a
b:bs :: [a]
bs) = do
Ordering
ord <- a -> a -> m Ordering
cmp a
a a
b
case Ordering
ord of
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
_ -> a -> ([a] -> [a]) -> [a] -> m [[a]]
ascending a
b (\ys :: [a]
ys -> [a] -> [a]
as (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ys)) [a]
bs
ascending a :: a
a as :: [a] -> [a]
as bs :: [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 [x :: [a]
x] = [a] -> m [a]
forall (m :: * -> *) a. Monad m => a -> m a
return [a]
x
mergeAll xs :: [[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]
b:xs :: [[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 xs :: [[a]]
xs = [[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' :: [a]
as') bs :: [a]
bs@(b :: a
b:bs' :: [a]
bs') = do
Ordering
ord <- a -> a -> m Ordering
cmp a
a a
b
case Ordering
ord of
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'
_ -> ([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 [] bs :: [a]
bs = [a] -> m [a]
forall (m :: * -> *) a. Monad m => a -> m a
return [a]
bs
merge as :: [a]
as [] = [a] -> m [a]
forall (m :: * -> *) a. Monad m => a -> m a
return [a]
as
insertM :: (Ord a, Monad m) => a -> [a] -> m [a]
insertM :: 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 :: (a -> a -> m Ordering) -> a -> [a] -> m [a]
insertByM _ x :: a
x [] = [a] -> m [a]
forall (m :: * -> *) a. Monad m => a -> m a
return [a
x]
insertByM cmp :: a -> a -> m Ordering
cmp x :: a
x (y :: a
y:ys :: [a]
ys) = do
Ordering
ordering <- a -> a -> m Ordering
cmp a
x a
y
case Ordering
ordering of
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
_ -> [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 :: [a] -> m a
maximumM [] = String -> String -> m a
forall a. String -> String -> a
error "maximumM" "empty list"
maximumM xs :: [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 :: (a -> a -> m Ordering) -> [a] -> m a
maximumByM _ [] = String -> String -> m a
forall a. String -> String -> a
error "maximumByM" "empty list"
maximumByM cmp :: a -> a -> m Ordering
cmp xs :: [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 x :: a
x y :: a
y = do
Ordering
ordering <- a -> a -> m Ordering
cmp a
x a
y
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
$ case Ordering
ordering of
GT -> a
x
_ -> a
y
minimumM :: (Ord a, Monad m) => [a] -> m a
minimumM :: [a] -> m a
minimumM [] = String -> String -> m a
forall a. String -> String -> a
error "minimumM" "empty list"
minimumM xs :: [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 :: (a -> a -> m Ordering) -> [a] -> m a
minimumByM _ [] = String -> String -> m a
forall a. String -> String -> a
error "minimumByM" "empty list"
minimumByM cmp :: a -> a -> m Ordering
cmp xs :: [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 x :: a
x y :: a
y = do
Ordering
ordering <- a -> a -> m Ordering
cmp a
x a
y
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
$ case Ordering
ordering of
GT -> a
y
_ -> a
x