    {-# LANGUAGE FlexibleContexts, TypeFamilies #-}

    -- | The 'List' class and actions for lists

    module Data.List.Class (
        -- | The List typeclass
        List (..), ListItem (..),
        fromList,
        -- | List operations for MonadPlus
        filter,
        -- | Standard list operations
        repeat,
        take, takeWhile, genericTake, scanl, scanl1,
        transpose, zip, zipWith,
        concat, concatMap,
        tail,
        enumFrom, enumFromTo,
        catMaybes, mapMaybe,
        -- | Non standard List operations
        foldrL, foldlL, foldl1L, toList, lengthL, lastL,
        merge2On, mergeOn,
        -- | Operations useful for monadic lists
        execute, joinM, mapL, filterL, iterateM, takeWhileM, repeatM,
        splitAtM, splitWhenM,
        -- | Operations for non-monadic lists
        sortOn,
        -- | Convert between List types
        transformListMonad,
        listStateJoin
        ) where

    import Control.Monad (MonadPlus(..), join, liftM)
    import Control.Monad.Trans.State (StateT(..), evalStateT, get)
    import Data.Function (fix)
    import Data.Functor.Identity (Identity(..))
    import Data.List (sortBy)
    import Data.Maybe (fromJust)
    import Data.Ord (comparing)
    import Prelude hiding (
        concat, concatMap, enumFrom, enumFromTo, filter, repeat, scanl, scanl1,
        tail, take, takeWhile, zip, zipWith)

    data ListItem l a =
        Nil |
        Cons { forall (l :: * -> *) a. ListItem l a -> a
    headL :: a, forall (l :: * -> *) a. ListItem l a -> l a
    tailL :: l a }
        deriving (ListItem l a -> ListItem l a -> Bool
    (ListItem l a -> ListItem l a -> Bool)
    -> (ListItem l a -> ListItem l a -> Bool) -> Eq (ListItem l a)
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    forall (l :: * -> *) a.
    (Eq a, Eq (l a)) =>
    ListItem l a -> ListItem l a -> Bool
    $c== :: forall (l :: * -> *) a.
    (Eq a, Eq (l a)) =>
    ListItem l a -> ListItem l a -> Bool
    == :: ListItem l a -> ListItem l a -> Bool
    $c/= :: forall (l :: * -> *) a.
    (Eq a, Eq (l a)) =>
    ListItem l a -> ListItem l a -> Bool
    /= :: ListItem l a -> ListItem l a -> Bool
    Eq, Eq (ListItem l a)
    Eq (ListItem l a) =>
    (ListItem l a -> ListItem l a -> Ordering)
    -> (ListItem l a -> ListItem l a -> Bool)
    -> (ListItem l a -> ListItem l a -> Bool)
    -> (ListItem l a -> ListItem l a -> Bool)
    -> (ListItem l a -> ListItem l a -> Bool)
    -> (ListItem l a -> ListItem l a -> ListItem l a)
    -> (ListItem l a -> ListItem l a -> ListItem l a)
    -> Ord (ListItem l a)
    ListItem l a -> ListItem l a -> Bool
    ListItem l a -> ListItem l a -> Ordering
    ListItem l a -> ListItem l a -> ListItem l a
    forall a.
    Eq a =>
    (a -> a -> Ordering)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> a)
    -> (a -> a -> a)
    -> Ord a
    forall (l :: * -> *) a. (Ord a, Ord (l a)) => Eq (ListItem l a)
    forall (l :: * -> *) a.
    (Ord a, Ord (l a)) =>
    ListItem l a -> ListItem l a -> Bool
    forall (l :: * -> *) a.
    (Ord a, Ord (l a)) =>
    ListItem l a -> ListItem l a -> Ordering
    forall (l :: * -> *) a.
    (Ord a, Ord (l a)) =>
    ListItem l a -> ListItem l a -> ListItem l a
    $ccompare :: forall (l :: * -> *) a.
    (Ord a, Ord (l a)) =>
    ListItem l a -> ListItem l a -> Ordering
    compare :: ListItem l a -> ListItem l a -> Ordering
    $c< :: forall (l :: * -> *) a.
    (Ord a, Ord (l a)) =>
    ListItem l a -> ListItem l a -> Bool
    < :: ListItem l a -> ListItem l a -> Bool
    $c<= :: forall (l :: * -> *) a.
    (Ord a, Ord (l a)) =>
    ListItem l a -> ListItem l a -> Bool
    <= :: ListItem l a -> ListItem l a -> Bool
    $c> :: forall (l :: * -> *) a.
    (Ord a, Ord (l a)) =>
    ListItem l a -> ListItem l a -> Bool
    > :: ListItem l a -> ListItem l a -> Bool
    $c>= :: forall (l :: * -> *) a.
    (Ord a, Ord (l a)) =>
    ListItem l a -> ListItem l a -> Bool
    >= :: ListItem l a -> ListItem l a -> Bool
    $cmax :: forall (l :: * -> *) a.
    (Ord a, Ord (l a)) =>
    ListItem l a -> ListItem l a -> ListItem l a
    max :: ListItem l a -> ListItem l a -> ListItem l a
    $cmin :: forall (l :: * -> *) a.
    (Ord a, Ord (l a)) =>
    ListItem l a -> ListItem l a -> ListItem l a
    min :: ListItem l a -> ListItem l a -> ListItem l a
    Ord, ReadPrec [ListItem l a]
    ReadPrec (ListItem l a)
    Int -> ReadS (ListItem l a)
    ReadS [ListItem l a]
    (Int -> ReadS (ListItem l a))
    -> ReadS [ListItem l a]
    -> ReadPrec (ListItem l a)
    -> ReadPrec [ListItem l a]
    -> Read (ListItem l a)
    forall a.
    (Int -> ReadS a)
    -> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
    forall (l :: * -> *) a.
    (Read a, Read (l a)) =>
    ReadPrec [ListItem l a]
    forall (l :: * -> *) a.
    (Read a, Read (l a)) =>
    ReadPrec (ListItem l a)
    forall (l :: * -> *) a.
    (Read a, Read (l a)) =>
    Int -> ReadS (ListItem l a)
    forall (l :: * -> *) a.
    (Read a, Read (l a)) =>
    ReadS [ListItem l a]
    $creadsPrec :: forall (l :: * -> *) a.
    (Read a, Read (l a)) =>
    Int -> ReadS (ListItem l a)
    readsPrec :: Int -> ReadS (ListItem l a)
    $creadList :: forall (l :: * -> *) a.
    (Read a, Read (l a)) =>
    ReadS [ListItem l a]
    readList :: ReadS [ListItem l a]
    $creadPrec :: forall (l :: * -> *) a.
    (Read a, Read (l a)) =>
    ReadPrec (ListItem l a)
    readPrec :: ReadPrec (ListItem l a)
    $creadListPrec :: forall (l :: * -> *) a.
    (Read a, Read (l a)) =>
    ReadPrec [ListItem l a]
    readListPrec :: ReadPrec [ListItem l a]
    Read, Int -> ListItem l a -> ShowS
    [ListItem l a] -> ShowS
    ListItem l a -> String
    (Int -> ListItem l a -> ShowS)
    -> (ListItem l a -> String)
    -> ([ListItem l a] -> ShowS)
    -> Show (ListItem l a)
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    forall (l :: * -> *) a.
    (Show a, Show (l a)) =>
    Int -> ListItem l a -> ShowS
    forall (l :: * -> *) a.
    (Show a, Show (l a)) =>
    [ListItem l a] -> ShowS
    forall (l :: * -> *) a.
    (Show a, Show (l a)) =>
    ListItem l a -> String
    $cshowsPrec :: forall (l :: * -> *) a.
    (Show a, Show (l a)) =>
    Int -> ListItem l a -> ShowS
    showsPrec :: Int -> ListItem l a -> ShowS
    $cshow :: forall (l :: * -> *) a.
    (Show a, Show (l a)) =>
    ListItem l a -> String
    show :: ListItem l a -> String
    $cshowList :: forall (l :: * -> *) a.
    (Show a, Show (l a)) =>
    [ListItem l a] -> ShowS
    showList :: [ListItem l a] -> ShowS
    Show)

    infixr 5 `cons`

    -- | A class for list types.
    -- Every list has an underlying monad.
    class (MonadPlus l, Monad (ItemM l)) => List l where
        type ItemM l :: * -> *
        runList :: l a -> ItemM l (ListItem l a)
        -- | Transform an action returning a list to the returned list
        --
        -- > > joinL $ Identity "hello"
        -- > "hello"
        joinL :: ItemM l (l a) -> l a
        -- | cons. Can be derived from MonadPlus but is part of class for performance.
        cons :: a -> l a -> l a
        cons = l a -> l a -> l a
    forall a. l a -> l a -> l a
    forall (m :: * -> *) a. MonadPlus m => m a -> m a -> m a
    mplus (l a -> l a -> l a) -> (a -> l a) -> a -> l a -> l a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> l a
    forall a. a -> l a
    forall (m :: * -> *) a. Monad m => a -> m a
    return

    instance List [] where
        type ItemM [] = Identity
        runList :: forall a. [a] -> ItemM [] (ListItem [] a)
    runList [] = ListItem [] a -> Identity (ListItem [] a)
    forall a. a -> Identity a
    Identity ListItem [] a
    forall (l :: * -> *) a. ListItem l a
    Nil
        runList (a
    x:[a]
    xs) = ListItem [] a -> Identity (ListItem [] a)
    forall a. a -> Identity a
    Identity (ListItem [] a -> Identity (ListItem [] a))
    -> ListItem [] a -> Identity (ListItem [] a)
    forall a b. (a -> b) -> a -> b
    $ a -> [a] -> ListItem [] a
    forall (l :: * -> *) a. a -> l a -> ListItem l a
    Cons a
    x [a]
    xs
        joinL :: forall a. ItemM [] [a] -> [a]
    joinL = Identity [a] -> [a]
    ItemM [] [a] -> [a]
    forall a. Identity a -> a
    runIdentity
        cons :: forall a. a -> [a] -> [a]
    cons = (:)

    instance Functor m => Functor (ListItem m) where
        fmap :: forall a b. (a -> b) -> ListItem m a -> ListItem m b
    fmap a -> b
    _ ListItem m a
    Nil = ListItem m b
    forall (l :: * -> *) a. ListItem l a
    Nil
        fmap a -> b
    func (Cons a
    x m a
    xs) = b -> m b -> ListItem m b
    forall (l :: * -> *) a. a -> l a -> ListItem l a
    Cons (a -> b
    func a
    x) ((a -> b) -> m a -> m b
    forall a b. (a -> b) -> m a -> m b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap a -> b
    func m a
    xs)

    -- A "monadic-catamorphism" for lists.
    -- Unlike folds, this only looks at the list head.
    --
    -- Should this be exposed? Needs a good name first..
    deconstructList :: List l => ItemM l r -> (a -> l a -> ItemM l r) -> l a -> ItemM l r
    deconstructList :: forall (l :: * -> *) r a.
    List l =>
    ItemM l r -> (a -> l a -> ItemM l r) -> l a -> ItemM l r
    deconstructList ItemM l r
    onNil a -> l a -> ItemM l r
    onCons l a
    list = do
        item <- l a -> ItemM l (ListItem l a)
    forall a. l a -> ItemM l (ListItem l a)
    forall (l :: * -> *) a. List l => l a -> ItemM l (ListItem l a)
    runList l a
    list
        case item of
            ListItem l a
    Nil -> ItemM l r
    onNil
            Cons a
    x l a
    xs -> a -> l a -> ItemM l r
    onCons a
    x l a
    xs

    deconstructList' :: List l => l r -> (a -> l a -> l r) -> l a -> l r
    deconstructList' :: forall (l :: * -> *) r a.
    List l =>
    l r -> (a -> l a -> l r) -> l a -> l r
    deconstructList' l r
    onNil a -> l a -> l r
    onCons =
        ItemM l (l r) -> l r
    forall a. ItemM l (l a) -> l a
    forall (l :: * -> *) a. List l => ItemM l (l a) -> l a
    joinL (ItemM l (l r) -> l r) -> (l a -> ItemM l (l r)) -> l a -> l r
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ItemM l (l r)
    -> (a -> l a -> ItemM l (l r)) -> l a -> ItemM l (l r)
    forall (l :: * -> *) r a.
    List l =>
    ItemM l r -> (a -> l a -> ItemM l r) -> l a -> ItemM l r
    deconstructList (l r -> ItemM l (l r)
    forall a. a -> ItemM l a
    forall (m :: * -> *) a. Monad m => a -> m a
    return l r
    onNil) a -> l a -> ItemM l (l r)
    onCons'
        where
            onCons' :: a -> l a -> ItemM l (l r)
    onCons' a
    x = l r -> ItemM l (l r)
    forall a. a -> ItemM l a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (l r -> ItemM l (l r)) -> (l a -> l r) -> l a -> ItemM l (l r)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> l a -> l r
    onCons a
    x

    -- | foldr for 'List's.
    -- the result and 'right side' values are monadic actions.
    foldrL :: List l => (a -> ItemM l b -> ItemM l b) -> ItemM l b -> l a -> ItemM l b
    foldrL :: forall (l :: * -> *) a b.
    List l =>
    (a -> ItemM l b -> ItemM l b) -> ItemM l b -> l a -> ItemM l b
    foldrL a -> ItemM l b -> ItemM l b
    consFunc ItemM l b
    nilFunc =
        ItemM l b -> (a -> l a -> ItemM l b) -> l a -> ItemM l b
    forall (l :: * -> *) r a.
    List l =>
    ItemM l r -> (a -> l a -> ItemM l r) -> l a -> ItemM l r
    deconstructList ItemM l b
    nilFunc a -> l a -> ItemM l b
    onCons
        where
            onCons :: a -> l a -> ItemM l b
    onCons a
    x = a -> ItemM l b -> ItemM l b
    consFunc a
    x (ItemM l b -> ItemM l b) -> (l a -> ItemM l b) -> l a -> ItemM l b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> ItemM l b -> ItemM l b) -> ItemM l b -> l a -> ItemM l b
    forall (l :: * -> *) a b.
    List l =>
    (a -> ItemM l b -> ItemM l b) -> ItemM l b -> l a -> ItemM l b
    foldrL a -> ItemM l b -> ItemM l b
    consFunc ItemM l b
    nilFunc

    -- | Convert a list to a 'MonadPlus'
    --
    -- > > fromList [] :: Maybe Int
    -- > Nothing
    -- > > fromList [5] :: Maybe Int
    -- > Just 5
    fromList :: List l => [a] -> l a
    fromList :: forall (l :: * -> *) a. List l => [a] -> l a
    fromList = (a -> l a -> l a) -> l a -> [a] -> l a
    forall a b. (a -> b -> b) -> b -> [a] -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr a -> l a -> l a
    forall a. a -> l a -> l a
    forall (l :: * -> *) a. List l => a -> l a -> l a
    cons l a
    forall a. l a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero

    -- | filter for any MonadPlus
    --
    -- > > filter (> 5) (Just 3)
    -- > Nothing
    filter :: MonadPlus m => (a -> Bool) -> m a -> m a
    filter :: forall (m :: * -> *) a. MonadPlus m => (a -> Bool) -> m a -> m a
    filter a -> Bool
    cond =
        (m a -> (a -> m a) -> m a
    forall a b. m a -> (a -> m b) -> m b
    forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
    >>= a -> m a
    f)
        where
            f :: a -> m a
    f a
    x
                | a -> Bool
    cond a
    x = a -> m a
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return a
    x
                | Bool
    otherwise = m a
    forall a. m a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero

    -- | An action to do foldl for 'List's
    foldlL :: List l => (a -> b -> a) -> a -> l b -> ItemM l a
    foldlL :: forall (l :: * -> *) a b.
    List l =>
    (a -> b -> a) -> a -> l b -> ItemM l a
    foldlL a -> b -> a
    step a
    startVal =
        ItemM l a -> (b -> l b -> ItemM l a) -> l b -> ItemM l a
    forall (l :: * -> *) r a.
    List l =>
    ItemM l r -> (a -> l a -> ItemM l r) -> l a -> ItemM l r
    deconstructList (a -> ItemM l a
    forall a. a -> ItemM l a
    forall (m :: * -> *) a. Monad m => a -> m a
    return a
    startVal) b -> l b -> ItemM l a
    onCons
        where
            onCons :: b -> l b -> ItemM l a
    onCons b
    x l b
    xs =
                let v :: a
    v = a -> b -> a
    step a
    startVal b
    x
                in a
    v a -> ItemM l a -> ItemM l a
    forall a b. a -> b -> b
    `seq` (a -> b -> a) -> a -> l b -> ItemM l a
    forall (l :: * -> *) a b.
    List l =>
    (a -> b -> a) -> a -> l b -> ItemM l a
    foldlL a -> b -> a
    step a
    v l b
    xs

    foldl1L :: List l => (a -> a -> a) -> l a -> ItemM l a
    -- should use "error" or "fail"?
    foldl1L :: forall (l :: * -> *) a. List l => (a -> a -> a) -> l a -> ItemM l a
    foldl1L = ItemM l a -> (a -> l a -> ItemM l a) -> l a -> ItemM l a
    forall (l :: * -> *) r a.
    List l =>
    ItemM l r -> (a -> l a -> ItemM l r) -> l a -> ItemM l r
    deconstructList (String -> ItemM l a
    forall a. HasCallStack => String -> a
    error String
    "foldl1L: empty list") ((a -> l a -> ItemM l a) -> l a -> ItemM l a)
    -> ((a -> a -> a) -> a -> l a -> ItemM l a)
    -> (a -> a -> a)
    -> l a
    -> ItemM l a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> a -> a) -> a -> l a -> ItemM l a
    forall (l :: * -> *) a b.
    List l =>
    (a -> b -> a) -> a -> l b -> ItemM l a
    foldlL

    scanl :: List l => (a -> b -> a) -> a -> l b -> l a
    scanl :: forall (l :: * -> *) a b.
    List l =>
    (a -> b -> a) -> a -> l b -> l a
    scanl a -> b -> a
    step a
    startVal =
        a -> l a -> l a
    forall a. a -> l a -> l a
    forall (l :: * -> *) a. List l => a -> l a -> l a
    cons a
    startVal (l a -> l a) -> (l b -> l a) -> l b -> l a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . l a -> (b -> l b -> l a) -> l b -> l a
    forall (l :: * -> *) r a.
    List l =>
    l r -> (a -> l a -> l r) -> l a -> l r
    deconstructList' l a
    forall a. l a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero ((a -> b -> a) -> a -> l b -> l a
    forall (l :: * -> *) a b.
    List l =>
    (a -> b -> a) -> a -> l b -> l a
    scanl a -> b -> a
    step (a -> l b -> l a) -> (b -> a) -> b -> l b -> l a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> b -> a
    step a
    startVal)

    scanl1 :: List l => (a -> a -> a) -> l a -> l a
    scanl1 :: forall (l :: * -> *) a. List l => (a -> a -> a) -> l a -> l a
    scanl1 = l a -> (a -> l a -> l a) -> l a -> l a
    forall (l :: * -> *) r a.
    List l =>
    l r -> (a -> l a -> l r) -> l a -> l r
    deconstructList' l a
    forall a. l a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero ((a -> l a -> l a) -> l a -> l a)
    -> ((a -> a -> a) -> a -> l a -> l a)
    -> (a -> a -> a)
    -> l a
    -> l a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> a -> a) -> a -> l a -> l a
    forall (l :: * -> *) a b.
    List l =>
    (a -> b -> a) -> a -> l b -> l a
    scanl

    genericTake :: (Integral i, List l) => i -> l a -> l a
    genericTake :: forall i (l :: * -> *) a. (Integral i, List l) => i -> l a -> l a
    genericTake i
    count
        | i
    count i -> i -> Bool
    forall a. Ord a => a -> a -> Bool
    <= i
    0 = l a -> l a -> l a
    forall a b. a -> b -> a
    const l a
    forall a. l a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero
        | Bool
    otherwise = l a -> (a -> l a -> l a) -> l a -> l a
    forall (l :: * -> *) r a.
    List l =>
    l r -> (a -> l a -> l r) -> l a -> l r
    deconstructList' l a
    forall a. l a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero a -> l a -> l a
    onCons
        where
            onCons :: a -> l a -> l a
    onCons a
    x = a -> l a -> l a
    forall a. a -> l a -> l a
    forall (l :: * -> *) a. List l => a -> l a -> l a
    cons a
    x (l a -> l a) -> (l a -> l a) -> l a -> l a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . i -> l a -> l a
    forall i (l :: * -> *) a. (Integral i, List l) => i -> l a -> l a
    genericTake (i
    count i -> i -> i
    forall a. Num a => a -> a -> a
    - i
    1)

    take :: List l => Int -> l a -> l a
    take :: forall (l :: * -> *) a. List l => Int -> l a -> l a
    take = Int -> l a -> l a
    forall i (l :: * -> *) a. (Integral i, List l) => i -> l a -> l a
    genericTake

    -- | Execute the monadic actions in a 'List'
    execute :: List l => l a -> ItemM l ()
    execute :: forall (l :: * -> *) a. List l => l a -> ItemM l ()
    execute = (() -> a -> ()) -> () -> l a -> ItemM l ()
    forall (l :: * -> *) a b.
    List l =>
    (a -> b -> a) -> a -> l b -> ItemM l a
    foldlL () -> a -> ()
    forall a b. a -> b -> a
    const ()

    -- | Transform a list of actions to a list of their results
    --
    -- > > joinM [Identity 4, Identity 7]
    -- > [4,7]
    joinM :: List l => l (ItemM l a) -> l a
    joinM :: forall (l :: * -> *) a. List l => l (ItemM l a) -> l a
    joinM =
        ItemM l (l a) -> l a
    forall a. ItemM l (l a) -> l a
    forall (l :: * -> *) a. List l => ItemM l (l a) -> l a
    joinL (ItemM l (l a) -> l a)
    -> (l (ItemM l a) -> ItemM l (l a)) -> l (ItemM l a) -> l a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (ItemM l a -> ItemM l (l a) -> ItemM l (l a))
    -> ItemM l (l a) -> l (ItemM l a) -> ItemM l (l a)
    forall (l :: * -> *) a b.
    List l =>
    (a -> ItemM l b -> ItemM l b) -> ItemM l b -> l a -> ItemM l b
    foldrL ItemM l a -> ItemM l (l a) -> ItemM l (l a)
    forall {l :: * -> *} {m :: * -> *} {a1}.
    (List l, Monad m) =>
    m a1 -> ItemM l (l a1) -> m (l a1)
    consFunc (l a -> ItemM l (l a)
    forall a. a -> ItemM l a
    forall (m :: * -> *) a. Monad m => a -> m a
    return l a
    forall a. l a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero)
        where
            consFunc :: m a1 -> ItemM l (l a1) -> m (l a1)
    consFunc m a1
    action ItemM l (l a1)
    rest =
                (a1 -> l a1) -> m a1 -> m (l a1)
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM (a1 -> l a1 -> l a1
    forall a. a -> l a -> l a
    forall (l :: * -> *) a. List l => a -> l a -> l a
    `cons` ItemM l (l a1) -> l a1
    forall a. ItemM l (l a) -> l a
    forall (l :: * -> *) a. List l => ItemM l (l a) -> l a
    joinL ItemM l (l a1)
    rest) m a1
    action

    mapL :: List l => (a -> ItemM l b) -> l a -> l b
    mapL :: forall (l :: * -> *) a b. List l => (a -> ItemM l b) -> l a -> l b
    mapL a -> ItemM l b
    func = l (ItemM l b) -> l b
    forall (l :: * -> *) a. List l => l (ItemM l a) -> l a
    joinM (l (ItemM l b) -> l b) -> (l a -> l (ItemM l b)) -> l a -> l b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> ItemM l b) -> l a -> l (ItemM l b)
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM a -> ItemM l b
    func

    takeWhile :: List l => (a -> Bool) -> l a -> l a
    takeWhile :: forall (l :: * -> *) a. List l => (a -> Bool) -> l a -> l a
    takeWhile = (a -> ItemM l Bool) -> l a -> l a
    forall (l :: * -> *) a. List l => (a -> ItemM l Bool) -> l a -> l a
    takeWhileM ((a -> ItemM l Bool) -> l a -> l a)
    -> ((a -> Bool) -> a -> ItemM l Bool) -> (a -> Bool) -> l a -> l a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Bool -> ItemM l Bool) -> (a -> Bool) -> a -> ItemM l Bool
    forall a b. (a -> b) -> (a -> a) -> a -> b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap Bool -> ItemM l Bool
    forall a. a -> ItemM l a
    forall (m :: * -> *) a. Monad m => a -> m a
    return

    repeatM :: List l => ItemM l a -> l a
    repeatM :: forall (l :: * -> *) a. List l => ItemM l a -> l a
    repeatM = l (ItemM l a) -> l a
    forall (l :: * -> *) a. List l => l (ItemM l a) -> l a
    joinM (l (ItemM l a) -> l a)
    -> (ItemM l a -> l (ItemM l a)) -> ItemM l a -> l a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ItemM l a -> l (ItemM l a)
    forall (l :: * -> *) a. List l => a -> l a
    repeat

    filterL :: List l => (a -> ItemM l Bool) -> l a -> l a
    filterL :: forall (l :: * -> *) a. List l => (a -> ItemM l Bool) -> l a -> l a
    filterL a -> ItemM l Bool
    cond =
        ItemM l (l a) -> l a
    forall a. ItemM l (l a) -> l a
    forall (l :: * -> *) a. List l => ItemM l (l a) -> l a
    joinL (ItemM l (l a) -> l a) -> (l a -> ItemM l (l a)) -> l a -> l a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> ItemM l (l a) -> ItemM l (l a))
    -> ItemM l (l a) -> l a -> ItemM l (l a)
    forall (l :: * -> *) a b.
    List l =>
    (a -> ItemM l b -> ItemM l b) -> ItemM l b -> l a -> ItemM l b
    foldrL a -> ItemM l (l a) -> ItemM l (l a)
    step (l a -> ItemM l (l a)
    forall a. a -> ItemM l a
    forall (m :: * -> *) a. Monad m => a -> m a
    return l a
    forall a. l a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero)
        where
            step :: a -> ItemM l (l a) -> ItemM l (l a)
    step a
    x ItemM l (l a)
    rest = do
                b <- a -> ItemM l Bool
    cond a
    x
                if b
                    then return . cons x . joinL $ rest
                    else rest

    takeWhileM :: List l => (a -> ItemM l Bool) -> l a -> l a
    takeWhileM :: forall (l :: * -> *) a. List l => (a -> ItemM l Bool) -> l a -> l a
    takeWhileM a -> ItemM l Bool
    cond =
        ItemM l (l a) -> l a
    forall a. ItemM l (l a) -> l a
    forall (l :: * -> *) a. List l => ItemM l (l a) -> l a
    joinL (ItemM l (l a) -> l a) -> (l a -> ItemM l (l a)) -> l a -> l a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> ItemM l (l a) -> ItemM l (l a))
    -> ItemM l (l a) -> l a -> ItemM l (l a)
    forall (l :: * -> *) a b.
    List l =>
    (a -> ItemM l b -> ItemM l b) -> ItemM l b -> l a -> ItemM l b
    foldrL a -> ItemM l (l a) -> ItemM l (l a)
    step (l a -> ItemM l (l a)
    forall a. a -> ItemM l a
    forall (m :: * -> *) a. Monad m => a -> m a
    return l a
    forall a. l a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero)
        where
            step :: a -> ItemM l (l a) -> ItemM l (l a)
    step a
    x ItemM l (l a)
    rest = do
                b <- a -> ItemM l Bool
    cond a
    x
                if b
                    then return . cons x . joinL $ rest
                    else return mzero

    -- | An action to transform a 'List' to a list
    --
    -- > > runIdentity $ toList "hello!"
    -- > "hello!"
    toList :: List l => l a -> ItemM l [a]
    toList :: forall (l :: * -> *) a. List l => l a -> ItemM l [a]
    toList =
        (a -> ItemM l [a] -> ItemM l [a])
    -> ItemM l [a] -> l a -> ItemM l [a]
    forall (l :: * -> *) a b.
    List l =>
    (a -> ItemM l b -> ItemM l b) -> ItemM l b -> l a -> ItemM l b
    foldrL a -> ItemM l [a] -> ItemM l [a]
    forall {a}. a -> ItemM l [a] -> ItemM l [a]
    step ([a] -> ItemM l [a]
    forall a. a -> ItemM l a
    forall (m :: * -> *) a. Monad m => a -> m a
    return [])
        where
            step :: a -> ItemM l [a] -> ItemM l [a]
    step = ([a] -> [a]) -> ItemM l [a] -> ItemM l [a]
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM (([a] -> [a]) -> ItemM l [a] -> ItemM l [a])
    -> (a -> [a] -> [a]) -> a -> ItemM l [a] -> ItemM l [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (:)

    -- | Consume a list (execute its actions) and return its length
    --
    -- > > runIdentity $ lengthL [1,2,3]
    -- > 3
    lengthL :: (Integral i, List l) => l a -> ItemM l i
    lengthL :: forall i (l :: * -> *) a. (Integral i, List l) => l a -> ItemM l i
    lengthL = (i -> a -> i) -> i -> l a -> ItemM l i
    forall (l :: * -> *) a b.
    List l =>
    (a -> b -> a) -> a -> l b -> ItemM l a
    foldlL (i -> a -> i
    forall a b. a -> b -> a
    const (i -> a -> i) -> (i -> i) -> i -> a -> i
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (i -> i -> i
    forall a. Num a => a -> a -> a
    + i
    1)) i
    0

    -- | Transform the underlying monad of a list given a way to transform the monad
    --
    -- > > import Data.List.Tree (bfs)
    -- > > bfs (transformListMonad (\(Identity x) -> [x, x]) "hey" :: ListT [] Char)
    -- > "hheeeeyyyyyyyy"
    transformListMonad :: (List l, List k) =>
        (ItemM l (k a) -> ItemM k (k a)) -> l a -> k a
    transformListMonad :: forall (l :: * -> *) (k :: * -> *) a.
    (List l, List k) =>
    (ItemM l (k a) -> ItemM k (k a)) -> l a -> k a
    transformListMonad ItemM l (k a) -> ItemM k (k a)
    trans =
        ItemM l (k a) -> k a
    t (ItemM l (k a) -> k a) -> (l a -> ItemM l (k a)) -> l a -> k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> ItemM l (k a) -> ItemM l (k a))
    -> ItemM l (k a) -> l a -> ItemM l (k a)
    forall (l :: * -> *) a b.
    List l =>
    (a -> ItemM l b -> ItemM l b) -> ItemM l b -> l a -> ItemM l b
    foldrL a -> ItemM l (k a) -> ItemM l (k a)
    step (k a -> ItemM l (k a)
    forall a. a -> ItemM l a
    forall (m :: * -> *) a. Monad m => a -> m a
    return k a
    forall a. k a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero)
        where
            t :: ItemM l (k a) -> k a
    t = ItemM k (k a) -> k a
    forall a. ItemM k (k a) -> k a
    forall (l :: * -> *) a. List l => ItemM l (l a) -> l a
    joinL (ItemM k (k a) -> k a)
    -> (ItemM l (k a) -> ItemM k (k a)) -> ItemM l (k a) -> k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ItemM l (k a) -> ItemM k (k a)
    trans
            step :: a -> ItemM l (k a) -> ItemM l (k a)
    step a
    x = k a -> ItemM l (k a)
    forall a. a -> ItemM l a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (k a -> ItemM l (k a))
    -> (ItemM l (k a) -> k a) -> ItemM l (k a) -> ItemM l (k a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> k a -> k a
    forall a. a -> k a -> k a
    forall (l :: * -> *) a. List l => a -> l a -> l a
    cons a
    x (k a -> k a) -> (ItemM l (k a) -> k a) -> ItemM l (k a) -> k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ItemM l (k a) -> k a
    t

    zip :: List l => l a -> l b -> l (a, b)
    zip :: forall (l :: * -> *) a b. List l => l a -> l b -> l (a, b)
    zip l a
    xx l b
    yy =
        l (a, b) -> (a -> l a -> l (a, b)) -> l a -> l (a, b)
    forall (l :: * -> *) r a.
    List l =>
    l r -> (a -> l a -> l r) -> l a -> l r
    deconstructList' l (a, b)
    forall a. l a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero a -> l a -> l (a, b)
    onConsX l a
    xx
        where
            onConsX :: a -> l a -> l (a, b)
    onConsX a
    x l a
    xs = l (a, b) -> (b -> l b -> l (a, b)) -> l b -> l (a, b)
    forall (l :: * -> *) r a.
    List l =>
    l r -> (a -> l a -> l r) -> l a -> l r
    deconstructList' l (a, b)
    forall a. l a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero (a -> l a -> b -> l b -> l (a, b)
    forall {l :: * -> *} {a} {b}.
    List l =>
    a -> l a -> b -> l b -> l (a, b)
    onConsXY a
    x l a
    xs) l b
    yy
            onConsXY :: a -> l a -> b -> l b -> l (a, b)
    onConsXY a
    x l a
    xs b
    y l b
    ys = (a, b) -> l (a, b) -> l (a, b)
    forall a. a -> l a -> l a
    forall (l :: * -> *) a. List l => a -> l a -> l a
    cons (a
    x, b
    y) (l (a, b) -> l (a, b)) -> l (a, b) -> l (a, b)
    forall a b. (a -> b) -> a -> b
    $ l a -> l b -> l (a, b)
    forall (l :: * -> *) a b. List l => l a -> l b -> l (a, b)
    zip l a
    xs l b
    ys

    -- zipWith based on zip and not vice versa,
    -- because the other way around hlint compains "use zip".
    zipWith :: List l => (a -> b -> c) -> l a -> l b -> l c
    zipWith :: forall (l :: * -> *) a b c.
    List l =>
    (a -> b -> c) -> l a -> l b -> l c
    zipWith a -> b -> c
    func l a
    as = ((a, b) -> c) -> l (a, b) -> l c
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM ((a -> b -> c) -> (a, b) -> c
    forall a b c. (a -> b -> c) -> (a, b) -> c
    uncurry a -> b -> c
    func) (l (a, b) -> l c) -> (l b -> l (a, b)) -> l b -> l c
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . l a -> l b -> l (a, b)
    forall (l :: * -> *) a b. List l => l a -> l b -> l (a, b)
    zip l a
    as

    tail :: List l => l a -> l a
    tail :: forall (l :: * -> *) a. List l => l a -> l a
    tail = ItemM l (l a) -> l a
    forall a. ItemM l (l a) -> l a
    forall (l :: * -> *) a. List l => ItemM l (l a) -> l a
    joinL (ItemM l (l a) -> l a) -> (l a -> ItemM l (l a)) -> l a -> l a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (ListItem l a -> l a) -> ItemM l (ListItem l a) -> ItemM l (l a)
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM ListItem l a -> l a
    forall (l :: * -> *) a. ListItem l a -> l a
    tailL (ItemM l (ListItem l a) -> ItemM l (l a))
    -> (l a -> ItemM l (ListItem l a)) -> l a -> ItemM l (l a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . l a -> ItemM l (ListItem l a)
    forall a. l a -> ItemM l (ListItem l a)
    forall (l :: * -> *) a. List l => l a -> ItemM l (ListItem l a)
    runList

    -- | Consume all items and return the last one
    --
    -- > > runIdentity $ lastL "hello"
    -- > 'o'
    lastL :: List l => l a -> ItemM l a
    lastL :: forall (l :: * -> *) a. List l => l a -> ItemM l a
    lastL = (Maybe a -> a) -> ItemM l (Maybe a) -> ItemM l a
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM Maybe a -> a
    forall a. HasCallStack => Maybe a -> a
    fromJust (ItemM l (Maybe a) -> ItemM l a)
    -> (l a -> ItemM l (Maybe a)) -> l a -> ItemM l a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Maybe a -> a -> Maybe a) -> Maybe a -> l a -> ItemM l (Maybe a)
    forall (l :: * -> *) a b.
    List l =>
    (a -> b -> a) -> a -> l b -> ItemM l a
    foldlL ((a -> Maybe a) -> Maybe a -> a -> Maybe a
    forall a b. a -> b -> a
    const a -> Maybe a
    forall a. a -> Maybe a
    Just) Maybe a
    forall a. Maybe a
    Nothing

    repeat :: List l => a -> l a
    repeat :: forall (l :: * -> *) a. List l => a -> l a
    repeat = (l a -> l a) -> l a
    forall a. (a -> a) -> a
    fix ((l a -> l a) -> l a) -> (a -> l a -> l a) -> a -> l a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> l a -> l a
    forall a. a -> l a -> l a
    forall (l :: * -> *) a. List l => a -> l a -> l a
    cons

    transpose :: List l => l (l a) -> l (l a)
    transpose :: forall (l :: * -> *) a. List l => l (l a) -> l (l a)
    transpose l (l a)
    matrix =
        ItemM l (l (l a)) -> l (l a)
    forall a. ItemM l (l a) -> l a
    forall (l :: * -> *) a. List l => ItemM l (l a) -> l a
    joinL (ItemM l (l (l a)) -> l (l a)) -> ItemM l (l (l a)) -> l (l a)
    forall a b. (a -> b) -> a -> b
    $ l (l a) -> ItemM l [l a]
    forall (l :: * -> *) a. List l => l a -> ItemM l [a]
    toList l (l a)
    matrix ItemM l [l a] -> ([l a] -> ItemM l (l (l a))) -> ItemM l (l (l a))
    forall a b. ItemM l a -> (a -> ItemM l b) -> ItemM l b
    forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
    >>= [l a] -> ItemM l (l (l a))
    forall {m :: * -> *} {l :: * -> *} {l :: * -> *} {a}.
    (ItemM m ~ ItemM l, List l, List m, List l) =>
    [l a] -> ItemM l (m (l a))
    r
        where
            r :: [l a] -> ItemM l (m (l a))
    r [l a]
    xs = do
                items <- (l a -> ItemM l (ListItem l a)) -> [l a] -> ItemM l [ListItem l a]
    forall (t :: * -> *) (m :: * -> *) a b.
    (Traversable t, Monad m) =>
    (a -> m b) -> t a -> m (t b)
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> [a] -> m [b]
    mapM l a -> ItemM l (ListItem l a)
    forall a. l a -> ItemM l (ListItem l a)
    forall (l :: * -> *) a. List l => l a -> ItemM l (ListItem l a)
    runList [l a]
    xs
                return $ case filter isCons items of
                    [] -> m (l a)
    forall a. m a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero
                    [ListItem l a]
    citems ->
                        l a -> m (l a) -> m (l a)
    forall a. a -> m a -> m a
    forall (l :: * -> *) a. List l => a -> l a -> l a
    cons ([a] -> l a
    forall (l :: * -> *) a. List l => [a] -> l a
    fromList ((ListItem l a -> a) -> [ListItem l a] -> [a]
    forall a b. (a -> b) -> [a] -> [b]
    map ListItem l a -> a
    forall (l :: * -> *) a. ListItem l a -> a
    headL [ListItem l a]
    citems)) (m (l a) -> m (l a)) -> ([l a] -> m (l a)) -> [l a] -> m (l a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    .
                        ItemM m (m (l a)) -> m (l a)
    ItemM l (m (l a)) -> m (l a)
    forall a. ItemM m (m a) -> m a
    forall (l :: * -> *) a. List l => ItemM l (l a) -> l a
    joinL (ItemM l (m (l a)) -> m (l a))
    -> ([l a] -> ItemM l (m (l a))) -> [l a] -> m (l a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [l a] -> ItemM l (m (l a))
    r ([l a] -> m (l a)) -> [l a] -> m (l a)
    forall a b. (a -> b) -> a -> b
    $ (ListItem l a -> l a) -> [ListItem l a] -> [l a]
    forall a b. (a -> b) -> [a] -> [b]
    map ListItem l a -> l a
    forall (l :: * -> *) a. ListItem l a -> l a
    tailL [ListItem l a]
    citems
            isCons :: ListItem l a -> Bool
    isCons ListItem l a
    Nil = Bool
    False
            isCons ListItem l a
    _ = Bool
    True

    -- | Merge many lists sorted by a criteria given the criteria
    --
    -- > > mergeOn length [["hi", "hey", "hello"], ["cat", "falcon"], ["banana", "cucumber"]]
    -- > ["hi","cat","hey","hello","banana","falcon","cucumber"]
    mergeOn :: (Ord b, List l) => (a -> b) -> l (l a) -> l a
    mergeOn :: forall b (l :: * -> *) a.
    (Ord b, List l) =>
    (a -> b) -> l (l a) -> l a
    mergeOn a -> b
    f = ItemM l (l a) -> l a
    forall a. ItemM l (l a) -> l a
    forall (l :: * -> *) a. List l => ItemM l (l a) -> l a
    joinL (ItemM l (l a) -> l a)
    -> (l (l a) -> ItemM l (l a)) -> l (l a) -> l a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (l a -> l a -> l a) -> l a -> l (l a) -> ItemM l (l a)
    forall (l :: * -> *) a b.
    List l =>
    (a -> b -> a) -> a -> l b -> ItemM l a
    foldlL ((a -> b) -> l a -> l a -> l a
    forall b (l :: * -> *) a.
    (Ord b, List l) =>
    (a -> b) -> l a -> l a -> l a
    merge2On a -> b
    f) l a
    forall a. l a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero

    -- | Merge two lists sorted by a criteria given the criteria
    --
    -- > > merge2On id "01568" "239"
    -- > "01235689"
    merge2On :: (Ord b, List l) => (a -> b) -> l a -> l a -> l a
    merge2On :: forall b (l :: * -> *) a.
    (Ord b, List l) =>
    (a -> b) -> l a -> l a -> l a
    merge2On a -> b
    f l a
    xx l a
    yy =
        ItemM l (l a) -> l a
    forall a. ItemM l (l a) -> l a
    forall (l :: * -> *) a. List l => ItemM l (l a) -> l a
    joinL (ItemM l (l a) -> l a) -> ItemM l (l a) -> l a
    forall a b. (a -> b) -> a -> b
    $ do
            xi <- l a -> ItemM l (ListItem l a)
    forall a. l a -> ItemM l (ListItem l a)
    forall (l :: * -> *) a. List l => l a -> ItemM l (ListItem l a)
    runList l a
    xx
            yi <- runList yy
            return $ case (xi, yi) of
                (Cons a
    x l a
    xs, Cons a
    y l a
    ys)
                    | a -> b
    f a
    y b -> b -> Bool
    forall a. Ord a => a -> a -> Bool
    > a -> b
    f a
    x -> a -> l a -> l a
    forall a. a -> l a -> l a
    forall (l :: * -> *) a. List l => a -> l a -> l a
    cons a
    x (l a -> l a) -> (l a -> l a) -> l a -> l a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> b) -> l a -> l a -> l a
    forall b (l :: * -> *) a.
    (Ord b, List l) =>
    (a -> b) -> l a -> l a -> l a
    merge2On a -> b
    f l a
    xs (l a -> l a) -> l a -> l a
    forall a b. (a -> b) -> a -> b
    $ a -> l a -> l a
    forall a. a -> l a -> l a
    forall (l :: * -> *) a. List l => a -> l a -> l a
    cons a
    y l a
    ys
                    | Bool
    otherwise -> a -> l a -> l a
    forall a. a -> l a -> l a
    forall (l :: * -> *) a. List l => a -> l a -> l a
    cons a
    y (l a -> l a) -> l a -> l a
    forall a b. (a -> b) -> a -> b
    $ (a -> b) -> l a -> l a -> l a
    forall b (l :: * -> *) a.
    (Ord b, List l) =>
    (a -> b) -> l a -> l a -> l a
    merge2On a -> b
    f (a -> l a -> l a
    forall a. a -> l a -> l a
    forall (l :: * -> *) a. List l => a -> l a -> l a
    cons a
    x l a
    xs) l a
    ys
                (Cons a
    x l a
    xs, ListItem l a
    Nil) -> a -> l a -> l a
    forall a. a -> l a -> l a
    forall (l :: * -> *) a. List l => a -> l a -> l a
    cons a
    x l a
    xs
                (ListItem l a
    Nil, Cons a
    y l a
    ys) -> a -> l a -> l a
    forall a. a -> l a -> l a
    forall (l :: * -> *) a. List l => a -> l a -> l a
    cons a
    y l a
    ys
                (ListItem l a
    Nil, ListItem l a
    Nil) -> l a
    forall a. l a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero

    -- sorts require looking at the whole list
    -- even before the consumption of the first result element,
    -- so they make no sense for monadic lists
    sortOn :: Ord b => (a -> b) -> [a] -> [a]
    sortOn :: forall b a. Ord b => (a -> b) -> [a] -> [a]
    sortOn = (a -> a -> Ordering) -> [a] -> [a]
    forall a. (a -> a -> Ordering) -> [a] -> [a]
    sortBy ((a -> a -> Ordering) -> [a] -> [a])
    -> ((a -> b) -> a -> a -> Ordering) -> (a -> b) -> [a] -> [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> b) -> a -> a -> Ordering
    forall a b. Ord a => (b -> a) -> b -> b -> Ordering
    comparing

    -- | Monadic version of iterate.
    -- Can be used to produce trees given a children of node function.
    --
    -- > import Data.List.Tree (bfsLayers)
    -- > take 3 $ bfsLayers (iterateM (\i -> [i*2, i*2+1]) [1] :: ListT [] Int)
    -- > [[1],[2,3],[4,5,6,7]]
    iterateM :: List l => (a -> ItemM l a) -> ItemM l a -> l a
    iterateM :: forall (l :: * -> *) a.
    List l =>
    (a -> ItemM l a) -> ItemM l a -> l a
    iterateM a -> ItemM l a
    step ItemM l a
    startM =
        ItemM l (l a) -> l a
    forall a. ItemM l (l a) -> l a
    forall (l :: * -> *) a. List l => ItemM l (l a) -> l a
    joinL (ItemM l (l a) -> l a) -> ItemM l (l a) -> l a
    forall a b. (a -> b) -> a -> b
    $ do
            start <- ItemM l a
    startM
            return . cons start
                . iterateM step
                . step $ start

    -- | Monadic variant of splitAt.
    -- Consumes x items from the list and return them with the remaining monadic list.
    splitAtM :: List l => Int -> l a -> ItemM l ([a], l a)
    splitAtM :: forall (l :: * -> *) a. List l => Int -> l a -> ItemM l ([a], l a)
    splitAtM Int
    at l a
    list
        | Int
    at Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    <= Int
    0 = ([a], l a) -> ItemM l ([a], l a)
    forall a. a -> ItemM l a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ([], l a
    list)
        | Bool
    otherwise = do
            item <- l a -> ItemM l (ListItem l a)
    forall a. l a -> ItemM l (ListItem l a)
    forall (l :: * -> *) a. List l => l a -> ItemM l (ListItem l a)
    runList l a
    list
            case item of
                ListItem l a
    Nil -> ([a], l a) -> ItemM l ([a], l a)
    forall a. a -> ItemM l a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ([], l a
    forall a. l a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero)
                Cons a
    x l a
    xs -> do
                    (pre, post) <- Int -> l a -> ItemM l ([a], l a)
    forall (l :: * -> *) a. List l => Int -> l a -> ItemM l ([a], l a)
    splitAtM (Int
    atInt -> Int -> Int
    forall a. Num a => a -> a -> a
    -Int
    1) l a
    xs
                    return (x:pre, post)

    -- | Monadic variant of break.
    -- Consumes items from the list until a condition holds.
    splitWhenM :: List l => (a -> ItemM l Bool) -> l a -> ItemM l ([a], l a)
    splitWhenM :: forall (l :: * -> *) a.
    List l =>
    (a -> ItemM l Bool) -> l a -> ItemM l ([a], l a)
    splitWhenM a -> ItemM l Bool
    cond l a
    list = do
        item <- l a -> ItemM l (ListItem l a)
    forall a. l a -> ItemM l (ListItem l a)
    forall (l :: * -> *) a. List l => l a -> ItemM l (ListItem l a)
    runList l a
    list
        case item of
            ListItem l a
    Nil -> ([a], l a) -> ItemM l ([a], l a)
    forall a. a -> ItemM l a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ([], l a
    forall a. l a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero)
            Cons a
    x l a
    xs -> do
                isSplit <- a -> ItemM l Bool
    cond a
    x
                if isSplit
                    then return ([], cons x xs)
                    else do
                        (pre, post) <- splitWhenM cond xs
                        return (x:pre, post)

    -- | listStateJoin can transform a
    -- @ListT (StateT s m) a@ to a @StateT s m (ListT m a)@.
    --
    -- When iterating a list, a state is already maintained and passed along
    -- in the form of the location along the list.
    -- This joins the inner @StateT s@ into the list.
    -- The list will fork the state given to it and won't share its changes.
    listStateJoin :: (List l, List k, ItemM l ~ StateT s (ItemM k))
        => l a -> ItemM l (k a)
    listStateJoin :: forall (l :: * -> *) (k :: * -> *) s a.
    (List l, List k, ItemM l ~ StateT s (ItemM k)) =>
    l a -> ItemM l (k a)
    listStateJoin l a
    list = do
        start <- StateT s (ItemM k) s
    forall (m :: * -> *) s. Monad m => StateT s m s
    get
        return . joinL . (`evalStateT` start) $ deconstructList (return mzero) onCons list
        where
            onCons :: a -> l a -> StateT s (ItemM l) (l a)
    onCons a
    x = (l a -> l a)
    -> StateT s (ItemM l) (l a) -> StateT s (ItemM l) (l a)
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM (a -> l a -> l a
    forall a. a -> l a -> l a
    forall (l :: * -> *) a. List l => a -> l a -> l a
    cons a
    x) (StateT s (ItemM l) (l a) -> StateT s (ItemM l) (l a))
    -> (l a -> StateT s (ItemM l) (l a))
    -> l a
    -> StateT s (ItemM l) (l a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . l a -> StateT s (ItemM l) (l a)
    l a -> ItemM l (l a)
    forall (l :: * -> *) (k :: * -> *) s a.
    (List l, List k, ItemM l ~ StateT s (ItemM k)) =>
    l a -> ItemM l (k a)
    listStateJoin

    -- | Generalized 'concat'
    --
    -- For @List l => l (l a) -> l a@ use 'join'
    concat :: List l => l [a] -> l a
    concat :: forall (l :: * -> *) a. List l => l [a] -> l a
    concat = l (l a) -> l a
    forall (m :: * -> *) a. Monad m => m (m a) -> m a
    join (l (l a) -> l a) -> (l [a] -> l (l a)) -> l [a] -> l a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ([a] -> l a) -> l [a] -> l (l a)
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM [a] -> l a
    forall (l :: * -> *) a. List l => [a] -> l a
    fromList

    -- | Genereralized 'concatMap'
    --
    -- For @List l => (a -> l b) -> l a -> l b@ use '=<<' (monadic bind)
    concatMap :: List l => (a -> [b]) -> l a -> l b
    concatMap :: forall (l :: * -> *) a b. List l => (a -> [b]) -> l a -> l b
    concatMap a -> [b]
    f = l [b] -> l b
    forall (l :: * -> *) a. List l => l [a] -> l a
    concat (l [b] -> l b) -> (l a -> l [b]) -> l a -> l b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> [b]) -> l a -> l [b]
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM a -> [b]
    f

    catMaybes :: List l => l (Maybe a) -> l a
    catMaybes :: forall (l :: * -> *) a. List l => l (Maybe a) -> l a
    catMaybes =
        (Maybe a -> [a]) -> l (Maybe a) -> l a
    forall (l :: * -> *) a b. List l => (a -> [b]) -> l a -> l b
    concatMap Maybe a -> [a]
    forall {m :: * -> *} {a}. MonadPlus m => Maybe a -> m a
    f
        where
            f :: Maybe a -> m a
    f Maybe a
    Nothing = m a
    forall a. m a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero
            f (Just a
    x) = a -> m a
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return a
    x

    mapMaybe :: List l => (a -> Maybe b) -> l a -> l b
    mapMaybe :: forall (l :: * -> *) a b. List l => (a -> Maybe b) -> l a -> l b
    mapMaybe a -> Maybe b
    f = l (Maybe b) -> l b
    forall (l :: * -> *) a. List l => l (Maybe a) -> l a
    catMaybes (l (Maybe b) -> l b) -> (l a -> l (Maybe b)) -> l a -> l b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> Maybe b) -> l a -> l (Maybe b)
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM a -> Maybe b
    f

    enumFrom :: (List l, Enum a) => a -> l a
    enumFrom :: forall (l :: * -> *) a. (List l, Enum a) => a -> l a
    enumFrom a
    x = a -> l a -> l a
    forall a. a -> l a -> l a
    forall (l :: * -> *) a. List l => a -> l a -> l a
    cons a
    x (a -> l a
    forall (l :: * -> *) a. (List l, Enum a) => a -> l a
    enumFrom (a -> a
    forall a. Enum a => a -> a
    succ a
    x))

    enumFromTo :: (List l, Enum a) => a -> a -> l a
    enumFromTo :: forall (l :: * -> *) a. (List l, Enum a) => a -> a -> l a
    enumFromTo a
    from a
    to
        | a -> Int
    forall a. Enum a => a -> Int
    fromEnum a
    from Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > a -> Int
    forall a. Enum a => a -> Int
    fromEnum a
    to = l a
    forall a. l a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero
        | Bool
    otherwise = a -> l a -> l a
    forall a. a -> l a -> l a
    forall (l :: * -> *) a. List l => a -> l a -> l a
    cons a
    from (a -> a -> l a
    forall (l :: * -> *) a. (List l, Enum a) => a -> a -> l a
    enumFromTo (a -> a
    forall a. Enum a => a -> a
    succ a
    from) a
    to)