    {-# LANGUAGE CPP #-}

    -- | See 'Filtrable'.
    module Data.Filtrable
      ( Filtrable (..)
      , (<$?>), (<*?>)
      , nub, nubBy, nubOrd, nubOrdBy
      ) where

    import Prelude hiding (filter)

    import Control.Applicative
    import Control.Applicative.Backwards
    import Control.Monad
    import qualified Control.Monad.Trans.State as M
    import Data.Bool (bool)
    import Data.Functor.Compose
    import Data.Functor.Product
    import Data.Functor.Reverse
    import Data.Functor.Sum
    import Data.Proxy
    import Data.Traversable

    #ifdef MIN_VERSION_containers
    import Data.IntMap (IntMap)
    import qualified Data.IntMap as IntMap
    import Data.Map (Map)
    import qualified Data.Map as Map
    import Data.Sequence (Seq)
    import qualified Data.Sequence as Seq
    #endif

    import qualified Data.Set.Private as Set

    -- | Class of filtrable containers, i.e. containers we can map over while selectively dropping elements.
    --
    -- Laws:
    --
    -- * @'mapMaybe' 'Just' = id@
    --
    -- * @'mapMaybe' f = 'catMaybes' ∘ 'fmap' f@
    --
    -- * @'catMaybes' = 'mapMaybe' id@
    --
    -- * @'filter' f = 'mapMaybe' (\\ x -> 'bool' 'Nothing' ('Just' x) (f x))@
    --
    -- * @'mapMaybe' g . 'mapMaybe' f = 'mapMaybe' (g '<=<' f)@
    --
    --   Laws if @'Foldable' f@:
    --
    -- * @'foldMap' g . 'filter' f = 'foldMap' (\\ x -> 'bool' 'mempty' (g x) (f x))@
    class Functor f => Filtrable f where
        {-# MINIMAL mapMaybe | catMaybes #-}

        -- | Map the container with the given function, dropping the elements for which it returns 'Nothing'.
        mapMaybe :: (a -> Maybe b) -> f a -> f b
        mapMaybe a -> Maybe b
    f = f (Maybe b) -> f b
    forall a. f (Maybe a) -> f a
    forall (f :: * -> *) a. Filtrable f => f (Maybe a) -> f a
    catMaybes (f (Maybe b) -> f b) -> (f a -> f (Maybe b)) -> f a -> f b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> Maybe b) -> f a -> f (Maybe b)
    forall a b. (a -> b) -> f a -> f b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap a -> Maybe b
    f

        -- | @'catMaybes' = 'mapMaybe' 'id'@
        catMaybes :: f (Maybe a) -> f a
        catMaybes = (Maybe a -> Maybe a) -> f (Maybe a) -> f a
    forall a b. (a -> Maybe b) -> f a -> f b
    forall (f :: * -> *) a b.
    Filtrable f =>
    (a -> Maybe b) -> f a -> f b
    mapMaybe Maybe a -> Maybe a
    forall a. a -> a
    id

        -- | Drop the elements for which the given predicate is 'False'.
        filter :: (a -> Bool) -> f a -> f a
        filter a -> Bool
    f = (a -> Maybe a) -> f a -> f a
    forall a b. (a -> Maybe b) -> f a -> f b
    forall (f :: * -> *) a b.
    Filtrable f =>
    (a -> Maybe b) -> f a -> f b
    mapMaybe (a -> Maybe () -> Maybe a
    forall a b. a -> Maybe b -> Maybe a
    forall (f :: * -> *) a b. Functor f => a -> f b -> f a
    (<$) (a -> Maybe () -> Maybe a) -> (a -> Maybe ()) -> a -> Maybe a
    forall a b. (a -> a -> b) -> (a -> a) -> a -> b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> Bool -> Maybe ()
    forall (f :: * -> *). Alternative f => Bool -> f ()
    guard (Bool -> Maybe ()) -> (a -> Bool) -> a -> Maybe ()
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> Bool
    f)

        -- | Traverse the container with the given function, dropping the elements for which it returns 'Nothing'.
        mapMaybeA :: (Traversable f, Applicative p) => (a -> p (Maybe b)) -> f a -> p (f b)
        mapMaybeA a -> p (Maybe b)
    f f a
    xs = f (Maybe b) -> f b
    forall a. f (Maybe a) -> f a
    forall (f :: * -> *) a. Filtrable f => f (Maybe a) -> f a
    catMaybes (f (Maybe b) -> f b) -> p (f (Maybe b)) -> p (f b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (a -> p (Maybe b)) -> f a -> p (f (Maybe b))
    forall (t :: * -> *) (f :: * -> *) a b.
    (Traversable t, Applicative f) =>
    (a -> f b) -> t a -> f (t b)
    forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> f a -> f (f b)
    traverse a -> p (Maybe b)
    f f a
    xs

        -- | Drop the elements for which the given predicate is 'False'.
        filterA :: (Traversable f, Applicative p) => (a -> p Bool) -> f a -> p (f a)
        filterA a -> p Bool
    f = (a -> p (Maybe a)) -> f a -> p (f a)
    forall (f :: * -> *) (p :: * -> *) a b.
    (Filtrable f, Traversable f, Applicative p) =>
    (a -> p (Maybe b)) -> f a -> p (f b)
    forall (p :: * -> *) a b.
    (Traversable f, Applicative p) =>
    (a -> p (Maybe b)) -> f a -> p (f b)
    mapMaybeA (\ a
    x -> (a
    x a -> Maybe () -> Maybe a
    forall a b. a -> Maybe b -> Maybe a
    forall (f :: * -> *) a b. Functor f => a -> f b -> f a
    <$) (Maybe () -> Maybe a) -> (Bool -> Maybe ()) -> Bool -> Maybe a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Bool -> Maybe ()
    forall (f :: * -> *). Alternative f => Bool -> f ()
    guard (Bool -> Maybe a) -> p Bool -> p (Maybe a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> a -> p Bool
    f a
    x)

        -- | Map the container with the given function, collecting the 'Left's and the 'Right's separately.
        mapEither :: (a -> Either b c) -> f a -> (f b, f c)
        mapEither a -> Either b c
    f = (,) (f b -> f c -> (f b, f c))
    -> (f a -> f b) -> f a -> f c -> (f b, f c)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (a -> Maybe b) -> f a -> f b
    forall a b. (a -> Maybe b) -> f a -> f b
    forall (f :: * -> *) a b.
    Filtrable f =>
    (a -> Maybe b) -> f a -> f b
    mapMaybe ((b -> Maybe b) -> (c -> Maybe b) -> Either b c -> Maybe b
    forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
    either b -> Maybe b
    forall a. a -> Maybe a
    Just (Maybe b -> c -> Maybe b
    forall a. a -> c -> a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure Maybe b
    forall a. Maybe a
    Nothing) (Either b c -> Maybe b) -> (a -> Either b c) -> a -> Maybe b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> Either b c
    f)
                          (f a -> f c -> (f b, f c)) -> (f a -> f c) -> f a -> (f b, f c)
    forall a b. (f a -> a -> b) -> (f a -> a) -> f a -> b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> (a -> Maybe c) -> f a -> f c
    forall a b. (a -> Maybe b) -> f a -> f b
    forall (f :: * -> *) a b.
    Filtrable f =>
    (a -> Maybe b) -> f a -> f b
    mapMaybe ((b -> Maybe c) -> (c -> Maybe c) -> Either b c -> Maybe c
    forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
    either (Maybe c -> b -> Maybe c
    forall a. a -> b -> a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure Maybe c
    forall a. Maybe a
    Nothing) c -> Maybe c
    forall a. a -> Maybe a
    Just (Either b c -> Maybe c) -> (a -> Either b c) -> a -> Maybe c
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> Either b c
    f)

        -- | Traverse the container with the given function, collecting the 'Left's and the 'Right's separately.
        mapEitherA :: (Traversable f, Applicative p) => (a -> p (Either b c)) -> f a -> p (f b, f c)
        mapEitherA a -> p (Either b c)
    f = (f b -> f c -> (f b, f c)) -> p (f b) -> p (f c) -> p (f b, f c)
    forall a b c. (a -> b -> c) -> p a -> p b -> p c
    forall (f :: * -> *) a b c.
    Applicative f =>
    (a -> b -> c) -> f a -> f b -> f c
    liftA2 (,) (p (f b) -> p (f c) -> p (f b, f c))
    -> (f a -> p (f b)) -> f a -> p (f c) -> p (f b, f c)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (a -> p (Maybe b)) -> f a -> p (f b)
    forall (f :: * -> *) (p :: * -> *) a b.
    (Filtrable f, Traversable f, Applicative p) =>
    (a -> p (Maybe b)) -> f a -> p (f b)
    forall (p :: * -> *) a b.
    (Traversable f, Applicative p) =>
    (a -> p (Maybe b)) -> f a -> p (f b)
    mapMaybeA ((Either b c -> Maybe b) -> p (Either b c) -> p (Maybe b)
    forall a b. (a -> b) -> p a -> p b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (b -> Maybe b
    forall a. a -> Maybe a
    Just (b -> Maybe b) -> (c -> Maybe b) -> Either b c -> Maybe b
    forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
    `either` Maybe b -> c -> Maybe b
    forall a. a -> c -> a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure Maybe b
    forall a. Maybe a
    Nothing) (p (Either b c) -> p (Maybe b))
    -> (a -> p (Either b c)) -> a -> p (Maybe b)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> p (Either b c)
    f)
                                  (f a -> p (f c) -> p (f b, f c))
    -> (f a -> p (f c)) -> f a -> p (f b, f c)
    forall a b. (f a -> a -> b) -> (f a -> a) -> f a -> b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> (a -> p (Maybe c)) -> f a -> p (f c)
    forall (f :: * -> *) (p :: * -> *) a b.
    (Filtrable f, Traversable f, Applicative p) =>
    (a -> p (Maybe b)) -> f a -> p (f b)
    forall (p :: * -> *) a b.
    (Traversable f, Applicative p) =>
    (a -> p (Maybe b)) -> f a -> p (f b)
    mapMaybeA ((Either b c -> Maybe c) -> p (Either b c) -> p (Maybe c)
    forall a b. (a -> b) -> p a -> p b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (Maybe c -> b -> Maybe c
    forall a. a -> b -> a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure Maybe c
    forall a. Maybe a
    Nothing (b -> Maybe c) -> (c -> Maybe c) -> Either b c -> Maybe c
    forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
    `either` c -> Maybe c
    forall a. a -> Maybe a
    Just) (p (Either b c) -> p (Maybe c))
    -> (a -> p (Either b c)) -> a -> p (Maybe c)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> p (Either b c)
    f)

        -- | @'partitionEithers' = 'mapEither' 'id'@
        partitionEithers :: f (Either a b) -> (f a, f b)
        partitionEithers = (Either a b -> Either a b) -> f (Either a b) -> (f a, f b)
    forall a b c. (a -> Either b c) -> f a -> (f b, f c)
    forall (f :: * -> *) a b c.
    Filtrable f =>
    (a -> Either b c) -> f a -> (f b, f c)
    mapEither Either a b -> Either a b
    forall a. a -> a
    id

    instance Filtrable [] where
        mapMaybe :: forall a b. (a -> Maybe b) -> [a] -> [b]
    mapMaybe a -> Maybe b
    f = (a -> [b] -> [b]) -> [b] -> [a] -> [b]
    forall a b. (a -> b -> b) -> b -> [a] -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr (([b] -> [b]) -> (b -> [b] -> [b]) -> Maybe b -> [b] -> [b]
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe [b] -> [b]
    forall a. a -> a
    id (:) (Maybe b -> [b] -> [b]) -> (a -> Maybe b) -> a -> [b] -> [b]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> Maybe b
    f) []

        mapMaybeA :: forall (p :: * -> *) a b.
    (Traversable [], Applicative p) =>
    (a -> p (Maybe b)) -> [a] -> p [b]
    mapMaybeA a -> p (Maybe b)
    _ [] = [b] -> p [b]
    forall a. a -> p a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure []
        mapMaybeA a -> p (Maybe b)
    f (a
    x:[a]
    xs) = ([b] -> [b]) -> (b -> [b] -> [b]) -> Maybe b -> [b] -> [b]
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe [b] -> [b]
    forall a. a -> a
    id (:) (Maybe b -> [b] -> [b]) -> p (Maybe b) -> p ([b] -> [b])
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> a -> p (Maybe b)
    f a
    x p ([b] -> [b]) -> p [b] -> p [b]
    forall a b. p (a -> b) -> p a -> p b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> (a -> p (Maybe b)) -> [a] -> p [b]
    forall (f :: * -> *) (p :: * -> *) a b.
    (Filtrable f, Traversable f, Applicative p) =>
    (a -> p (Maybe b)) -> f a -> p (f b)
    forall (p :: * -> *) a b.
    (Traversable [], Applicative p) =>
    (a -> p (Maybe b)) -> [a] -> p [b]
    mapMaybeA a -> p (Maybe b)
    f [a]
    xs

    instance Filtrable Maybe where
        mapMaybe :: forall a b. (a -> Maybe b) -> Maybe a -> Maybe b
    mapMaybe = (a -> Maybe b) -> Maybe a -> Maybe b
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
    (=<<)
        catMaybes :: forall a. Maybe (Maybe a) -> Maybe a
    catMaybes = Maybe (Maybe a) -> Maybe a
    forall (m :: * -> *) a. Monad m => m (m a) -> m a
    join

    instance Filtrable Proxy where
        mapMaybe :: forall a b. (a -> Maybe b) -> Proxy a -> Proxy b
    mapMaybe a -> Maybe b
    _ Proxy a
    Proxy = Proxy b
    forall {k} (t :: k). Proxy t
    Proxy

    instance Filtrable (Const a) where
        mapMaybe :: forall a b. (a -> Maybe b) -> Const a a -> Const a b
    mapMaybe a -> Maybe b
    _ (Const a
    x) = a -> Const a b
    forall {k} a (b :: k). a -> Const a b
    Const a
    x

    instance (Filtrable f, Filtrable g) => Filtrable (Product f g) where
        mapMaybe :: forall a b. (a -> Maybe b) -> Product f g a -> Product f g b
    mapMaybe a -> Maybe b
    f (Pair f a
    as g a
    bs) = f b -> g b -> Product f g b
    forall {k} (f :: k -> *) (g :: k -> *) (a :: k).
    f a -> g a -> Product f g a
    Pair ((a -> Maybe b) -> f a -> f b
    forall a b. (a -> Maybe b) -> f a -> f b
    forall (f :: * -> *) a b.
    Filtrable f =>
    (a -> Maybe b) -> f a -> f b
    mapMaybe a -> Maybe b
    f f a
    as) ((a -> Maybe b) -> g a -> g b
    forall a b. (a -> Maybe b) -> g a -> g b
    forall (f :: * -> *) a b.
    Filtrable f =>
    (a -> Maybe b) -> f a -> f b
    mapMaybe a -> Maybe b
    f g a
    bs)

    instance (Filtrable f, Filtrable g) => Filtrable (Sum f g) where
        mapMaybe :: forall a b. (a -> Maybe b) -> Sum f g a -> Sum f g b
    mapMaybe a -> Maybe b
    f = \ case
            InL f a
    as -> f b -> Sum f g b
    forall {k} (f :: k -> *) (g :: k -> *) (a :: k). f a -> Sum f g a
    InL ((a -> Maybe b) -> f a -> f b
    forall a b. (a -> Maybe b) -> f a -> f b
    forall (f :: * -> *) a b.
    Filtrable f =>
    (a -> Maybe b) -> f a -> f b
    mapMaybe a -> Maybe b
    f f a
    as)
            InR g a
    bs -> g b -> Sum f g b
    forall {k} (f :: k -> *) (g :: k -> *) (a :: k). g a -> Sum f g a
    InR ((a -> Maybe b) -> g a -> g b
    forall a b. (a -> Maybe b) -> g a -> g b
    forall (f :: * -> *) a b.
    Filtrable f =>
    (a -> Maybe b) -> f a -> f b
    mapMaybe a -> Maybe b
    f g a
    bs)

    instance (Functor f, Filtrable g) => Filtrable (Compose f g) where
        mapMaybe :: forall a b. (a -> Maybe b) -> Compose f g a -> Compose f g b
    mapMaybe a -> Maybe b
    f = f (g b) -> Compose f g b
    forall {k} {k1} (f :: k -> *) (g :: k1 -> k) (a :: k1).
    f (g a) -> Compose f g a
    Compose (f (g b) -> Compose f g b)
    -> (Compose f g a -> f (g b)) -> Compose f g a -> Compose f g b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ((g a -> g b) -> f (g a) -> f (g b)
    forall a b. (a -> b) -> f a -> f b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap ((g a -> g b) -> f (g a) -> f (g b))
    -> ((a -> Maybe b) -> g a -> g b)
    -> (a -> Maybe b)
    -> f (g a)
    -> f (g b)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> Maybe b) -> g a -> g b
    forall a b. (a -> Maybe b) -> g a -> g b
    forall (f :: * -> *) a b.
    Filtrable f =>
    (a -> Maybe b) -> f a -> f b
    mapMaybe) a -> Maybe b
    f (f (g a) -> f (g b))
    -> (Compose f g a -> f (g a)) -> Compose f g a -> f (g b)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Compose f g a -> f (g a)
    forall {k1} {k2} (f :: k1 -> *) (g :: k2 -> k1) (a :: k2).
    Compose f g a -> f (g a)
    getCompose

    instance Filtrable f => Filtrable (Backwards f) where
        mapMaybe :: forall a b. (a -> Maybe b) -> Backwards f a -> Backwards f b
    mapMaybe a -> Maybe b
    f = f b -> Backwards f b
    forall {k} (f :: k -> *) (a :: k). f a -> Backwards f a
    Backwards (f b -> Backwards f b)
    -> (Backwards f a -> f b) -> Backwards f a -> Backwards f b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> Maybe b) -> f a -> f b
    forall a b. (a -> Maybe b) -> f a -> f b
    forall (f :: * -> *) a b.
    Filtrable f =>
    (a -> Maybe b) -> f a -> f b
    mapMaybe a -> Maybe b
    f (f a -> f b) -> (Backwards f a -> f a) -> Backwards f a -> f b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Backwards f a -> f a
    forall {k} (f :: k -> *) (a :: k). Backwards f a -> f a
    forwards

    instance Filtrable f => Filtrable (Reverse f) where
        mapMaybe :: forall a b. (a -> Maybe b) -> Reverse f a -> Reverse f b
    mapMaybe a -> Maybe b
    f = f b -> Reverse f b
    forall {k} (f :: k -> *) (a :: k). f a -> Reverse f a
    Reverse (f b -> Reverse f b)
    -> (Reverse f a -> f b) -> Reverse f a -> Reverse f b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> Maybe b) -> f a -> f b
    forall a b. (a -> Maybe b) -> f a -> f b
    forall (f :: * -> *) a b.
    Filtrable f =>
    (a -> Maybe b) -> f a -> f b
    mapMaybe a -> Maybe b
    f (f a -> f b) -> (Reverse f a -> f a) -> Reverse f a -> f b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Reverse f a -> f a
    forall {k} (f :: k -> *) (a :: k). Reverse f a -> f a
    getReverse

    infixl 4 <$?>, <*?>

    -- | Infix synonym of 'mapMaybe'
    (<$?>) :: Filtrable f => (a -> Maybe b) -> f a -> f b
    <$?> :: forall (f :: * -> *) a b.
    Filtrable f =>
    (a -> Maybe b) -> f a -> f b
    (<$?>) = (a -> Maybe b) -> f a -> f b
    forall a b. (a -> Maybe b) -> f a -> f b
    forall (f :: * -> *) a b.
    Filtrable f =>
    (a -> Maybe b) -> f a -> f b
    mapMaybe

    -- | @f '<*?>' a = 'catMaybes' (f '<*>' a)@
    (<*?>) :: (Applicative p, Filtrable p) => p (a -> Maybe b) -> p a -> p b
    p (a -> Maybe b)
    f <*?> :: forall (p :: * -> *) a b.
    (Applicative p, Filtrable p) =>
    p (a -> Maybe b) -> p a -> p b
    <*?> p a
    a = p (Maybe b) -> p b
    forall a. p (Maybe a) -> p a
    forall (f :: * -> *) a. Filtrable f => f (Maybe a) -> f a
    catMaybes (p (a -> Maybe b)
    f p (a -> Maybe b) -> p a -> p (Maybe b)
    forall a b. p (a -> b) -> p a -> p b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> p a
    a)

    -- | \(\mathcal{O}(n^2)\)
    -- Delete all but the first copy of each element, special case of 'nubBy'.
    nub :: (Filtrable f, Traversable f, Eq a) => f a -> f a
    nub :: forall (f :: * -> *) a.
    (Filtrable f, Traversable f, Eq a) =>
    f a -> f a
    nub = (a -> a -> Bool) -> f a -> f a
    forall (f :: * -> *) a.
    (Filtrable f, Traversable f) =>
    (a -> a -> Bool) -> f a -> f a
    nubBy a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    (==)

    -- | \(\mathcal{O}(n^2)\)
    -- Delete all but the first copy of each element, with the given relation.
    nubBy :: (Filtrable f, Traversable f) => (a -> a -> Bool) -> f a -> f a
    nubBy :: forall (f :: * -> *) a.
    (Filtrable f, Traversable f) =>
    (a -> a -> Bool) -> f a -> f a
    nubBy a -> a -> Bool
    eq = (State [a] (f a) -> f a) -> (f a -> State [a] (f a)) -> f a -> f a
    forall a b. (a -> b) -> (f a -> a) -> f a -> b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap ((State [a] (f a) -> [a] -> f a) -> [a] -> State [a] (f a) -> f a
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip State [a] (f a) -> [a] -> f a
    forall s a. State s a -> s -> a
    M.evalState []) ((f a -> State [a] (f a)) -> f a -> f a)
    -> ((a -> StateT [a] Identity Bool) -> f a -> State [a] (f a))
    -> (a -> StateT [a] Identity Bool)
    -> f a
    -> f a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> StateT [a] Identity Bool) -> f a -> State [a] (f a)
    forall (f :: * -> *) (p :: * -> *) a.
    (Filtrable f, Traversable f, Applicative p) =>
    (a -> p Bool) -> f a -> p (f a)
    forall (p :: * -> *) a.
    (Traversable f, Applicative p) =>
    (a -> p Bool) -> f a -> p (f a)
    filterA ((a -> StateT [a] Identity Bool) -> f a -> f a)
    -> (a -> StateT [a] Identity Bool) -> f a -> f a
    forall a b. (a -> b) -> a -> b
    $ \ a
    a -> do
        as <- StateT [a] Identity [a]
    forall (m :: * -> *) s. Monad m => StateT s m s
    M.get
        let b = (a -> Bool) -> [a] -> Bool
    forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
    all (Bool -> Bool
    not (Bool -> Bool) -> (a -> Bool) -> a -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> a -> Bool
    eq a
    a) [a]
    as
        b <$ when b (M.modify (a:))

    -- | \(\mathcal{O}(n\;\mathrm{log}\;n)\)
    -- Delete all but the first copy of each element, special case of 'nubOrdBy'.
    nubOrd :: (Filtrable f, Traversable f, Ord a) => f a -> f a
    nubOrd :: forall (f :: * -> *) a.
    (Filtrable f, Traversable f, Ord a) =>
    f a -> f a
    nubOrd = (a -> a -> Ordering) -> f a -> f a
    forall (f :: * -> *) a.
    (Filtrable f, Traversable f) =>
    (a -> a -> Ordering) -> f a -> f a
    nubOrdBy a -> a -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare

    -- | \(\mathcal{O}(n\;\mathrm{log}\;n)\)
    -- Delete all but the first copy of each element, with the given relation.
    nubOrdBy :: (Filtrable f, Traversable f) => (a -> a -> Ordering) -> f a -> f a
    nubOrdBy :: forall (f :: * -> *) a.
    (Filtrable f, Traversable f) =>
    (a -> a -> Ordering) -> f a -> f a
    nubOrdBy a -> a -> Ordering
    compare = (State (Set a) (f a) -> f a)
    -> (f a -> State (Set a) (f a)) -> f a -> f a
    forall a b. (a -> b) -> (f a -> a) -> f a -> b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap ((State (Set a) (f a) -> Set a -> f a)
    -> Set a -> State (Set a) (f a) -> f a
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip State (Set a) (f a) -> Set a -> f a
    forall s a. State s a -> s -> a
    M.evalState Set a
    forall a. Set a
    Set.empty) ((f a -> State (Set a) (f a)) -> f a -> f a)
    -> ((a -> StateT (Set a) Identity Bool)
        -> f a -> State (Set a) (f a))
    -> (a -> StateT (Set a) Identity Bool)
    -> f a
    -> f a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> StateT (Set a) Identity Bool) -> f a -> State (Set a) (f a)
    forall (f :: * -> *) (p :: * -> *) a.
    (Filtrable f, Traversable f, Applicative p) =>
    (a -> p Bool) -> f a -> p (f a)
    forall (p :: * -> *) a.
    (Traversable f, Applicative p) =>
    (a -> p Bool) -> f a -> p (f a)
    filterA ((a -> StateT (Set a) Identity Bool) -> f a -> f a)
    -> (a -> StateT (Set a) Identity Bool) -> f a -> f a
    forall a b. (a -> b) -> a -> b
    $ \ a
    a -> (Set a -> (Bool, Set a)) -> StateT (Set a) Identity Bool
    forall (m :: * -> *) s a. Monad m => (s -> (a, s)) -> StateT s m a
    M.state ((Set a -> (Bool, Set a)) -> StateT (Set a) Identity Bool)
    -> (Set a -> (Bool, Set a)) -> StateT (Set a) Identity Bool
    forall a b. (a -> b) -> a -> b
    $ \ Set a
    as ->
        case (a -> a -> Ordering) -> a -> Set a -> Maybe (Set a)
    forall a. (a -> a -> Ordering) -> a -> Set a -> Maybe (Set a)
    Set.insertBy' a -> a -> Ordering
    compare a
    a Set a
    as of
            Maybe (Set a)
    Nothing -> (Bool
    False, Set a
    as)
            Just Set a
    as' -> (Bool
    True, Set a
    as')

    #ifdef MIN_VERSION_containers
    instance Filtrable IntMap where
        mapMaybe :: forall a b. (a -> Maybe b) -> IntMap a -> IntMap b
    mapMaybe = (a -> Maybe b) -> IntMap a -> IntMap b
    forall a b. (a -> Maybe b) -> IntMap a -> IntMap b
    IntMap.mapMaybe
        mapEither :: forall a b c. (a -> Either b c) -> IntMap a -> (IntMap b, IntMap c)
    mapEither = (a -> Either b c) -> IntMap a -> (IntMap b, IntMap c)
    forall a b c. (a -> Either b c) -> IntMap a -> (IntMap b, IntMap c)
    IntMap.mapEither
        filter :: forall a. (a -> Bool) -> IntMap a -> IntMap a
    filter = (a -> Bool) -> IntMap a -> IntMap a
    forall a. (a -> Bool) -> IntMap a -> IntMap a
    IntMap.filter

    instance Ord k => Filtrable (Map k) where
        mapMaybe :: forall a b. (a -> Maybe b) -> Map k a -> Map k b
    mapMaybe = (a -> Maybe b) -> Map k a -> Map k b
    forall a b k. (a -> Maybe b) -> Map k a -> Map k b
    Map.mapMaybe
        mapEither :: forall a b c. (a -> Either b c) -> Map k a -> (Map k b, Map k c)
    mapEither = (a -> Either b c) -> Map k a -> (Map k b, Map k c)
    forall a b c k. (a -> Either b c) -> Map k a -> (Map k b, Map k c)
    Map.mapEither
        filter :: forall a. (a -> Bool) -> Map k a -> Map k a
    filter = (a -> Bool) -> Map k a -> Map k a
    forall a k. (a -> Bool) -> Map k a -> Map k a
    Map.filter

    instance Filtrable Seq where
        mapMaybe :: forall a b. (a -> Maybe b) -> Seq a -> Seq b
    mapMaybe a -> Maybe b
    f = Seq a -> Seq b
    go
          where
            go :: Seq a -> Seq b
    go = \ case
                Seq a
    Seq.Empty -> Seq b
    forall a. Seq a
    Seq.Empty
                a
    a Seq.:<| Seq a
    as -> (Seq b -> Seq b)
    -> (b -> Seq b -> Seq b) -> Maybe b -> Seq b -> Seq b
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe Seq b -> Seq b
    forall a. a -> a
    id b -> Seq b -> Seq b
    forall a. a -> Seq a -> Seq a
    (Seq.:<|) (a -> Maybe b
    f a
    a) (Seq a -> Seq b
    go Seq a
    as)
    #endif