{-# 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
    ListItem l a
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 ListItem l a
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
            Bool
b <- a -> ItemM l Bool
cond a
x
            if Bool
b
                then l a -> ItemM l (l a)
forall a. a -> ItemM l a
forall (m :: * -> *) a. Monad m => a -> m a
return (l a -> ItemM l (l a))
-> (ItemM l (l a) -> l a) -> ItemM l (l a) -> ItemM l (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 a
x (l a -> l a) -> (ItemM l (l a) -> l a) -> ItemM l (l a) -> l a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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) -> ItemM l (l a)) -> ItemM l (l a) -> ItemM l (l a)
forall a b. (a -> b) -> a -> b
$ ItemM l (l a)
rest
                else ItemM l (l a)
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
            Bool
b <- a -> ItemM l Bool
cond a
x
            if Bool
b
                then l a -> ItemM l (l a)
forall a. a -> ItemM l a
forall (m :: * -> *) a. Monad m => a -> m a
return (l a -> ItemM l (l a))
-> (ItemM l (l a) -> l a) -> ItemM l (l a) -> ItemM l (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 a
x (l a -> l a) -> (ItemM l (l a) -> l a) -> ItemM l (l a) -> l a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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) -> ItemM l (l a)) -> ItemM l (l a) -> ItemM l (l a)
forall a b. (a -> b) -> a -> b
$ ItemM l (l a)
rest
                else 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

-- | 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
            [ListItem l a]
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
            m (l a) -> ItemM l (m (l a))
forall a. a -> ItemM l a
forall (m :: * -> *) a. Monad m => a -> m a
return (m (l a) -> ItemM l (m (l a))) -> m (l a) -> ItemM l (m (l a))
forall a b. (a -> b) -> a -> b
$ case (ListItem l a -> Bool) -> [ListItem l a] -> [ListItem l a]
forall (m :: * -> *) a. MonadPlus m => (a -> Bool) -> m a -> m a
filter ListItem l a -> Bool
forall {l :: * -> *} {a}. ListItem l a -> Bool
isCons [ListItem l a]
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
        ListItem l a
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
        ListItem l a
yi <- 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
yy
        l a -> ItemM l (l a)
forall a. a -> ItemM l a
forall (m :: * -> *) a. Monad m => a -> m a
return (l a -> ItemM l (l a)) -> l a -> ItemM l (l a)
forall a b. (a -> b) -> a -> b
$ case (ListItem l a
xi, ListItem l a
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
        a
start <- ItemM l a
startM
        l a -> ItemM l (l a)
forall a. a -> ItemM l a
forall (m :: * -> *) a. Monad m => a -> m a
return (l a -> ItemM l (l a)) -> (a -> l a) -> a -> ItemM l (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 a
start
            (l a -> l a) -> (a -> l a) -> a -> l a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> ItemM l a) -> ItemM l a -> l a
forall (l :: * -> *) a.
List l =>
(a -> ItemM l a) -> ItemM l a -> l a
iterateM a -> ItemM l a
step
            (ItemM l a -> l a) -> (a -> ItemM l a) -> a -> l a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> ItemM l a
step (a -> ItemM l (l a)) -> a -> ItemM l (l a)
forall a b. (a -> b) -> a -> b
$ a
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
        ListItem l a
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 ListItem l a
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
                ([a]
pre, l a
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
                ([a], l a) -> ItemM l ([a], l a)
forall a. a -> ItemM l a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
pre, l a
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
    ListItem l a
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 ListItem l a
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
            Bool
isSplit <- a -> ItemM l Bool
cond a
x
            if Bool
isSplit
                then ([a], l a) -> ItemM l ([a], l a)
forall a. a -> ItemM l a
forall (m :: * -> *) a. Monad m => a -> m a
return ([], 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)
                else do
                    ([a]
pre, l a
post) <- (a -> ItemM l Bool) -> l a -> ItemM l ([a], l a)
forall (l :: * -> *) a.
List l =>
(a -> ItemM l Bool) -> l a -> ItemM l ([a], l a)
splitWhenM a -> ItemM l Bool
cond l a
xs
                    ([a], l a) -> ItemM l ([a], l a)
forall a. a -> ItemM l a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
pre, l a
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
    s
start <- StateT s (ItemM k) s
forall (m :: * -> *) s. Monad m => StateT s m s
get
    k a -> StateT s (ItemM k) (k a)
forall a. a -> StateT s (ItemM k) a
forall (m :: * -> *) a. Monad m => a -> m a
return (k a -> StateT s (ItemM k) (k a))
-> (StateT s (ItemM k) (k a) -> k a)
-> StateT s (ItemM k) (k a)
-> StateT s (ItemM k) (k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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)
-> (StateT s (ItemM k) (k a) -> ItemM k (k a))
-> StateT s (ItemM k) (k a)
-> k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (StateT s (ItemM k) (k a) -> s -> ItemM k (k a)
forall (m :: * -> *) s a. Monad m => StateT s m a -> s -> m a
`evalStateT` s
start) (StateT s (ItemM k) (k a) -> StateT s (ItemM k) (k a))
-> StateT s (ItemM k) (k a) -> StateT s (ItemM k) (k a)
forall a b. (a -> b) -> a -> b
$ ItemM l (k a)
-> (a -> l a -> ItemM l (k a)) -> l a -> ItemM l (k a)
forall (l :: * -> *) r a.
List l =>
ItemM l r -> (a -> l a -> ItemM l r) -> l a -> ItemM l r
deconstructList (k a -> StateT s (ItemM k) (k a)
forall a. a -> StateT s (ItemM k) a
forall (m :: * -> *) a. Monad m => a -> m a
return k a
forall a. k a
forall (m :: * -> *) a. MonadPlus m => m a
mzero) a -> l a -> StateT s (ItemM k) (k a)
a -> l a -> ItemM l (k a)
forall {l :: * -> *} {s} {l :: * -> *} {a}.
(ItemM l ~ StateT s (ItemM l), List l, List l) =>
a -> l a -> StateT s (ItemM l) (l a)
onCons l a
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)