module ListT
(
  ListT(..),
  -- * Execution utilities
  uncons,
  head,
  tail,
  null,
  alternate,
  alternateHoisting,
  fold,
  foldMaybe,
  applyFoldM,
  toList,
  toReverseList,
  traverse_,
  splitAt,
  -- * Construction utilities
  cons,
  fromFoldable,
  fromMVar,
  unfold,
  unfoldM,
  repeat,
  -- * Transformation utilities
  -- | 
  -- These utilities only accumulate the transformations
  -- without actually traversing the stream.
  -- They only get applied in a single traversal, 
  -- which only happens at the execution.
  traverse,
  take,
  drop,
  slice,
)
where

import ListT.Prelude hiding (uncons, toList, yield, fold, traverse, head, tail, take, drop, repeat, null, traverse_, splitAt)
import Control.Monad

-- |
-- A proper implementation of the list monad-transformer.
-- Useful for streaming of monadic data structures.
-- 
-- Since it has instances of 'MonadPlus' and 'Alternative',
-- you can use general utilities packages like
-- <http://hackage.haskell.org/package/monadplus "monadplus">
-- with it.
newtype ListT m a =
  ListT (m (Maybe (a, ListT m a)))
  deriving (ListT m a -> Bool
(a -> m) -> ListT m a -> m
(a -> b -> b) -> b -> ListT m a -> b
(forall m. Monoid m => ListT m m -> m)
-> (forall m a. Monoid m => (a -> m) -> ListT m a -> m)
-> (forall m a. Monoid m => (a -> m) -> ListT m a -> m)
-> (forall a b. (a -> b -> b) -> b -> ListT m a -> b)
-> (forall a b. (a -> b -> b) -> b -> ListT m a -> b)
-> (forall b a. (b -> a -> b) -> b -> ListT m a -> b)
-> (forall b a. (b -> a -> b) -> b -> ListT m a -> b)
-> (forall a. (a -> a -> a) -> ListT m a -> a)
-> (forall a. (a -> a -> a) -> ListT m a -> a)
-> (forall a. ListT m a -> [a])
-> (forall a. ListT m a -> Bool)
-> (forall a. ListT m a -> Int)
-> (forall a. Eq a => a -> ListT m a -> Bool)
-> (forall a. Ord a => ListT m a -> a)
-> (forall a. Ord a => ListT m a -> a)
-> (forall a. Num a => ListT m a -> a)
-> (forall a. Num a => ListT m a -> a)
-> Foldable (ListT m)
forall a. Eq a => a -> ListT m a -> Bool
forall a. Num a => ListT m a -> a
forall a. Ord a => ListT m a -> a
forall m. Monoid m => ListT m m -> m
forall a. ListT m a -> Bool
forall a. ListT m a -> Int
forall a. ListT m a -> [a]
forall a. (a -> a -> a) -> ListT m a -> a
forall m a. Monoid m => (a -> m) -> ListT m a -> m
forall b a. (b -> a -> b) -> b -> ListT m a -> b
forall a b. (a -> b -> b) -> b -> ListT m a -> b
forall (m :: * -> *) a.
(Foldable m, Eq a) =>
a -> ListT m a -> Bool
forall (m :: * -> *) a. (Foldable m, Num a) => ListT m a -> a
forall (m :: * -> *) a. (Foldable m, Ord a) => ListT m a -> a
forall (m :: * -> *) m. (Foldable m, Monoid m) => ListT m m -> m
forall (m :: * -> *) a. Foldable m => ListT m a -> Bool
forall (m :: * -> *) a. Foldable m => ListT m a -> Int
forall (m :: * -> *) a. Foldable m => ListT m a -> [a]
forall (m :: * -> *) a.
Foldable m =>
(a -> a -> a) -> ListT m a -> a
forall (m :: * -> *) m a.
(Foldable m, Monoid m) =>
(a -> m) -> ListT m a -> m
forall (m :: * -> *) b a.
Foldable m =>
(b -> a -> b) -> b -> ListT m a -> b
forall (m :: * -> *) a b.
Foldable m =>
(a -> b -> b) -> b -> ListT m a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
product :: ListT m a -> a
$cproduct :: forall (m :: * -> *) a. (Foldable m, Num a) => ListT m a -> a
sum :: ListT m a -> a
$csum :: forall (m :: * -> *) a. (Foldable m, Num a) => ListT m a -> a
minimum :: ListT m a -> a
$cminimum :: forall (m :: * -> *) a. (Foldable m, Ord a) => ListT m a -> a
maximum :: ListT m a -> a
$cmaximum :: forall (m :: * -> *) a. (Foldable m, Ord a) => ListT m a -> a
elem :: a -> ListT m a -> Bool
$celem :: forall (m :: * -> *) a.
(Foldable m, Eq a) =>
a -> ListT m a -> Bool
length :: ListT m a -> Int
$clength :: forall (m :: * -> *) a. Foldable m => ListT m a -> Int
null :: ListT m a -> Bool
$cnull :: forall (m :: * -> *) a. Foldable m => ListT m a -> Bool
toList :: ListT m a -> [a]
$ctoList :: forall (m :: * -> *) a. Foldable m => ListT m a -> [a]
foldl1 :: (a -> a -> a) -> ListT m a -> a
$cfoldl1 :: forall (m :: * -> *) a.
Foldable m =>
(a -> a -> a) -> ListT m a -> a
foldr1 :: (a -> a -> a) -> ListT m a -> a
$cfoldr1 :: forall (m :: * -> *) a.
Foldable m =>
(a -> a -> a) -> ListT m a -> a
foldl' :: (b -> a -> b) -> b -> ListT m a -> b
$cfoldl' :: forall (m :: * -> *) b a.
Foldable m =>
(b -> a -> b) -> b -> ListT m a -> b
foldl :: (b -> a -> b) -> b -> ListT m a -> b
$cfoldl :: forall (m :: * -> *) b a.
Foldable m =>
(b -> a -> b) -> b -> ListT m a -> b
foldr' :: (a -> b -> b) -> b -> ListT m a -> b
$cfoldr' :: forall (m :: * -> *) a b.
Foldable m =>
(a -> b -> b) -> b -> ListT m a -> b
foldr :: (a -> b -> b) -> b -> ListT m a -> b
$cfoldr :: forall (m :: * -> *) a b.
Foldable m =>
(a -> b -> b) -> b -> ListT m a -> b
foldMap' :: (a -> m) -> ListT m a -> m
$cfoldMap' :: forall (m :: * -> *) m a.
(Foldable m, Monoid m) =>
(a -> m) -> ListT m a -> m
foldMap :: (a -> m) -> ListT m a -> m
$cfoldMap :: forall (m :: * -> *) m a.
(Foldable m, Monoid m) =>
(a -> m) -> ListT m a -> m
fold :: ListT m m -> m
$cfold :: forall (m :: * -> *) m. (Foldable m, Monoid m) => ListT m m -> m
Foldable, Functor (ListT m)
Foldable (ListT m)
Functor (ListT m)
-> Foldable (ListT m)
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> ListT m a -> f (ListT m b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    ListT m (f a) -> f (ListT m a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> ListT m a -> m (ListT m b))
-> (forall (m :: * -> *) a.
    Monad m =>
    ListT m (m a) -> m (ListT m a))
-> Traversable (ListT m)
(a -> f b) -> ListT m a -> f (ListT m b)
forall (t :: * -> *).
Functor t
-> Foldable t
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *). Traversable m => Functor (ListT m)
forall (m :: * -> *). Traversable m => Foldable (ListT m)
forall (m :: * -> *) (m :: * -> *) a.
(Traversable m, Monad m) =>
ListT m (m a) -> m (ListT m a)
forall (m :: * -> *) (f :: * -> *) a.
(Traversable m, Applicative f) =>
ListT m (f a) -> f (ListT m a)
forall (m :: * -> *) (m :: * -> *) a b.
(Traversable m, Monad m) =>
(a -> m b) -> ListT m a -> m (ListT m b)
forall (m :: * -> *) (f :: * -> *) a b.
(Traversable m, Applicative f) =>
(a -> f b) -> ListT m a -> f (ListT m b)
forall (m :: * -> *) a. Monad m => ListT m (m a) -> m (ListT m a)
forall (f :: * -> *) a.
Applicative f =>
ListT m (f a) -> f (ListT m a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> ListT m a -> m (ListT m b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> ListT m a -> f (ListT m b)
sequence :: ListT m (m a) -> m (ListT m a)
$csequence :: forall (m :: * -> *) (m :: * -> *) a.
(Traversable m, Monad m) =>
ListT m (m a) -> m (ListT m a)
mapM :: (a -> m b) -> ListT m a -> m (ListT m b)
$cmapM :: forall (m :: * -> *) (m :: * -> *) a b.
(Traversable m, Monad m) =>
(a -> m b) -> ListT m a -> m (ListT m b)
sequenceA :: ListT m (f a) -> f (ListT m a)
$csequenceA :: forall (m :: * -> *) (f :: * -> *) a.
(Traversable m, Applicative f) =>
ListT m (f a) -> f (ListT m a)
traverse :: (a -> f b) -> ListT m a -> f (ListT m b)
$ctraverse :: forall (m :: * -> *) (f :: * -> *) a b.
(Traversable m, Applicative f) =>
(a -> f b) -> ListT m a -> f (ListT m b)
$cp2Traversable :: forall (m :: * -> *). Traversable m => Foldable (ListT m)
$cp1Traversable :: forall (m :: * -> *). Traversable m => Functor (ListT m)
Traversable, (forall x. ListT m a -> Rep (ListT m a) x)
-> (forall x. Rep (ListT m a) x -> ListT m a)
-> Generic (ListT m a)
forall x. Rep (ListT m a) x -> ListT m a
forall x. ListT m a -> Rep (ListT m a) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall (m :: * -> *) a x. Rep (ListT m a) x -> ListT m a
forall (m :: * -> *) a x. ListT m a -> Rep (ListT m a) x
$cto :: forall (m :: * -> *) a x. Rep (ListT m a) x -> ListT m a
$cfrom :: forall (m :: * -> *) a x. ListT m a -> Rep (ListT m a) x
Generic)

deriving instance Show (m (Maybe (a, ListT m a))) => Show (ListT m a)
deriving instance Read (m (Maybe (a, ListT m a))) => Read (ListT m a)
deriving instance Eq (m (Maybe (a, ListT m a))) => Eq (ListT m a)
deriving instance Ord (m (Maybe (a, ListT m a))) => Ord (ListT m a)
deriving instance (Typeable m, Typeable a, Data (m (Maybe (a, ListT m a)))) => Data (ListT m a)

instance Eq1 m => Eq1 (ListT m) where
  liftEq :: (a -> b -> Bool) -> ListT m a -> ListT m b -> Bool
liftEq a -> b -> Bool
eq = ListT m a -> ListT m b -> Bool
go
    where
      go :: ListT m a -> ListT m b -> Bool
go (ListT m (Maybe (a, ListT m a))
m) (ListT m (Maybe (b, ListT m b))
n) = (Maybe (a, ListT m a) -> Maybe (b, ListT m b) -> Bool)
-> m (Maybe (a, ListT m a)) -> m (Maybe (b, ListT m b)) -> Bool
forall (f :: * -> *) a b.
Eq1 f =>
(a -> b -> Bool) -> f a -> f b -> Bool
liftEq (((a, ListT m a) -> (b, ListT m b) -> Bool)
-> Maybe (a, ListT m a) -> Maybe (b, ListT m b) -> Bool
forall (f :: * -> *) a b.
Eq1 f =>
(a -> b -> Bool) -> f a -> f b -> Bool
liftEq (\(a
a, ListT m a
as) (b
b, ListT m b
bs) -> a -> b -> Bool
eq a
a b
b Bool -> Bool -> Bool
&& ListT m a -> ListT m b -> Bool
go ListT m a
as ListT m b
bs)) m (Maybe (a, ListT m a))
m m (Maybe (b, ListT m b))
n

instance Ord1 m => Ord1 (ListT m) where
  liftCompare :: (a -> b -> Ordering) -> ListT m a -> ListT m b -> Ordering
liftCompare a -> b -> Ordering
cmp = ListT m a -> ListT m b -> Ordering
go
    where
      go :: ListT m a -> ListT m b -> Ordering
go (ListT m (Maybe (a, ListT m a))
m) (ListT m (Maybe (b, ListT m b))
n) = (Maybe (a, ListT m a) -> Maybe (b, ListT m b) -> Ordering)
-> m (Maybe (a, ListT m a)) -> m (Maybe (b, ListT m b)) -> Ordering
forall (f :: * -> *) a b.
Ord1 f =>
(a -> b -> Ordering) -> f a -> f b -> Ordering
liftCompare (((a, ListT m a) -> (b, ListT m b) -> Ordering)
-> Maybe (a, ListT m a) -> Maybe (b, ListT m b) -> Ordering
forall (f :: * -> *) a b.
Ord1 f =>
(a -> b -> Ordering) -> f a -> f b -> Ordering
liftCompare (\(a
a, ListT m a
as) (b
b, ListT m b
bs) -> a -> b -> Ordering
cmp a
a b
b Ordering -> Ordering -> Ordering
forall a. Semigroup a => a -> a -> a
<> ListT m a -> ListT m b -> Ordering
go ListT m a
as ListT m b
bs)) m (Maybe (a, ListT m a))
m m (Maybe (b, ListT m b))
n

instance Show1 m => Show1 (ListT m) where
  -- I wish I were joking.
  liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> ListT m a -> ShowS
liftShowsPrec Int -> a -> ShowS
sp ([a] -> ShowS
sl :: [a] -> ShowS) = Int -> ListT m a -> ShowS
mark
    where
      bob :: Int -> m (Maybe (a, ListT m a)) -> ShowS
      bob :: Int -> m (Maybe (a, ListT m a)) -> ShowS
bob = (Int -> Maybe (a, ListT m a) -> ShowS)
-> ([Maybe (a, ListT m a)] -> ShowS)
-> Int
-> m (Maybe (a, ListT m a))
-> ShowS
forall (f :: * -> *) a.
Show1 f =>
(Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> f a -> ShowS
liftShowsPrec Int -> Maybe (a, ListT m a) -> ShowS
jill [Maybe (a, ListT m a)] -> ShowS
edith

      edith :: [Maybe (a, ListT m a)] -> ShowS
      edith :: [Maybe (a, ListT m a)] -> ShowS
edith = (Int -> (a, ListT m a) -> ShowS)
-> ([(a, ListT m a)] -> ShowS) -> [Maybe (a, ListT m a)] -> ShowS
forall (f :: * -> *) a.
Show1 f =>
(Int -> a -> ShowS) -> ([a] -> ShowS) -> [f a] -> ShowS
liftShowList Int -> (a, ListT m a) -> ShowS
jack [(a, ListT m a)] -> ShowS
martha

      jill :: Int -> Maybe (a, ListT m a) -> ShowS
      jill :: Int -> Maybe (a, ListT m a) -> ShowS
jill = (Int -> (a, ListT m a) -> ShowS)
-> ([(a, ListT m a)] -> ShowS)
-> Int
-> Maybe (a, ListT m a)
-> ShowS
forall (f :: * -> *) a.
Show1 f =>
(Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> f a -> ShowS
liftShowsPrec Int -> (a, ListT m a) -> ShowS
jack [(a, ListT m a)] -> ShowS
martha

      martha :: [(a, ListT m a)] -> ShowS
      martha :: [(a, ListT m a)] -> ShowS
martha = (Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> ListT m a -> ShowS)
-> ([ListT m a] -> ShowS)
-> [(a, ListT m a)]
-> ShowS
forall (f :: * -> * -> *) a b.
Show2 f =>
(Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> [f a b]
-> ShowS
liftShowList2 Int -> a -> ShowS
sp [a] -> ShowS
sl Int -> ListT m a -> ShowS
mark [ListT m a] -> ShowS
juan

      mark :: Int -> ListT m a -> ShowS
      mark :: Int -> ListT m a -> ShowS
mark Int
d (ListT m (Maybe (a, ListT m a))
m) = (Int -> m (Maybe (a, ListT m a)) -> ShowS)
-> String -> Int -> m (Maybe (a, ListT m a)) -> ShowS
forall a. (Int -> a -> ShowS) -> String -> Int -> a -> ShowS
showsUnaryWith Int -> m (Maybe (a, ListT m a)) -> ShowS
bob String
"ListT" Int
d m (Maybe (a, ListT m a))
m

      juan :: [ListT m a] -> ShowS
      juan :: [ListT m a] -> ShowS
juan = (Int -> a -> ShowS) -> ([a] -> ShowS) -> [ListT m a] -> ShowS
forall (f :: * -> *) a.
Show1 f =>
(Int -> a -> ShowS) -> ([a] -> ShowS) -> [f a] -> ShowS
liftShowList Int -> a -> ShowS
sp [a] -> ShowS
sl

      jack :: Int -> (a, ListT m a) -> ShowS
      jack :: Int -> (a, ListT m a) -> ShowS
jack = (Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> ListT m a -> ShowS)
-> ([ListT m a] -> ShowS)
-> Int
-> (a, ListT m a)
-> ShowS
forall (f :: * -> * -> *) a b.
Show2 f =>
(Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> Int
-> f a b
-> ShowS
liftShowsPrec2 Int -> a -> ShowS
sp [a] -> ShowS
sl Int -> ListT m a -> ShowS
mark [ListT m a] -> ShowS
juan

instance Monad m => Semigroup (ListT m a) where
  <> :: ListT m a -> ListT m a -> ListT m a
(<>) (ListT m (Maybe (a, ListT m a))
m1) (ListT m (Maybe (a, ListT m a))
m2) =
    m (Maybe (a, ListT m a)) -> ListT m a
forall (m :: * -> *) a. m (Maybe (a, ListT m a)) -> ListT m a
ListT (m (Maybe (a, ListT m a)) -> ListT m a)
-> m (Maybe (a, ListT m a)) -> ListT m a
forall a b. (a -> b) -> a -> b
$
      m (Maybe (a, ListT m a))
m1 m (Maybe (a, ListT m a))
-> (Maybe (a, ListT m a) -> m (Maybe (a, ListT m a)))
-> m (Maybe (a, ListT m a))
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>=
        \case
          Maybe (a, ListT m a)
Nothing ->
            m (Maybe (a, ListT m a))
m2
          Just (a
h1, ListT m a
s1') ->
            Maybe (a, ListT m a) -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. Monad m => a -> m a
return ((a, ListT m a) -> Maybe (a, ListT m a)
forall a. a -> Maybe a
Just (a
h1, (ListT m a -> ListT m a -> ListT m a
forall a. Semigroup a => a -> a -> a
(<>) ListT m a
s1' (m (Maybe (a, ListT m a)) -> ListT m a
forall (m :: * -> *) a. m (Maybe (a, ListT m a)) -> ListT m a
ListT m (Maybe (a, ListT m a))
m2))))

instance Monad m => Monoid (ListT m a) where
  mempty :: ListT m a
mempty =
    m (Maybe (a, ListT m a)) -> ListT m a
forall (m :: * -> *) a. m (Maybe (a, ListT m a)) -> ListT m a
ListT (m (Maybe (a, ListT m a)) -> ListT m a)
-> m (Maybe (a, ListT m a)) -> ListT m a
forall a b. (a -> b) -> a -> b
$ 
      Maybe (a, ListT m a) -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe (a, ListT m a)
forall a. Maybe a
Nothing
  mappend :: ListT m a -> ListT m a -> ListT m a
mappend = ListT m a -> ListT m a -> ListT m a
forall a. Semigroup a => a -> a -> a
(<>)

instance Functor m => Functor (ListT m) where
  fmap :: (a -> b) -> ListT m a -> ListT m b
fmap a -> b
f = ListT m a -> ListT m b
go
    where
      go :: ListT m a -> ListT m b
go =
        m (Maybe (b, ListT m b)) -> ListT m b
forall (m :: * -> *) a. m (Maybe (a, ListT m a)) -> ListT m a
ListT (m (Maybe (b, ListT m b)) -> ListT m b)
-> (ListT m a -> m (Maybe (b, ListT m b)))
-> ListT m a
-> ListT m b
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. ((Maybe (a, ListT m a) -> Maybe (b, ListT m b))
-> m (Maybe (a, ListT m a)) -> m (Maybe (b, ListT m b))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((Maybe (a, ListT m a) -> Maybe (b, ListT m b))
 -> m (Maybe (a, ListT m a)) -> m (Maybe (b, ListT m b)))
-> (((a, ListT m a) -> (b, ListT m b))
    -> Maybe (a, ListT m a) -> Maybe (b, ListT m b))
-> ((a, ListT m a) -> (b, ListT m b))
-> m (Maybe (a, ListT m a))
-> m (Maybe (b, ListT m b))
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. ((a, ListT m a) -> (b, ListT m b))
-> Maybe (a, ListT m a) -> Maybe (b, ListT m b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap) ((a -> b)
-> (ListT m a -> ListT m b) -> (a, ListT m a) -> (b, ListT m b)
forall a b c d. (a -> b) -> (c -> d) -> (a, c) -> (b, d)
bimapPair' a -> b
f ListT m a -> ListT m b
go) (m (Maybe (a, ListT m a)) -> m (Maybe (b, ListT m b)))
-> (ListT m a -> m (Maybe (a, ListT m a)))
-> ListT m a
-> m (Maybe (b, ListT m b))
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. ListT m a -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons

instance (Monad m, Functor m) => Applicative (ListT m) where
  pure :: a -> ListT m a
pure = 
    a -> ListT m a
forall (m :: * -> *) a. Monad m => a -> m a
return
  <*> :: ListT m (a -> b) -> ListT m a -> ListT m b
(<*>) = 
    ListT m (a -> b) -> ListT m a -> ListT m b
forall (m :: * -> *) a b. Monad m => m (a -> b) -> m a -> m b
ap
  -- This is just like liftM2, but it uses fmap over the second
  -- action. liftM2 can't do that, because it has to deal with
  -- the possibility that someone defines liftA2 = liftM2 and
  -- fmap f = (pure f <*>) (leaving (<*>) to the default).
  liftA2 :: (a -> b -> c) -> ListT m a -> ListT m b -> ListT m c
liftA2 a -> b -> c
f ListT m a
m1 ListT m b
m2 = do
    a
x1 <- ListT m a
m1
    (b -> c) -> ListT m b -> ListT m c
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (a -> b -> c
f a
x1) ListT m b
m2
  *> :: ListT m a -> ListT m b -> ListT m b
(*>) = ListT m a -> ListT m b -> ListT m b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
(>>)

instance (Monad m, Functor m) => Alternative (ListT m) where
  empty :: ListT m a
empty = 
    ListT m a -> ListT m a
forall a. a -> a
inline ListT m a
forall a. Monoid a => a
mempty
  <|> :: ListT m a -> ListT m a -> ListT m a
(<|>) = 
    (ListT m a -> ListT m a -> ListT m a)
-> ListT m a -> ListT m a -> ListT m a
forall a. a -> a
inline ListT m a -> ListT m a -> ListT m a
forall a. Monoid a => a -> a -> a
mappend

instance Monad m => Monad (ListT m) where
  return :: a -> ListT m a
return a
a =
    m (Maybe (a, ListT m a)) -> ListT m a
forall (m :: * -> *) a. m (Maybe (a, ListT m a)) -> ListT m a
ListT (m (Maybe (a, ListT m a)) -> ListT m a)
-> m (Maybe (a, ListT m a)) -> ListT m a
forall a b. (a -> b) -> a -> b
$ Maybe (a, ListT m a) -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. Monad m => a -> m a
return ((a, ListT m a) -> Maybe (a, ListT m a)
forall a. a -> Maybe a
Just (a
a, (m (Maybe (a, ListT m a)) -> ListT m a
forall (m :: * -> *) a. m (Maybe (a, ListT m a)) -> ListT m a
ListT (Maybe (a, ListT m a) -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe (a, ListT m a)
forall a. Maybe a
Nothing))))
  -- We use a go function so GHC can inline k2
  -- if it likes.
  >>= :: ListT m a -> (a -> ListT m b) -> ListT m b
(>>=) ListT m a
s10 a -> ListT m b
k2 = ListT m a -> ListT m b
go ListT m a
s10
    where
      go :: ListT m a -> ListT m b
go ListT m a
s1 =
        m (Maybe (b, ListT m b)) -> ListT m b
forall (m :: * -> *) a. m (Maybe (a, ListT m a)) -> ListT m a
ListT (m (Maybe (b, ListT m b)) -> ListT m b)
-> m (Maybe (b, ListT m b)) -> ListT m b
forall a b. (a -> b) -> a -> b
$
          ListT m a -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons ListT m a
s1 m (Maybe (a, ListT m a))
-> (Maybe (a, ListT m a) -> m (Maybe (b, ListT m b)))
-> m (Maybe (b, ListT m b))
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>=
            \case
              Maybe (a, ListT m a)
Nothing ->
                Maybe (b, ListT m b) -> m (Maybe (b, ListT m b))
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe (b, ListT m b)
forall a. Maybe a
Nothing
              Just (a
h1, ListT m a
t1) ->
                ListT m b -> m (Maybe (b, ListT m b))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons (ListT m b -> m (Maybe (b, ListT m b)))
-> ListT m b -> m (Maybe (b, ListT m b))
forall a b. (a -> b) -> a -> b
$ a -> ListT m b
k2 a
h1 ListT m b -> ListT m b -> ListT m b
forall a. Semigroup a => a -> a -> a
<> ListT m a -> ListT m b
go ListT m a
t1

instance Monad m => MonadFail (ListT m) where
  fail :: String -> ListT m a
fail String
_ =
    ListT m a -> ListT m a
forall a. a -> a
inline ListT m a
forall a. Monoid a => a
mempty

instance Monad m => MonadPlus (ListT m) where
  mzero :: ListT m a
mzero = 
    ListT m a -> ListT m a
forall a. a -> a
inline ListT m a
forall a. Monoid a => a
mempty
  mplus :: ListT m a -> ListT m a -> ListT m a
mplus = 
    (ListT m a -> ListT m a -> ListT m a)
-> ListT m a -> ListT m a -> ListT m a
forall a. a -> a
inline ListT m a -> ListT m a -> ListT m a
forall a. Monoid a => a -> a -> a
mappend

instance MonadTrans ListT where
  lift :: m a -> ListT m a
lift =
    m (Maybe (a, ListT m a)) -> ListT m a
forall (m :: * -> *) a. m (Maybe (a, ListT m a)) -> ListT m a
ListT (m (Maybe (a, ListT m a)) -> ListT m a)
-> (m a -> m (Maybe (a, ListT m a))) -> m a -> ListT m a
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (a -> Maybe (a, ListT m a)) -> m a -> m (Maybe (a, ListT m a))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\a
a -> (a, ListT m a) -> Maybe (a, ListT m a)
forall a. a -> Maybe a
Just (a
a, ListT m a
forall a. Monoid a => a
mempty))

instance MonadIO m => MonadIO (ListT m) where
  liftIO :: IO a -> ListT m a
liftIO =
    m a -> ListT m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (m a -> ListT m a) -> (IO a -> m a) -> IO a -> ListT m a
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. IO a -> m a
forall (m :: * -> *) a. MonadIO m => IO a -> m a
liftIO

instance MFunctor ListT where
  hoist :: (forall a. m a -> n a) -> ListT m b -> ListT n b
hoist forall a. m a -> n a
f = ListT m b -> ListT n b
go
    where
      go :: ListT m b -> ListT n b
go = n (Maybe (b, ListT n b)) -> ListT n b
forall (m :: * -> *) a. m (Maybe (a, ListT m a)) -> ListT m a
ListT (n (Maybe (b, ListT n b)) -> ListT n b)
-> (ListT m b -> n (Maybe (b, ListT n b)))
-> ListT m b
-> ListT n b
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. m (Maybe (b, ListT n b)) -> n (Maybe (b, ListT n b))
forall a. m a -> n a
f (m (Maybe (b, ListT n b)) -> n (Maybe (b, ListT n b)))
-> (ListT m b -> m (Maybe (b, ListT n b)))
-> ListT m b
-> n (Maybe (b, ListT n b))
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. ((Maybe (b, ListT m b) -> Maybe (b, ListT n b))
-> m (Maybe (b, ListT m b)) -> m (Maybe (b, ListT n b))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((Maybe (b, ListT m b) -> Maybe (b, ListT n b))
 -> m (Maybe (b, ListT m b)) -> m (Maybe (b, ListT n b)))
-> (((b, ListT m b) -> (b, ListT n b))
    -> Maybe (b, ListT m b) -> Maybe (b, ListT n b))
-> ((b, ListT m b) -> (b, ListT n b))
-> m (Maybe (b, ListT m b))
-> m (Maybe (b, ListT n b))
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. ((b, ListT m b) -> (b, ListT n b))
-> Maybe (b, ListT m b) -> Maybe (b, ListT n b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap) ((b -> b)
-> (ListT m b -> ListT n b) -> (b, ListT m b) -> (b, ListT n b)
forall a b c d. (a -> b) -> (c -> d) -> (a, c) -> (b, d)
bimapPair' b -> b
forall k (cat :: k -> k -> *) (a :: k). Category cat => cat a a
id ListT m b -> ListT n b
go) (m (Maybe (b, ListT m b)) -> m (Maybe (b, ListT n b)))
-> (ListT m b -> m (Maybe (b, ListT m b)))
-> ListT m b
-> m (Maybe (b, ListT n b))
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. ListT m b -> m (Maybe (b, ListT m b))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons

instance MMonad ListT where
  embed :: (forall a. m a -> ListT n a) -> ListT m b -> ListT n b
embed forall a. m a -> ListT n a
f (ListT m (Maybe (b, ListT m b))
m) =
    m (Maybe (b, ListT m b)) -> ListT n (Maybe (b, ListT m b))
forall a. m a -> ListT n a
f m (Maybe (b, ListT m b))
m ListT n (Maybe (b, ListT m b))
-> (Maybe (b, ListT m b) -> ListT n b) -> ListT n b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \case
      Maybe (b, ListT m b)
Nothing -> ListT n b
forall (m :: * -> *) a. MonadPlus m => m a
mzero
      Just (b
h, ListT m b
t) -> n (Maybe (b, ListT n b)) -> ListT n b
forall (m :: * -> *) a. m (Maybe (a, ListT m a)) -> ListT m a
ListT (n (Maybe (b, ListT n b)) -> ListT n b)
-> n (Maybe (b, ListT n b)) -> ListT n b
forall a b. (a -> b) -> a -> b
$ Maybe (b, ListT n b) -> n (Maybe (b, ListT n b))
forall (m :: * -> *) a. Monad m => a -> m a
return (Maybe (b, ListT n b) -> n (Maybe (b, ListT n b)))
-> Maybe (b, ListT n b) -> n (Maybe (b, ListT n b))
forall a b. (a -> b) -> a -> b
$ (b, ListT n b) -> Maybe (b, ListT n b)
forall a. a -> Maybe a
Just ((b, ListT n b) -> Maybe (b, ListT n b))
-> (b, ListT n b) -> Maybe (b, ListT n b)
forall a b. (a -> b) -> a -> b
$ (b
h, (forall a. m a -> ListT n a) -> ListT m b -> ListT n b
forall (t :: (* -> *) -> * -> *) (n :: * -> *) (m :: * -> *) b.
(MMonad t, Monad n) =>
(forall a. m a -> t n a) -> t m b -> t n b
embed forall a. m a -> ListT n a
f ListT m b
t)

instance MonadBase b m => MonadBase b (ListT m) where
  liftBase :: b α -> ListT m α
liftBase =
    m α -> ListT m α
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (m α -> ListT m α) -> (b α -> m α) -> b α -> ListT m α
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. b α -> m α
forall (b :: * -> *) (m :: * -> *) α. MonadBase b m => b α -> m α
liftBase

instance MonadBaseControl b m => MonadBaseControl b (ListT m) where
  type StM (ListT m) a =
    StM m (Maybe (a, ListT m a))
  liftBaseWith :: (RunInBase (ListT m) b -> b a) -> ListT m a
liftBaseWith RunInBase (ListT m) b -> b a
runToBase =
    m a -> ListT m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (m a -> ListT m a) -> m a -> ListT m a
forall a b. (a -> b) -> a -> b
$ (RunInBase m b -> b a) -> m a
forall (b :: * -> *) (m :: * -> *) a.
MonadBaseControl b m =>
(RunInBase m b -> b a) -> m a
liftBaseWith ((RunInBase m b -> b a) -> m a) -> (RunInBase m b -> b a) -> m a
forall a b. (a -> b) -> a -> b
$ \RunInBase m b
runInner -> 
      RunInBase (ListT m) b -> b a
runToBase (RunInBase (ListT m) b -> b a) -> RunInBase (ListT m) b -> b a
forall a b. (a -> b) -> a -> b
$ m (Maybe (a, ListT m a)) -> b (StM m (Maybe (a, ListT m a)))
RunInBase m b
runInner (m (Maybe (a, ListT m a)) -> b (StM m (Maybe (a, ListT m a))))
-> (ListT m a -> m (Maybe (a, ListT m a)))
-> ListT m a
-> b (StM m (Maybe (a, ListT m a)))
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. ListT m a -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons
  restoreM :: StM (ListT m) a -> ListT m a
restoreM StM (ListT m) a
inner =
    m (Maybe (a, ListT m a)) -> ListT m (Maybe (a, ListT m a))
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (StM m (Maybe (a, ListT m a)) -> m (Maybe (a, ListT m a))
forall (b :: * -> *) (m :: * -> *) a.
MonadBaseControl b m =>
StM m a -> m a
restoreM StM m (Maybe (a, ListT m a))
StM (ListT m) a
inner) ListT m (Maybe (a, ListT m a))
-> (Maybe (a, ListT m a) -> ListT m a) -> ListT m a
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \case
      Maybe (a, ListT m a)
Nothing -> ListT m a
forall (m :: * -> *) a. MonadPlus m => m a
mzero
      Just (a
h, ListT m a
t) -> a -> ListT m a -> ListT m a
forall (m :: * -> *) a. Monad m => a -> ListT m a -> ListT m a
cons a
h ListT m a
t

instance MonadError e m => MonadError e (ListT m) where
  throwError :: e -> ListT m a
throwError = m (Maybe (a, ListT m a)) -> ListT m a
forall (m :: * -> *) a. m (Maybe (a, ListT m a)) -> ListT m a
ListT (m (Maybe (a, ListT m a)) -> ListT m a)
-> (e -> m (Maybe (a, ListT m a))) -> e -> ListT m a
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. e -> m (Maybe (a, ListT m a))
forall e (m :: * -> *) a. MonadError e m => e -> m a
throwError
  catchError :: ListT m a -> (e -> ListT m a) -> ListT m a
catchError ListT m a
m e -> ListT m a
handler = m (Maybe (a, ListT m a)) -> ListT m a
forall (m :: * -> *) a. m (Maybe (a, ListT m a)) -> ListT m a
ListT (m (Maybe (a, ListT m a)) -> ListT m a)
-> m (Maybe (a, ListT m a)) -> ListT m a
forall a b. (a -> b) -> a -> b
$ m (Maybe (a, ListT m a))
-> (e -> m (Maybe (a, ListT m a))) -> m (Maybe (a, ListT m a))
forall e (m :: * -> *) a.
MonadError e m =>
m a -> (e -> m a) -> m a
catchError (ListT m a -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons ListT m a
m) ((e -> m (Maybe (a, ListT m a))) -> m (Maybe (a, ListT m a)))
-> (e -> m (Maybe (a, ListT m a))) -> m (Maybe (a, ListT m a))
forall a b. (a -> b) -> a -> b
$ ListT m a -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons (ListT m a -> m (Maybe (a, ListT m a)))
-> (e -> ListT m a) -> e -> m (Maybe (a, ListT m a))
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. e -> ListT m a
handler

instance MonadReader e m => MonadReader e (ListT m) where
  ask :: ListT m e
ask = m e -> ListT m e
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift m e
forall r (m :: * -> *). MonadReader r m => m r
ask
  reader :: (e -> a) -> ListT m a
reader = m a -> ListT m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (m a -> ListT m a) -> ((e -> a) -> m a) -> (e -> a) -> ListT m a
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (e -> a) -> m a
forall r (m :: * -> *) a. MonadReader r m => (r -> a) -> m a
reader
  local :: (e -> e) -> ListT m a -> ListT m a
local e -> e
r = ListT m a -> ListT m a
go
    where
      go :: ListT m a -> ListT m a
go (ListT m (Maybe (a, ListT m a))
m) = m (Maybe (a, ListT m a)) -> ListT m a
forall (m :: * -> *) a. m (Maybe (a, ListT m a)) -> ListT m a
ListT (m (Maybe (a, ListT m a)) -> ListT m a)
-> m (Maybe (a, ListT m a)) -> ListT m a
forall a b. (a -> b) -> a -> b
$ (e -> e) -> m (Maybe (a, ListT m a)) -> m (Maybe (a, ListT m a))
forall r (m :: * -> *) a. MonadReader r m => (r -> r) -> m a -> m a
local e -> e
r ((Maybe (a, ListT m a) -> Maybe (a, ListT m a))
-> m (Maybe (a, ListT m a)) -> m (Maybe (a, ListT m a))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (((a, ListT m a) -> (a, ListT m a))
-> Maybe (a, ListT m a) -> Maybe (a, ListT m a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((ListT m a -> ListT m a) -> (a, ListT m a) -> (a, ListT m a)
forall b c a. (b -> c) -> (a, b) -> (a, c)
secondPair' ListT m a -> ListT m a
go)) m (Maybe (a, ListT m a))
m)

instance MonadState e m => MonadState e (ListT m) where
  get :: ListT m e
get = m e -> ListT m e
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift m e
forall s (m :: * -> *). MonadState s m => m s
get
  put :: e -> ListT m ()
put = m () -> ListT m ()
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (m () -> ListT m ()) -> (e -> m ()) -> e -> ListT m ()
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. e -> m ()
forall s (m :: * -> *). MonadState s m => s -> m ()
put
  state :: (e -> (a, e)) -> ListT m a
state = m a -> ListT m a
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (m a -> ListT m a)
-> ((e -> (a, e)) -> m a) -> (e -> (a, e)) -> ListT m a
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (e -> (a, e)) -> m a
forall s (m :: * -> *) a. MonadState s m => (s -> (a, s)) -> m a
state

instance Monad m => MonadLogic (ListT m) where
  msplit :: ListT m a -> ListT m (Maybe (a, ListT m a))
msplit (ListT m (Maybe (a, ListT m a))
m) = m (Maybe (a, ListT m a)) -> ListT m (Maybe (a, ListT m a))
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift m (Maybe (a, ListT m a))
m

  interleave :: ListT m a -> ListT m a -> ListT m a
interleave ListT m a
m1 ListT m a
m2 = m (Maybe (a, ListT m a)) -> ListT m a
forall (m :: * -> *) a. m (Maybe (a, ListT m a)) -> ListT m a
ListT (m (Maybe (a, ListT m a)) -> ListT m a)
-> m (Maybe (a, ListT m a)) -> ListT m a
forall a b. (a -> b) -> a -> b
$ ListT m a -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons ListT m a
m1 m (Maybe (a, ListT m a))
-> (Maybe (a, ListT m a) -> m (Maybe (a, ListT m a)))
-> m (Maybe (a, ListT m a))
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \case
    Maybe (a, ListT m a)
Nothing -> ListT m a -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons ListT m a
m2
    Just (a
a, ListT m a
m1') -> ListT m a -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons (ListT m a -> m (Maybe (a, ListT m a)))
-> ListT m a -> m (Maybe (a, ListT m a))
forall a b. (a -> b) -> a -> b
$ a -> ListT m a -> ListT m a
forall (m :: * -> *) a. Monad m => a -> ListT m a -> ListT m a
cons a
a (ListT m a -> ListT m a -> ListT m a
forall (m :: * -> *) a. MonadLogic m => m a -> m a -> m a
interleave ListT m a
m2 ListT m a
m1')

  ListT m a
m >>- :: ListT m a -> (a -> ListT m b) -> ListT m b
>>- a -> ListT m b
f = m (Maybe (b, ListT m b)) -> ListT m b
forall (m :: * -> *) a. m (Maybe (a, ListT m a)) -> ListT m a
ListT (m (Maybe (b, ListT m b)) -> ListT m b)
-> m (Maybe (b, ListT m b)) -> ListT m b
forall a b. (a -> b) -> a -> b
$ ListT m a -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons ListT m a
m m (Maybe (a, ListT m a))
-> (Maybe (a, ListT m a) -> m (Maybe (b, ListT m b)))
-> m (Maybe (b, ListT m b))
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \case
    Maybe (a, ListT m a)
Nothing -> ListT m b -> m (Maybe (b, ListT m b))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons ListT m b
forall (f :: * -> *) a. Alternative f => f a
empty
    Just (a
a, ListT m a
m') -> ListT m b -> m (Maybe (b, ListT m b))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons (ListT m b -> m (Maybe (b, ListT m b)))
-> ListT m b -> m (Maybe (b, ListT m b))
forall a b. (a -> b) -> a -> b
$ ListT m b -> ListT m b -> ListT m b
forall (m :: * -> *) a. MonadLogic m => m a -> m a -> m a
interleave (a -> ListT m b
f a
a) (ListT m a
m' ListT m a -> (a -> ListT m b) -> ListT m b
forall (m :: * -> *) a b. MonadLogic m => m a -> (a -> m b) -> m b
>>- a -> ListT m b
f)

  ifte :: ListT m a -> (a -> ListT m b) -> ListT m b -> ListT m b
ifte ListT m a
t a -> ListT m b
th ListT m b
el = m (Maybe (b, ListT m b)) -> ListT m b
forall (m :: * -> *) a. m (Maybe (a, ListT m a)) -> ListT m a
ListT (m (Maybe (b, ListT m b)) -> ListT m b)
-> m (Maybe (b, ListT m b)) -> ListT m b
forall a b. (a -> b) -> a -> b
$ ListT m a -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons ListT m a
t m (Maybe (a, ListT m a))
-> (Maybe (a, ListT m a) -> m (Maybe (b, ListT m b)))
-> m (Maybe (b, ListT m b))
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \case
    Maybe (a, ListT m a)
Nothing -> ListT m b -> m (Maybe (b, ListT m b))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons ListT m b
el
    Just (a
a,ListT m a
m) -> ListT m b -> m (Maybe (b, ListT m b))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons (ListT m b -> m (Maybe (b, ListT m b)))
-> ListT m b -> m (Maybe (b, ListT m b))
forall a b. (a -> b) -> a -> b
$ a -> ListT m b
th a
a ListT m b -> ListT m b -> ListT m b
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> (ListT m a
m ListT m a -> (a -> ListT m b) -> ListT m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= a -> ListT m b
th)

  once :: ListT m a -> ListT m a
once (ListT m (Maybe (a, ListT m a))
m) = m (Maybe (a, ListT m a)) -> ListT m a
forall (m :: * -> *) a. m (Maybe (a, ListT m a)) -> ListT m a
ListT (m (Maybe (a, ListT m a)) -> ListT m a)
-> m (Maybe (a, ListT m a)) -> ListT m a
forall a b. (a -> b) -> a -> b
$ m (Maybe (a, ListT m a))
m m (Maybe (a, ListT m a))
-> (Maybe (a, ListT m a) -> m (Maybe (a, ListT m a)))
-> m (Maybe (a, ListT m a))
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \case
    Maybe (a, ListT m a)
Nothing -> ListT m a -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons ListT m a
forall (f :: * -> *) a. Alternative f => f a
empty
    Just (a
a, ListT m a
_) -> ListT m a -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons (a -> ListT m a
forall (m :: * -> *) a. Monad m => a -> m a
return a
a)

  lnot :: ListT m a -> ListT m ()
lnot (ListT m (Maybe (a, ListT m a))
m) = m (Maybe ((), ListT m ())) -> ListT m ()
forall (m :: * -> *) a. m (Maybe (a, ListT m a)) -> ListT m a
ListT (m (Maybe ((), ListT m ())) -> ListT m ())
-> m (Maybe ((), ListT m ())) -> ListT m ()
forall a b. (a -> b) -> a -> b
$ m (Maybe (a, ListT m a))
m m (Maybe (a, ListT m a))
-> (Maybe (a, ListT m a) -> m (Maybe ((), ListT m ())))
-> m (Maybe ((), ListT m ()))
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \case
    Maybe (a, ListT m a)
Nothing -> ListT m () -> m (Maybe ((), ListT m ()))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons (() -> ListT m ()
forall (m :: * -> *) a. Monad m => a -> m a
return ())
    Just (a, ListT m a)
_ -> ListT m () -> m (Maybe ((), ListT m ()))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons ListT m ()
forall (f :: * -> *) a. Alternative f => f a
empty

instance MonadZip m => MonadZip (ListT m) where
  mzipWith :: (a -> b -> c) -> ListT m a -> ListT m b -> ListT m c
mzipWith a -> b -> c
f = ListT m a -> ListT m b -> ListT m c
go
    where
      go :: ListT m a -> ListT m b -> ListT m c
go (ListT m (Maybe (a, ListT m a))
m1) (ListT m (Maybe (b, ListT m b))
m2) =
        m (Maybe (c, ListT m c)) -> ListT m c
forall (m :: * -> *) a. m (Maybe (a, ListT m a)) -> ListT m a
ListT (m (Maybe (c, ListT m c)) -> ListT m c)
-> m (Maybe (c, ListT m c)) -> ListT m c
forall a b. (a -> b) -> a -> b
$ (Maybe (a, ListT m a)
 -> Maybe (b, ListT m b) -> Maybe (c, ListT m c))
-> m (Maybe (a, ListT m a))
-> m (Maybe (b, ListT m b))
-> m (Maybe (c, ListT m c))
forall (m :: * -> *) a b c.
MonadZip m =>
(a -> b -> c) -> m a -> m b -> m c
mzipWith (((a, ListT m a) -> (b, ListT m b) -> (c, ListT m c))
-> Maybe (a, ListT m a)
-> Maybe (b, ListT m b)
-> Maybe (c, ListT m c)
forall (m :: * -> *) a b c.
MonadZip m =>
(a -> b -> c) -> m a -> m b -> m c
mzipWith (((a, ListT m a) -> (b, ListT m b) -> (c, ListT m c))
 -> Maybe (a, ListT m a)
 -> Maybe (b, ListT m b)
 -> Maybe (c, ListT m c))
-> ((a, ListT m a) -> (b, ListT m b) -> (c, ListT m c))
-> Maybe (a, ListT m a)
-> Maybe (b, ListT m b)
-> Maybe (c, ListT m c)
forall a b. (a -> b) -> a -> b
$
                     \(a
a, ListT m a
as) (b
b, ListT m b
bs) -> (a -> b -> c
f a
a b
b, ListT m a -> ListT m b -> ListT m c
go ListT m a
as ListT m b
bs)) m (Maybe (a, ListT m a))
m1 m (Maybe (b, ListT m b))
m2

  munzip :: ListT m (a, b) -> (ListT m a, ListT m b)
munzip (ListT m (Maybe ((a, b), ListT m (a, b)))
m)
    | (m (Maybe (a, ListT m a))
l, m (Maybe (b, ListT m b))
r) <- m (Maybe (a, ListT m a), Maybe (b, ListT m b))
-> (m (Maybe (a, ListT m a)), m (Maybe (b, ListT m b)))
forall (m :: * -> *) a b. MonadZip m => m (a, b) -> (m a, m b)
munzip ((Maybe ((a, b), ListT m (a, b))
 -> (Maybe (a, ListT m a), Maybe (b, ListT m b)))
-> m (Maybe ((a, b), ListT m (a, b)))
-> m (Maybe (a, ListT m a), Maybe (b, ListT m b))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Maybe ((a, b), ListT m (a, b))
-> (Maybe (a, ListT m a), Maybe (b, ListT m b))
forall (m :: * -> *) a a a b.
MonadZip m =>
Maybe ((a, a), m (a, b)) -> (Maybe (a, m a), Maybe (a, m b))
go m (Maybe ((a, b), ListT m (a, b)))
m)
    = (m (Maybe (a, ListT m a)) -> ListT m a
forall (m :: * -> *) a. m (Maybe (a, ListT m a)) -> ListT m a
ListT m (Maybe (a, ListT m a))
l, m (Maybe (b, ListT m b)) -> ListT m b
forall (m :: * -> *) a. m (Maybe (a, ListT m a)) -> ListT m a
ListT m (Maybe (b, ListT m b))
r)
    where
      go :: Maybe ((a, a), m (a, b)) -> (Maybe (a, m a), Maybe (a, m b))
go Maybe ((a, a), m (a, b))
Nothing = (Maybe (a, m a)
forall a. Maybe a
Nothing, Maybe (a, m b)
forall a. Maybe a
Nothing)
      go (Just ((a
a, a
b), m (a, b)
listab))
        = ((a, m a) -> Maybe (a, m a)
forall a. a -> Maybe a
Just (a
a, m a
la), (a, m b) -> Maybe (a, m b)
forall a. a -> Maybe a
Just (a
b, m b
lb))
        where
          -- If the underlying munzip is careful not to leak memory, then we
          -- don't want to defeat it.  We need to be sure that la and lb are
          -- realized as selector thunks.
          {-# NOINLINE remains #-}
          {-# NOINLINE la #-}
          {-# NOINLINE lb #-}
          remains :: (m a, m b)
remains = m (a, b) -> (m a, m b)
forall (m :: * -> *) a b. MonadZip m => m (a, b) -> (m a, m b)
munzip m (a, b)
listab
          (m a
la, m b
lb) = (m a, m b)
remains

-- * Execution in the inner monad
-------------------------

-- |
-- Execute in the inner monad,
-- getting the head and the tail.
-- Returns nothing if it's empty.
uncons :: ListT m a -> m (Maybe (a, ListT m a))
uncons :: ListT m a -> m (Maybe (a, ListT m a))
uncons (ListT m (Maybe (a, ListT m a))
m) =
  m (Maybe (a, ListT m a))
m

-- |
-- Execute, getting the head. Returns nothing if it's empty.
{-# INLINABLE head #-}
head :: Monad m => ListT m a -> m (Maybe a)
head :: ListT m a -> m (Maybe a)
head =
  (Maybe (a, ListT m a) -> Maybe a)
-> m (Maybe (a, ListT m a)) -> m (Maybe a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (((a, ListT m a) -> a) -> Maybe (a, ListT m a) -> Maybe a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (a, ListT m a) -> a
forall a b. (a, b) -> a
fst) (m (Maybe (a, ListT m a)) -> m (Maybe a))
-> (ListT m a -> m (Maybe (a, ListT m a)))
-> ListT m a
-> m (Maybe a)
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. ListT m a -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons

-- |
-- Execute, getting the tail. Returns nothing if it's empty.
{-# INLINABLE tail #-}
tail :: Monad m => ListT m a -> m (Maybe (ListT m a))
tail :: ListT m a -> m (Maybe (ListT m a))
tail =
  (Maybe (a, ListT m a) -> Maybe (ListT m a))
-> m (Maybe (a, ListT m a)) -> m (Maybe (ListT m a))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (((a, ListT m a) -> ListT m a)
-> Maybe (a, ListT m a) -> Maybe (ListT m a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (a, ListT m a) -> ListT m a
forall a b. (a, b) -> b
snd) (m (Maybe (a, ListT m a)) -> m (Maybe (ListT m a)))
-> (ListT m a -> m (Maybe (a, ListT m a)))
-> ListT m a
-> m (Maybe (ListT m a))
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. ListT m a -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons

-- |
-- Execute, checking whether it's empty.
{-# INLINABLE null #-}
null :: Monad m => ListT m a -> m Bool
null :: ListT m a -> m Bool
null =
  (Maybe (a, ListT m a) -> Bool)
-> m (Maybe (a, ListT m a)) -> m Bool
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Bool -> ((a, ListT m a) -> Bool) -> Maybe (a, ListT m a) -> Bool
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Bool
True (Bool -> (a, ListT m a) -> Bool
forall a b. a -> b -> a
const Bool
False)) (m (Maybe (a, ListT m a)) -> m Bool)
-> (ListT m a -> m (Maybe (a, ListT m a))) -> ListT m a -> m Bool
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. ListT m a -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons

-- |
-- Execute in the inner monad,
-- using its '(<|>)' function on each entry.
{-# INLINABLE alternate #-}
alternate :: (Alternative m, Monad m) => ListT m a -> m a
alternate :: ListT m a -> m a
alternate (ListT m (Maybe (a, ListT m a))
m) = m (Maybe (a, ListT m a))
m m (Maybe (a, ListT m a)) -> (Maybe (a, ListT m a) -> m a) -> m a
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \case
  Maybe (a, ListT m a)
Nothing -> m a
forall (f :: * -> *) a. Alternative f => f a
empty
  Just (a
a, ListT m a
as) -> a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure a
a m a -> m a -> m a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> ListT m a -> m a
forall (m :: * -> *) a.
(Alternative m, Monad m) =>
ListT m a -> m a
alternate ListT m a
as

-- |
-- Use a monad morphism to convert a 'ListT' to a similar
-- monad, such as '[]'.
-- 
-- A more efficient alternative to @'alternate' . 'hoist' f@.
{-# INLINABLE alternateHoisting #-}
alternateHoisting :: (Monad n, Alternative n) => (forall a. m a -> n a) -> ListT m a -> n a
alternateHoisting :: (forall a. m a -> n a) -> ListT m a -> n a
alternateHoisting forall a. m a -> n a
f = ListT m a -> n a
go
  where
    go :: ListT m a -> n a
go (ListT m (Maybe (a, ListT m a))
m) = m (Maybe (a, ListT m a)) -> n (Maybe (a, ListT m a))
forall a. m a -> n a
f m (Maybe (a, ListT m a))
m n (Maybe (a, ListT m a)) -> (Maybe (a, ListT m a) -> n a) -> n a
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \case
      Maybe (a, ListT m a)
Nothing -> n a
forall (f :: * -> *) a. Alternative f => f a
empty
      Just (a
a, ListT m a
as) -> a -> n a
forall (f :: * -> *) a. Applicative f => a -> f a
pure a
a n a -> n a -> n a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> ListT m a -> n a
go ListT m a
as

-- |
-- Execute, applying a left fold.
{-# INLINABLE fold #-}
fold :: Monad m => (r -> a -> m r) -> r -> ListT m a -> m r
fold :: (r -> a -> m r) -> r -> ListT m a -> m r
fold r -> a -> m r
s r
r = 
  ListT m a -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons (ListT m a -> m (Maybe (a, ListT m a)))
-> (Maybe (a, ListT m a) -> m r) -> ListT m a -> m r
forall (m :: * -> *) a b c.
Monad m =>
(a -> m b) -> (b -> m c) -> a -> m c
>=> m r -> ((a, ListT m a) -> m r) -> Maybe (a, ListT m a) -> m r
forall b a. b -> (a -> b) -> Maybe a -> b
maybe (r -> m r
forall (m :: * -> *) a. Monad m => a -> m a
return r
r) (\(a
h, ListT m a
t) -> r -> a -> m r
s r
r a
h m r -> (r -> m r) -> m r
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \r
r' -> (r -> a -> m r) -> r -> ListT m a -> m r
forall (m :: * -> *) r a.
Monad m =>
(r -> a -> m r) -> r -> ListT m a -> m r
fold r -> a -> m r
s r
r' ListT m a
t)

-- |
-- A version of 'fold', which allows early termination.
{-# INLINABLE foldMaybe #-}
foldMaybe :: Monad m => (r -> a -> m (Maybe r)) -> r -> ListT m a -> m r
foldMaybe :: (r -> a -> m (Maybe r)) -> r -> ListT m a -> m r
foldMaybe r -> a -> m (Maybe r)
s r
r ListT m a
l =
  (Maybe r -> r) -> m (Maybe r) -> m r
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (r -> (r -> r) -> Maybe r -> r
forall b a. b -> (a -> b) -> Maybe a -> b
maybe r
r r -> r
forall k (cat :: k -> k -> *) (a :: k). Category cat => cat a a
id) (m (Maybe r) -> m r) -> m (Maybe r) -> m r
forall a b. (a -> b) -> a -> b
$ MaybeT m r -> m (Maybe r)
forall (m :: * -> *) a. MaybeT m a -> m (Maybe a)
runMaybeT (MaybeT m r -> m (Maybe r)) -> MaybeT m r -> m (Maybe r)
forall a b. (a -> b) -> a -> b
$ do
    (a
h, ListT m a
t) <- m (Maybe (a, ListT m a)) -> MaybeT m (a, ListT m a)
forall (m :: * -> *) a. m (Maybe a) -> MaybeT m a
MaybeT (m (Maybe (a, ListT m a)) -> MaybeT m (a, ListT m a))
-> m (Maybe (a, ListT m a)) -> MaybeT m (a, ListT m a)
forall a b. (a -> b) -> a -> b
$ ListT m a -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons ListT m a
l
    r
r' <- m (Maybe r) -> MaybeT m r
forall (m :: * -> *) a. m (Maybe a) -> MaybeT m a
MaybeT (m (Maybe r) -> MaybeT m r) -> m (Maybe r) -> MaybeT m r
forall a b. (a -> b) -> a -> b
$ r -> a -> m (Maybe r)
s r
r a
h
    m r -> MaybeT m r
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (m r -> MaybeT m r) -> m r -> MaybeT m r
forall a b. (a -> b) -> a -> b
$ (r -> a -> m (Maybe r)) -> r -> ListT m a -> m r
forall (m :: * -> *) r a.
Monad m =>
(r -> a -> m (Maybe r)) -> r -> ListT m a -> m r
foldMaybe r -> a -> m (Maybe r)
s r
r' ListT m a
t

-- |
-- Apply a left fold abstraction from the \"foldl\" package.
applyFoldM :: Monad m => FoldM m i o -> ListT m i -> m o
applyFoldM :: FoldM m i o -> ListT m i -> m o
applyFoldM (FoldM x -> i -> m x
step m x
init x -> m o
extract) ListT m i
lt = do
  x
a <- m x
init
  x
b <- (x -> i -> m x) -> x -> ListT m i -> m x
forall (m :: * -> *) r a.
Monad m =>
(r -> a -> m r) -> r -> ListT m a -> m r
fold x -> i -> m x
step x
a ListT m i
lt
  x -> m o
extract x
b

-- |
-- Execute, folding to a list.
{-# INLINABLE toList #-}
toList :: Monad m => ListT m a -> m [a]
toList :: ListT m a -> m [a]
toList =
  (([a] -> [a]) -> [a]) -> m ([a] -> [a]) -> m [a]
forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
liftM (([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ []) (m ([a] -> [a]) -> m [a])
-> (ListT m a -> m ([a] -> [a])) -> ListT m a -> m [a]
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (([a] -> [a]) -> a -> m ([a] -> [a]))
-> ([a] -> [a]) -> ListT m a -> m ([a] -> [a])
forall (m :: * -> *) r a.
Monad m =>
(r -> a -> m r) -> r -> ListT m a -> m r
fold (\[a] -> [a]
f a
e -> ([a] -> [a]) -> m ([a] -> [a])
forall (m :: * -> *) a. Monad m => a -> m a
return (([a] -> [a]) -> m ([a] -> [a])) -> ([a] -> [a]) -> m ([a] -> [a])
forall a b. (a -> b) -> a -> b
$ [a] -> [a]
f ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (a
e a -> [a] -> [a]
forall a. a -> [a] -> [a]
:)) [a] -> [a]
forall k (cat :: k -> k -> *) (a :: k). Category cat => cat a a
id

-- |
-- Execute, folding to a list in the reverse order.
-- Performs more efficiently than 'toList'.
{-# INLINABLE toReverseList #-}
toReverseList :: Monad m => ListT m a -> m [a]
toReverseList :: ListT m a -> m [a]
toReverseList =
  ([a] -> a -> m [a]) -> [a] -> ListT m a -> m [a]
forall (m :: * -> *) r a.
Monad m =>
(r -> a -> m r) -> r -> ListT m a -> m r
ListT.fold (\[a]
l -> [a] -> m [a]
forall (m :: * -> *) a. Monad m => a -> m a
return ([a] -> m [a]) -> (a -> [a]) -> a -> m [a]
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (a -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
l)) []

-- |
-- Execute, traversing the stream with a side effect in the inner monad. 
{-# INLINABLE traverse_ #-}
traverse_ :: Monad m => (a -> m ()) -> ListT m a -> m ()
traverse_ :: (a -> m ()) -> ListT m a -> m ()
traverse_ a -> m ()
f =
  (() -> a -> m ()) -> () -> ListT m a -> m ()
forall (m :: * -> *) r a.
Monad m =>
(r -> a -> m r) -> r -> ListT m a -> m r
fold ((a -> m ()) -> () -> a -> m ()
forall a b. a -> b -> a
const a -> m ()
f) ()

-- |
-- Execute, consuming a list of the specified length and returning the remainder stream.
{-# INLINABLE splitAt #-}
splitAt :: Monad m => Int -> ListT m a -> m ([a], ListT m a)
splitAt :: Int -> ListT m a -> m ([a], ListT m a)
splitAt =
  \case
    Int
n | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0 -> \ListT m a
l ->
      ListT m a -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons ListT m a
l m (Maybe (a, ListT m a))
-> (Maybe (a, ListT m a) -> m ([a], ListT m a))
-> m ([a], ListT m a)
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \case
        Maybe (a, ListT m a)
Nothing -> ([a], ListT m a) -> m ([a], ListT m a)
forall (m :: * -> *) a. Monad m => a -> m a
return ([], ListT m a
forall (m :: * -> *) a. MonadPlus m => m a
mzero)
        Just (a
h, ListT m a
t) -> do
          ([a]
r1, ListT m a
r2) <- Int -> ListT m a -> m ([a], ListT m a)
forall (m :: * -> *) a.
Monad m =>
Int -> ListT m a -> m ([a], ListT m a)
splitAt (Int -> Int
forall a. Enum a => a -> a
pred Int
n) ListT m a
t
          ([a], ListT m a) -> m ([a], ListT m a)
forall (m :: * -> *) a. Monad m => a -> m a
return (a
h a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
r1, ListT m a
r2)
    Int
_ -> \ListT m a
l -> 
      ([a], ListT m a) -> m ([a], ListT m a)
forall (m :: * -> *) a. Monad m => a -> m a
return ([], ListT m a
l)


-- * Construction
-------------------------

-- |
-- Prepend an element.
cons :: Monad m => a -> ListT m a -> ListT m a
cons :: a -> ListT m a -> ListT m a
cons a
h ListT m a
t =
  m (Maybe (a, ListT m a)) -> ListT m a
forall (m :: * -> *) a. m (Maybe (a, ListT m a)) -> ListT m a
ListT (m (Maybe (a, ListT m a)) -> ListT m a)
-> m (Maybe (a, ListT m a)) -> ListT m a
forall a b. (a -> b) -> a -> b
$ Maybe (a, ListT m a) -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. Monad m => a -> m a
return ((a, ListT m a) -> Maybe (a, ListT m a)
forall a. a -> Maybe a
Just (a
h, ListT m a
t))

-- |
-- Construct from any foldable.
{-# INLINABLE fromFoldable #-}
fromFoldable :: (Monad m, Foldable f) => f a -> ListT m a
fromFoldable :: f a -> ListT m a
fromFoldable = 
  (a -> ListT m a -> ListT m a) -> ListT m a -> f a -> ListT m a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> ListT m a -> ListT m a
forall (m :: * -> *) a. Monad m => a -> ListT m a -> ListT m a
cons ListT m a
forall (m :: * -> *) a. MonadPlus m => m a
mzero

-- |
-- Construct from an MVar, interpreting the value of Nothing as the end.
fromMVar :: (MonadIO m) => MVar (Maybe a) -> ListT m a
fromMVar :: MVar (Maybe a) -> ListT m a
fromMVar MVar (Maybe a)
v =
  (ListT m a -> ListT m a) -> ListT m a
forall a. (a -> a) -> a
fix ((ListT m a -> ListT m a) -> ListT m a)
-> (ListT m a -> ListT m a) -> ListT m a
forall a b. (a -> b) -> a -> b
$ \ListT m a
loop -> IO (Maybe a) -> ListT m (Maybe a)
forall (m :: * -> *) a. MonadIO m => IO a -> m a
liftIO (MVar (Maybe a) -> IO (Maybe a)
forall a. MVar a -> IO a
takeMVar MVar (Maybe a)
v) ListT m (Maybe a) -> (Maybe a -> ListT m a) -> ListT m a
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= ListT m a -> (a -> ListT m a) -> Maybe a -> ListT m a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe ListT m a
forall (m :: * -> *) a. MonadPlus m => m a
mzero ((a -> ListT m a -> ListT m a) -> ListT m a -> a -> ListT m a
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> ListT m a -> ListT m a
forall (m :: * -> *) a. Monad m => a -> ListT m a -> ListT m a
cons ListT m a
loop)

-- |
-- Construct by unfolding a pure data structure.
{-# INLINABLE unfold #-}
unfold :: Monad m => (b -> Maybe (a, b)) -> b -> ListT m a
unfold :: (b -> Maybe (a, b)) -> b -> ListT m a
unfold b -> Maybe (a, b)
f b
s =
  ListT m a -> ((a, b) -> ListT m a) -> Maybe (a, b) -> ListT m a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe ListT m a
forall (m :: * -> *) a. MonadPlus m => m a
mzero (\(a
h, b
t) -> a -> ListT m a -> ListT m a
forall (m :: * -> *) a. Monad m => a -> ListT m a -> ListT m a
cons a
h ((b -> Maybe (a, b)) -> b -> ListT m a
forall (m :: * -> *) b a.
Monad m =>
(b -> Maybe (a, b)) -> b -> ListT m a
unfold b -> Maybe (a, b)
f b
t)) (b -> Maybe (a, b)
f b
s)

-- |
-- Construct by unfolding a monadic data structure
--
-- This is the most memory-efficient way to construct ListT where
-- the length depends on the inner monad.
{-# INLINABLE unfoldM #-}
unfoldM :: Monad m => (b -> m (Maybe (a, b))) -> b -> ListT m a
unfoldM :: (b -> m (Maybe (a, b))) -> b -> ListT m a
unfoldM b -> m (Maybe (a, b))
f = b -> ListT m a
go where
  go :: b -> ListT m a
go b
s = m (Maybe (a, ListT m a)) -> ListT m a
forall (m :: * -> *) a. m (Maybe (a, ListT m a)) -> ListT m a
ListT (m (Maybe (a, ListT m a)) -> ListT m a)
-> m (Maybe (a, ListT m a)) -> ListT m a
forall a b. (a -> b) -> a -> b
$ b -> m (Maybe (a, b))
f b
s m (Maybe (a, b))
-> (Maybe (a, b) -> m (Maybe (a, ListT m a)))
-> m (Maybe (a, ListT m a))
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \case
    Maybe (a, b)
Nothing -> Maybe (a, ListT m a) -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe (a, ListT m a)
forall a. Maybe a
Nothing
    Just (a
a,b
r) -> Maybe (a, ListT m a) -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. Monad m => a -> m a
return ((a, ListT m a) -> Maybe (a, ListT m a)
forall a. a -> Maybe a
Just (a
a, b -> ListT m a
go b
r))

-- |
-- Produce an infinite stream.
{-# INLINABLE repeat #-}
repeat :: Monad m => a -> ListT m a
repeat :: a -> ListT m a
repeat = 
  (ListT m a -> ListT m a) -> ListT m a
forall a. (a -> a) -> a
fix ((ListT m a -> ListT m a) -> ListT m a)
-> (a -> ListT m a -> ListT m a) -> a -> ListT m a
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. a -> ListT m a -> ListT m a
forall (m :: * -> *) a. Monad m => a -> ListT m a -> ListT m a
cons


-- * Transformation
-------------------------

-- |
-- A transformation,
-- which traverses the stream with an action in the inner monad.
{-# INLINABLE traverse #-}
traverse :: Monad m => (a -> m b) -> ListT m a -> ListT m b
traverse :: (a -> m b) -> ListT m a -> ListT m b
traverse a -> m b
f ListT m a
s =
  m (Maybe (a, ListT m a)) -> ListT m (Maybe (a, ListT m a))
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (ListT m a -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons ListT m a
s) ListT m (Maybe (a, ListT m a))
-> (Maybe (a, ListT m a) -> ListT m (Maybe b)) -> ListT m (Maybe b)
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= 
  ((a, ListT m a) -> ListT m b)
-> Maybe (a, ListT m a) -> ListT m (Maybe b)
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM (\(a
h, ListT m a
t) -> m b -> ListT m b
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (a -> m b
f a
h) ListT m b -> (b -> ListT m b) -> ListT m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \b
h' -> b -> ListT m b -> ListT m b
forall (m :: * -> *) a. Monad m => a -> ListT m a -> ListT m a
cons b
h' ((a -> m b) -> ListT m a -> ListT m b
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> ListT m a -> ListT m b
traverse a -> m b
f ListT m a
t)) ListT m (Maybe b) -> (Maybe b -> ListT m b) -> ListT m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>=
  ListT m b -> (b -> ListT m b) -> Maybe b -> ListT m b
forall b a. b -> (a -> b) -> Maybe a -> b
maybe ListT m b
forall (m :: * -> *) a. MonadPlus m => m a
mzero b -> ListT m b
forall (m :: * -> *) a. Monad m => a -> m a
return

-- |
-- A transformation,
-- reproducing the behaviour of @Data.List.'Data.List.take'@.
{-# INLINABLE take #-}
take :: Monad m => Int -> ListT m a -> ListT m a
take :: Int -> ListT m a -> ListT m a
take =
  \case
    Int
n | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0 -> \ListT m a
t ->
      m (Maybe (a, ListT m a)) -> ListT m (Maybe (a, ListT m a))
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (ListT m a -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons ListT m a
t) ListT m (Maybe (a, ListT m a))
-> (Maybe (a, ListT m a) -> ListT m a) -> ListT m a
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= 
        \case
          Maybe (a, ListT m a)
Nothing -> ListT m a
t
          Just (a
h, ListT m a
t) -> a -> ListT m a -> ListT m a
forall (m :: * -> *) a. Monad m => a -> ListT m a -> ListT m a
cons a
h (Int -> ListT m a -> ListT m a
forall (m :: * -> *) a. Monad m => Int -> ListT m a -> ListT m a
take (Int -> Int
forall a. Enum a => a -> a
pred Int
n) ListT m a
t)
    Int
_ ->
      ListT m a -> ListT m a -> ListT m a
forall a b. a -> b -> a
const (ListT m a -> ListT m a -> ListT m a)
-> ListT m a -> ListT m a -> ListT m a
forall a b. (a -> b) -> a -> b
$ ListT m a
forall (m :: * -> *) a. MonadPlus m => m a
mzero

-- |
-- A transformation,
-- reproducing the behaviour of @Data.List.'Data.List.drop'@.
{-# INLINABLE drop #-}
drop :: Monad m => Int -> ListT m a -> ListT m a
drop :: Int -> ListT m a -> ListT m a
drop =
  \case
    Int
n | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0 ->
      m (Maybe (a, ListT m a)) -> ListT m (Maybe (a, ListT m a))
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (m (Maybe (a, ListT m a)) -> ListT m (Maybe (a, ListT m a)))
-> (ListT m a -> m (Maybe (a, ListT m a)))
-> ListT m a
-> ListT m (Maybe (a, ListT m a))
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. ListT m a -> m (Maybe (a, ListT m a))
forall (m :: * -> *) a. ListT m a -> m (Maybe (a, ListT m a))
uncons (ListT m a -> ListT m (Maybe (a, ListT m a)))
-> (Maybe (a, ListT m a) -> ListT m a) -> ListT m a -> ListT m a
forall (m :: * -> *) a b c.
Monad m =>
(a -> m b) -> (b -> m c) -> a -> m c
>=> ListT m a
-> ((a, ListT m a) -> ListT m a)
-> Maybe (a, ListT m a)
-> ListT m a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe ListT m a
forall (m :: * -> *) a. MonadPlus m => m a
mzero (Int -> ListT m a -> ListT m a
forall (m :: * -> *) a. Monad m => Int -> ListT m a -> ListT m a
drop (Int -> Int
forall a. Enum a => a -> a
pred Int
n) (ListT m a -> ListT m a)
-> ((a, ListT m a) -> ListT m a) -> (a, ListT m a) -> ListT m a
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (a, ListT m a) -> ListT m a
forall a b. (a, b) -> b
snd)
    Int
_ ->
      ListT m a -> ListT m a
forall k (cat :: k -> k -> *) (a :: k). Category cat => cat a a
id

-- |
-- A transformation,
-- which slices a list into chunks of the specified length.
{-# INLINABLE slice #-}
slice :: Monad m => Int -> ListT m a -> ListT m [a]
slice :: Int -> ListT m a -> ListT m [a]
slice Int
n ListT m a
l = 
  do
    ([a]
h, ListT m a
t) <- m ([a], ListT m a) -> ListT m ([a], ListT m a)
forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
(MonadTrans t, Monad m) =>
m a -> t m a
lift (m ([a], ListT m a) -> ListT m ([a], ListT m a))
-> m ([a], ListT m a) -> ListT m ([a], ListT m a)
forall a b. (a -> b) -> a -> b
$ Int -> ListT m a -> m ([a], ListT m a)
forall (m :: * -> *) a.
Monad m =>
Int -> ListT m a -> m ([a], ListT m a)
splitAt Int
n ListT m a
l
    case [a]
h of
      [] -> ListT m [a]
forall (m :: * -> *) a. MonadPlus m => m a
mzero
      [a]
_ -> [a] -> ListT m [a] -> ListT m [a]
forall (m :: * -> *) a. Monad m => a -> ListT m a -> ListT m a
cons [a]
h (Int -> ListT m a -> ListT m [a]
forall (m :: * -> *) a. Monad m => Int -> ListT m a -> ListT m [a]
slice Int
n ListT m a
t)