{-
(c) The University of Glasgow 2006
(c) The GRASP/AQUA Project, Glasgow University, 1992-1998


Bag: an unordered collection with duplicates
-}

{-# LANGUAGE ScopedTypeVariables, CPP #-}

module Bag (
        Bag, -- abstract type

        emptyBag, unitBag, unionBags, unionManyBags,
        mapBag,
        elemBag, lengthBag,
        filterBag, partitionBag, partitionBagWith,
        concatBag, catBagMaybes, foldBag, foldrBag, foldlBag,
        isEmptyBag, isSingletonBag, consBag, snocBag, anyBag, allBag,
        listToBag, bagToList, mapAccumBagL,
        concatMapBag, concatMapBagPair, mapMaybeBag,
        foldrBagM, foldlBagM, mapBagM, mapBagM_,
        flatMapBagM, flatMapBagPairM,
        mapAndUnzipBagM, mapAccumBagLM,
        anyBagM, filterBagM
    ) where

import GhcPrelude

import Outputable
import Util

import MonadUtils
import Control.Monad
import Data.Data
import Data.Maybe( mapMaybe )
import Data.List ( partition, mapAccumL )
import qualified Data.Foldable as Foldable

infixr 3 `consBag`
infixl 3 `snocBag`

data Bag a
  = EmptyBag
  | UnitBag a
  | TwoBags (Bag a) (Bag a) -- INVARIANT: neither branch is empty
  | ListBag [a]             -- INVARIANT: the list is non-empty

emptyBag :: Bag a
emptyBag :: Bag a
emptyBag = Bag a
forall a. Bag a
EmptyBag

unitBag :: a -> Bag a
unitBag :: a -> Bag a
unitBag  = a -> Bag a
forall a. a -> Bag a
UnitBag

lengthBag :: Bag a -> Int
lengthBag :: Bag a -> Int
lengthBag EmptyBag        = 0
lengthBag (UnitBag {})    = 1
lengthBag (TwoBags b1 :: Bag a
b1 b2 :: Bag a
b2) = Bag a -> Int
forall a. Bag a -> Int
lengthBag Bag a
b1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Bag a -> Int
forall a. Bag a -> Int
lengthBag Bag a
b2
lengthBag (ListBag xs :: [a]
xs)    = [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs

elemBag :: Eq a => a -> Bag a -> Bool
elemBag :: a -> Bag a -> Bool
elemBag _ EmptyBag        = Bool
False
elemBag x :: a
x (UnitBag y :: a
y)     = a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y
elemBag x :: a
x (TwoBags b1 :: Bag a
b1 b2 :: Bag a
b2) = a
x a -> Bag a -> Bool
forall a. Eq a => a -> Bag a -> Bool
`elemBag` Bag a
b1 Bool -> Bool -> Bool
|| a
x a -> Bag a -> Bool
forall a. Eq a => a -> Bag a -> Bool
`elemBag` Bag a
b2
elemBag x :: a
x (ListBag ys :: [a]
ys)    = (a -> Bool) -> [a] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
==) [a]
ys

unionManyBags :: [Bag a] -> Bag a
unionManyBags :: [Bag a] -> Bag a
unionManyBags xs :: [Bag a]
xs = (Bag a -> Bag a -> Bag a) -> Bag a -> [Bag a] -> Bag a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr Bag a -> Bag a -> Bag a
forall a. Bag a -> Bag a -> Bag a
unionBags Bag a
forall a. Bag a
EmptyBag [Bag a]
xs

-- This one is a bit stricter! The bag will get completely evaluated.

unionBags :: Bag a -> Bag a -> Bag a
unionBags :: Bag a -> Bag a -> Bag a
unionBags EmptyBag b :: Bag a
b = Bag a
b
unionBags b :: Bag a
b EmptyBag = Bag a
b
unionBags b1 :: Bag a
b1 b2 :: Bag a
b2      = Bag a -> Bag a -> Bag a
forall a. Bag a -> Bag a -> Bag a
TwoBags Bag a
b1 Bag a
b2

consBag :: a -> Bag a -> Bag a
snocBag :: Bag a -> a -> Bag a

consBag :: a -> Bag a -> Bag a
consBag elt :: a
elt bag :: Bag a
bag = (a -> Bag a
forall a. a -> Bag a
unitBag a
elt) Bag a -> Bag a -> Bag a
forall a. Bag a -> Bag a -> Bag a
`unionBags` Bag a
bag
snocBag :: Bag a -> a -> Bag a
snocBag bag :: Bag a
bag elt :: a
elt = Bag a
bag Bag a -> Bag a -> Bag a
forall a. Bag a -> Bag a -> Bag a
`unionBags` (a -> Bag a
forall a. a -> Bag a
unitBag a
elt)

isEmptyBag :: Bag a -> Bool
isEmptyBag :: Bag a -> Bool
isEmptyBag EmptyBag = Bool
True
isEmptyBag _        = Bool
False -- NB invariants

isSingletonBag :: Bag a -> Bool
isSingletonBag :: Bag a -> Bool
isSingletonBag EmptyBag      = Bool
False
isSingletonBag (UnitBag _)   = Bool
True
isSingletonBag (TwoBags _ _) = Bool
False          -- Neither is empty
isSingletonBag (ListBag xs :: [a]
xs)  = [a] -> Bool
forall a. [a] -> Bool
isSingleton [a]
xs

filterBag :: (a -> Bool) -> Bag a -> Bag a
filterBag :: (a -> Bool) -> Bag a -> Bag a
filterBag _    EmptyBag = Bag a
forall a. Bag a
EmptyBag
filterBag pred :: a -> Bool
pred b :: Bag a
b@(UnitBag val :: a
val) = if a -> Bool
pred a
val then Bag a
b else Bag a
forall a. Bag a
EmptyBag
filterBag pred :: a -> Bool
pred (TwoBags b1 :: Bag a
b1 b2 :: Bag a
b2) = Bag a
sat1 Bag a -> Bag a -> Bag a
forall a. Bag a -> Bag a -> Bag a
`unionBags` Bag a
sat2
    where sat1 :: Bag a
sat1 = (a -> Bool) -> Bag a -> Bag a
forall a. (a -> Bool) -> Bag a -> Bag a
filterBag a -> Bool
pred Bag a
b1
          sat2 :: Bag a
sat2 = (a -> Bool) -> Bag a -> Bag a
forall a. (a -> Bool) -> Bag a -> Bag a
filterBag a -> Bool
pred Bag a
b2
filterBag pred :: a -> Bool
pred (ListBag vs :: [a]
vs)    = [a] -> Bag a
forall a. [a] -> Bag a
listToBag ((a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
filter a -> Bool
pred [a]
vs)

filterBagM :: Monad m => (a -> m Bool) -> Bag a -> m (Bag a)
filterBagM :: (a -> m Bool) -> Bag a -> m (Bag a)
filterBagM _    EmptyBag = Bag a -> m (Bag a)
forall (m :: * -> *) a. Monad m => a -> m a
return Bag a
forall a. Bag a
EmptyBag
filterBagM pred :: a -> m Bool
pred b :: Bag a
b@(UnitBag val :: a
val) = do
  Bool
flag <- a -> m Bool
pred a
val
  if Bool
flag then Bag a -> m (Bag a)
forall (m :: * -> *) a. Monad m => a -> m a
return Bag a
b
          else Bag a -> m (Bag a)
forall (m :: * -> *) a. Monad m => a -> m a
return Bag a
forall a. Bag a
EmptyBag
filterBagM pred :: a -> m Bool
pred (TwoBags b1 :: Bag a
b1 b2 :: Bag a
b2) = do
  Bag a
sat1 <- (a -> m Bool) -> Bag a -> m (Bag a)
forall (m :: * -> *) a.
Monad m =>
(a -> m Bool) -> Bag a -> m (Bag a)
filterBagM a -> m Bool
pred Bag a
b1
  Bag a
sat2 <- (a -> m Bool) -> Bag a -> m (Bag a)
forall (m :: * -> *) a.
Monad m =>
(a -> m Bool) -> Bag a -> m (Bag a)
filterBagM a -> m Bool
pred Bag a
b2
  Bag a -> m (Bag a)
forall (m :: * -> *) a. Monad m => a -> m a
return (Bag a
sat1 Bag a -> Bag a -> Bag a
forall a. Bag a -> Bag a -> Bag a
`unionBags` Bag a
sat2)
filterBagM pred :: a -> m Bool
pred (ListBag vs :: [a]
vs) = do
  [a]
sat <- (a -> m Bool) -> [a] -> m [a]
forall (m :: * -> *) a.
Applicative m =>
(a -> m Bool) -> [a] -> m [a]
filterM a -> m Bool
pred [a]
vs
  Bag a -> m (Bag a)
forall (m :: * -> *) a. Monad m => a -> m a
return ([a] -> Bag a
forall a. [a] -> Bag a
listToBag [a]
sat)

allBag :: (a -> Bool) -> Bag a -> Bool
allBag :: (a -> Bool) -> Bag a -> Bool
allBag _ EmptyBag        = Bool
True
allBag p :: a -> Bool
p (UnitBag v :: a
v)     = a -> Bool
p a
v
allBag p :: a -> Bool
p (TwoBags b1 :: Bag a
b1 b2 :: Bag a
b2) = (a -> Bool) -> Bag a -> Bool
forall a. (a -> Bool) -> Bag a -> Bool
allBag a -> Bool
p Bag a
b1 Bool -> Bool -> Bool
&& (a -> Bool) -> Bag a -> Bool
forall a. (a -> Bool) -> Bag a -> Bool
allBag a -> Bool
p Bag a
b2
allBag p :: a -> Bool
p (ListBag xs :: [a]
xs)    = (a -> Bool) -> [a] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all a -> Bool
p [a]
xs

anyBag :: (a -> Bool) -> Bag a -> Bool
anyBag :: (a -> Bool) -> Bag a -> Bool
anyBag _ EmptyBag        = Bool
False
anyBag p :: a -> Bool
p (UnitBag v :: a
v)     = a -> Bool
p a
v
anyBag p :: a -> Bool
p (TwoBags b1 :: Bag a
b1 b2 :: Bag a
b2) = (a -> Bool) -> Bag a -> Bool
forall a. (a -> Bool) -> Bag a -> Bool
anyBag a -> Bool
p Bag a
b1 Bool -> Bool -> Bool
|| (a -> Bool) -> Bag a -> Bool
forall a. (a -> Bool) -> Bag a -> Bool
anyBag a -> Bool
p Bag a
b2
anyBag p :: a -> Bool
p (ListBag xs :: [a]
xs)    = (a -> Bool) -> [a] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any a -> Bool
p [a]
xs

anyBagM :: Monad m => (a -> m Bool) -> Bag a -> m Bool
anyBagM :: (a -> m Bool) -> Bag a -> m Bool
anyBagM _ EmptyBag        = Bool -> m Bool
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False
anyBagM p :: a -> m Bool
p (UnitBag v :: a
v)     = a -> m Bool
p a
v
anyBagM p :: a -> m Bool
p (TwoBags b1 :: Bag a
b1 b2 :: Bag a
b2) = do Bool
flag <- (a -> m Bool) -> Bag a -> m Bool
forall (m :: * -> *) a. Monad m => (a -> m Bool) -> Bag a -> m Bool
anyBagM a -> m Bool
p Bag a
b1
                               if Bool
flag then Bool -> m Bool
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
True
                                       else (a -> m Bool) -> Bag a -> m Bool
forall (m :: * -> *) a. Monad m => (a -> m Bool) -> Bag a -> m Bool
anyBagM a -> m Bool
p Bag a
b2
anyBagM p :: a -> m Bool
p (ListBag xs :: [a]
xs)    = (a -> m Bool) -> [a] -> m Bool
forall (m :: * -> *) a. Monad m => (a -> m Bool) -> [a] -> m Bool
anyM a -> m Bool
p [a]
xs

concatBag :: Bag (Bag a) -> Bag a
concatBag :: Bag (Bag a) -> Bag a
concatBag bss :: Bag (Bag a)
bss = (Bag a -> Bag a -> Bag a) -> Bag a -> Bag (Bag a) -> Bag a
forall a r. (a -> r -> r) -> r -> Bag a -> r
foldrBag Bag a -> Bag a -> Bag a
forall a. Bag a -> Bag a -> Bag a
add Bag a
forall a. Bag a
emptyBag Bag (Bag a)
bss
  where
    add :: Bag a -> Bag a -> Bag a
add bs :: Bag a
bs rs :: Bag a
rs = Bag a
bs Bag a -> Bag a -> Bag a
forall a. Bag a -> Bag a -> Bag a
`unionBags` Bag a
rs

catBagMaybes :: Bag (Maybe a) -> Bag a
catBagMaybes :: Bag (Maybe a) -> Bag a
catBagMaybes bs :: Bag (Maybe a)
bs = (Maybe a -> Bag a -> Bag a) -> Bag a -> Bag (Maybe a) -> Bag a
forall a r. (a -> r -> r) -> r -> Bag a -> r
foldrBag Maybe a -> Bag a -> Bag a
forall a. Maybe a -> Bag a -> Bag a
add Bag a
forall a. Bag a
emptyBag Bag (Maybe a)
bs
  where
    add :: Maybe a -> Bag a -> Bag a
add Nothing rs :: Bag a
rs = Bag a
rs
    add (Just x :: a
x) rs :: Bag a
rs = a
x a -> Bag a -> Bag a
forall a. a -> Bag a -> Bag a
`consBag` Bag a
rs

partitionBag :: (a -> Bool) -> Bag a -> (Bag a {- Satisfy predictate -},
                                         Bag a {- Don't -})
partitionBag :: (a -> Bool) -> Bag a -> (Bag a, Bag a)
partitionBag _    EmptyBag = (Bag a
forall a. Bag a
EmptyBag, Bag a
forall a. Bag a
EmptyBag)
partitionBag pred :: a -> Bool
pred b :: Bag a
b@(UnitBag val :: a
val)
    = if a -> Bool
pred a
val then (Bag a
b, Bag a
forall a. Bag a
EmptyBag) else (Bag a
forall a. Bag a
EmptyBag, Bag a
b)
partitionBag pred :: a -> Bool
pred (TwoBags b1 :: Bag a
b1 b2 :: Bag a
b2)
    = (Bag a
sat1 Bag a -> Bag a -> Bag a
forall a. Bag a -> Bag a -> Bag a
`unionBags` Bag a
sat2, Bag a
fail1 Bag a -> Bag a -> Bag a
forall a. Bag a -> Bag a -> Bag a
`unionBags` Bag a
fail2)
  where (sat1 :: Bag a
sat1, fail1 :: Bag a
fail1) = (a -> Bool) -> Bag a -> (Bag a, Bag a)
forall a. (a -> Bool) -> Bag a -> (Bag a, Bag a)
partitionBag a -> Bool
pred Bag a
b1
        (sat2 :: Bag a
sat2, fail2 :: Bag a
fail2) = (a -> Bool) -> Bag a -> (Bag a, Bag a)
forall a. (a -> Bool) -> Bag a -> (Bag a, Bag a)
partitionBag a -> Bool
pred Bag a
b2
partitionBag pred :: a -> Bool
pred (ListBag vs :: [a]
vs) = ([a] -> Bag a
forall a. [a] -> Bag a
listToBag [a]
sats, [a] -> Bag a
forall a. [a] -> Bag a
listToBag [a]
fails)
  where (sats :: [a]
sats, fails :: [a]
fails) = (a -> Bool) -> [a] -> ([a], [a])
forall a. (a -> Bool) -> [a] -> ([a], [a])
partition a -> Bool
pred [a]
vs


partitionBagWith :: (a -> Either b c) -> Bag a
                    -> (Bag b {- Left  -},
                        Bag c {- Right -})
partitionBagWith :: (a -> Either b c) -> Bag a -> (Bag b, Bag c)
partitionBagWith _    EmptyBag = (Bag b
forall a. Bag a
EmptyBag, Bag c
forall a. Bag a
EmptyBag)
partitionBagWith pred :: a -> Either b c
pred (UnitBag val :: a
val)
    = case a -> Either b c
pred a
val of
         Left a :: b
a  -> (b -> Bag b
forall a. a -> Bag a
UnitBag b
a, Bag c
forall a. Bag a
EmptyBag)
         Right b :: c
b -> (Bag b
forall a. Bag a
EmptyBag, c -> Bag c
forall a. a -> Bag a
UnitBag c
b)
partitionBagWith pred :: a -> Either b c
pred (TwoBags b1 :: Bag a
b1 b2 :: Bag a
b2)
    = (Bag b
sat1 Bag b -> Bag b -> Bag b
forall a. Bag a -> Bag a -> Bag a
`unionBags` Bag b
sat2, Bag c
fail1 Bag c -> Bag c -> Bag c
forall a. Bag a -> Bag a -> Bag a
`unionBags` Bag c
fail2)
  where (sat1 :: Bag b
sat1, fail1 :: Bag c
fail1) = (a -> Either b c) -> Bag a -> (Bag b, Bag c)
forall a b c. (a -> Either b c) -> Bag a -> (Bag b, Bag c)
partitionBagWith a -> Either b c
pred Bag a
b1
        (sat2 :: Bag b
sat2, fail2 :: Bag c
fail2) = (a -> Either b c) -> Bag a -> (Bag b, Bag c)
forall a b c. (a -> Either b c) -> Bag a -> (Bag b, Bag c)
partitionBagWith a -> Either b c
pred Bag a
b2
partitionBagWith pred :: a -> Either b c
pred (ListBag vs :: [a]
vs) = ([b] -> Bag b
forall a. [a] -> Bag a
listToBag [b]
sats, [c] -> Bag c
forall a. [a] -> Bag a
listToBag [c]
fails)
  where (sats :: [b]
sats, fails :: [c]
fails) = (a -> Either b c) -> [a] -> ([b], [c])
forall a b c. (a -> Either b c) -> [a] -> ([b], [c])
partitionWith a -> Either b c
pred [a]
vs

foldBag :: (r -> r -> r) -- Replace TwoBags with this; should be associative
        -> (a -> r)      -- Replace UnitBag with this
        -> r             -- Replace EmptyBag with this
        -> Bag a
        -> r

{- Standard definition
foldBag t u e EmptyBag        = e
foldBag t u e (UnitBag x)     = u x
foldBag t u e (TwoBags b1 b2) = (foldBag t u e b1) `t` (foldBag t u e b2)
foldBag t u e (ListBag xs)    = foldr (t.u) e xs
-}

-- More tail-recursive definition, exploiting associativity of "t"
foldBag :: (r -> r -> r) -> (a -> r) -> r -> Bag a -> r
foldBag _ _ e :: r
e EmptyBag        = r
e
foldBag t :: r -> r -> r
t u :: a -> r
u e :: r
e (UnitBag x :: a
x)     = a -> r
u a
x r -> r -> r
`t` r
e
foldBag t :: r -> r -> r
t u :: a -> r
u e :: r
e (TwoBags b1 :: Bag a
b1 b2 :: Bag a
b2) = (r -> r -> r) -> (a -> r) -> r -> Bag a -> r
forall r a. (r -> r -> r) -> (a -> r) -> r -> Bag a -> r
foldBag r -> r -> r
t a -> r
u ((r -> r -> r) -> (a -> r) -> r -> Bag a -> r
forall r a. (r -> r -> r) -> (a -> r) -> r -> Bag a -> r
foldBag r -> r -> r
t a -> r
u r
e Bag a
b2) Bag a
b1
foldBag t :: r -> r -> r
t u :: a -> r
u e :: r
e (ListBag xs :: [a]
xs)    = (a -> r -> r) -> r -> [a] -> r
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (r -> r -> r
t(r -> r -> r) -> (a -> r) -> a -> r -> r
forall b c a. (b -> c) -> (a -> b) -> a -> c
.a -> r
u) r
e [a]
xs

foldrBag :: (a -> r -> r) -> r
         -> Bag a
         -> r

foldrBag :: (a -> r -> r) -> r -> Bag a -> r
foldrBag _ z :: r
z EmptyBag        = r
z
foldrBag k :: a -> r -> r
k z :: r
z (UnitBag x :: a
x)     = a -> r -> r
k a
x r
z
foldrBag k :: a -> r -> r
k z :: r
z (TwoBags b1 :: Bag a
b1 b2 :: Bag a
b2) = (a -> r -> r) -> r -> Bag a -> r
forall a r. (a -> r -> r) -> r -> Bag a -> r
foldrBag a -> r -> r
k ((a -> r -> r) -> r -> Bag a -> r
forall a r. (a -> r -> r) -> r -> Bag a -> r
foldrBag a -> r -> r
k r
z Bag a
b2) Bag a
b1
foldrBag k :: a -> r -> r
k z :: r
z (ListBag xs :: [a]
xs)    = (a -> r -> r) -> r -> [a] -> r
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> r -> r
k r
z [a]
xs

foldlBag :: (r -> a -> r) -> r
         -> Bag a
         -> r

foldlBag :: (r -> a -> r) -> r -> Bag a -> r
foldlBag _ z :: r
z EmptyBag        = r
z
foldlBag k :: r -> a -> r
k z :: r
z (UnitBag x :: a
x)     = r -> a -> r
k r
z a
x
foldlBag k :: r -> a -> r
k z :: r
z (TwoBags b1 :: Bag a
b1 b2 :: Bag a
b2) = (r -> a -> r) -> r -> Bag a -> r
forall r a. (r -> a -> r) -> r -> Bag a -> r
foldlBag r -> a -> r
k ((r -> a -> r) -> r -> Bag a -> r
forall r a. (r -> a -> r) -> r -> Bag a -> r
foldlBag r -> a -> r
k r
z Bag a
b1) Bag a
b2
foldlBag k :: r -> a -> r
k z :: r
z (ListBag xs :: [a]
xs)    = (r -> a -> r) -> r -> [a] -> r
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl r -> a -> r
k r
z [a]
xs

foldrBagM :: (Monad m) => (a -> b -> m b) -> b -> Bag a -> m b
foldrBagM :: (a -> b -> m b) -> b -> Bag a -> m b
foldrBagM _ z :: b
z EmptyBag        = b -> m b
forall (m :: * -> *) a. Monad m => a -> m a
return b
z
foldrBagM k :: a -> b -> m b
k z :: b
z (UnitBag x :: a
x)     = a -> b -> m b
k a
x b
z
foldrBagM k :: a -> b -> m b
k z :: b
z (TwoBags b1 :: Bag a
b1 b2 :: Bag a
b2) = do { b
z' <- (a -> b -> m b) -> b -> Bag a -> m b
forall (m :: * -> *) a b.
Monad m =>
(a -> b -> m b) -> b -> Bag a -> m b
foldrBagM a -> b -> m b
k b
z Bag a
b2; (a -> b -> m b) -> b -> Bag a -> m b
forall (m :: * -> *) a b.
Monad m =>
(a -> b -> m b) -> b -> Bag a -> m b
foldrBagM a -> b -> m b
k b
z' Bag a
b1 }
foldrBagM k :: a -> b -> m b
k z :: b
z (ListBag xs :: [a]
xs)    = (a -> b -> m b) -> b -> [a] -> m b
forall (m :: * -> *) b a.
Monad m =>
(b -> a -> m a) -> a -> [b] -> m a
foldrM a -> b -> m b
k b
z [a]
xs

foldlBagM :: (Monad m) => (b -> a -> m b) -> b -> Bag a -> m b
foldlBagM :: (b -> a -> m b) -> b -> Bag a -> m b
foldlBagM _ z :: b
z EmptyBag        = b -> m b
forall (m :: * -> *) a. Monad m => a -> m a
return b
z
foldlBagM k :: b -> a -> m b
k z :: b
z (UnitBag x :: a
x)     = b -> a -> m b
k b
z a
x
foldlBagM k :: b -> a -> m b
k z :: b
z (TwoBags b1 :: Bag a
b1 b2 :: Bag a
b2) = do { b
z' <- (b -> a -> m b) -> b -> Bag a -> m b
forall (m :: * -> *) b a.
Monad m =>
(b -> a -> m b) -> b -> Bag a -> m b
foldlBagM b -> a -> m b
k b
z Bag a
b1; (b -> a -> m b) -> b -> Bag a -> m b
forall (m :: * -> *) b a.
Monad m =>
(b -> a -> m b) -> b -> Bag a -> m b
foldlBagM b -> a -> m b
k b
z' Bag a
b2 }
foldlBagM k :: b -> a -> m b
k z :: b
z (ListBag xs :: [a]
xs)    = (b -> a -> m b) -> b -> [a] -> m b
forall (m :: * -> *) a b.
Monad m =>
(a -> b -> m a) -> a -> [b] -> m a
foldlM b -> a -> m b
k b
z [a]
xs

mapBag :: (a -> b) -> Bag a -> Bag b
mapBag :: (a -> b) -> Bag a -> Bag b
mapBag _ EmptyBag        = Bag b
forall a. Bag a
EmptyBag
mapBag f :: a -> b
f (UnitBag x :: a
x)     = b -> Bag b
forall a. a -> Bag a
UnitBag (a -> b
f a
x)
mapBag f :: a -> b
f (TwoBags b1 :: Bag a
b1 b2 :: Bag a
b2) = Bag b -> Bag b -> Bag b
forall a. Bag a -> Bag a -> Bag a
TwoBags ((a -> b) -> Bag a -> Bag b
forall a b. (a -> b) -> Bag a -> Bag b
mapBag a -> b
f Bag a
b1) ((a -> b) -> Bag a -> Bag b
forall a b. (a -> b) -> Bag a -> Bag b
mapBag a -> b
f Bag a
b2)
mapBag f :: a -> b
f (ListBag xs :: [a]
xs)    = [b] -> Bag b
forall a. [a] -> Bag a
ListBag ((a -> b) -> [a] -> [b]
forall a b. (a -> b) -> [a] -> [b]
map a -> b
f [a]
xs)

concatMapBag :: (a -> Bag b) -> Bag a -> Bag b
concatMapBag :: (a -> Bag b) -> Bag a -> Bag b
concatMapBag _ EmptyBag        = Bag b
forall a. Bag a
EmptyBag
concatMapBag f :: a -> Bag b
f (UnitBag x :: a
x)     = a -> Bag b
f a
x
concatMapBag f :: a -> Bag b
f (TwoBags b1 :: Bag a
b1 b2 :: Bag a
b2) = Bag b -> Bag b -> Bag b
forall a. Bag a -> Bag a -> Bag a
unionBags ((a -> Bag b) -> Bag a -> Bag b
forall a b. (a -> Bag b) -> Bag a -> Bag b
concatMapBag a -> Bag b
f Bag a
b1) ((a -> Bag b) -> Bag a -> Bag b
forall a b. (a -> Bag b) -> Bag a -> Bag b
concatMapBag a -> Bag b
f Bag a
b2)
concatMapBag f :: a -> Bag b
f (ListBag xs :: [a]
xs)    = (a -> Bag b -> Bag b) -> Bag b -> [a] -> Bag b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (Bag b -> Bag b -> Bag b
forall a. Bag a -> Bag a -> Bag a
unionBags (Bag b -> Bag b -> Bag b) -> (a -> Bag b) -> a -> Bag b -> Bag b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bag b
f) Bag b
forall a. Bag a
emptyBag [a]
xs

concatMapBagPair :: (a -> (Bag b, Bag c)) -> Bag a -> (Bag b, Bag c)
concatMapBagPair :: (a -> (Bag b, Bag c)) -> Bag a -> (Bag b, Bag c)
concatMapBagPair _ EmptyBag        = (Bag b
forall a. Bag a
EmptyBag, Bag c
forall a. Bag a
EmptyBag)
concatMapBagPair f :: a -> (Bag b, Bag c)
f (UnitBag x :: a
x)     = a -> (Bag b, Bag c)
f a
x
concatMapBagPair f :: a -> (Bag b, Bag c)
f (TwoBags b1 :: Bag a
b1 b2 :: Bag a
b2) = (Bag b -> Bag b -> Bag b
forall a. Bag a -> Bag a -> Bag a
unionBags Bag b
r1 Bag b
r2, Bag c -> Bag c -> Bag c
forall a. Bag a -> Bag a -> Bag a
unionBags Bag c
s1 Bag c
s2)
  where
    (r1 :: Bag b
r1, s1 :: Bag c
s1) = (a -> (Bag b, Bag c)) -> Bag a -> (Bag b, Bag c)
forall a b c. (a -> (Bag b, Bag c)) -> Bag a -> (Bag b, Bag c)
concatMapBagPair a -> (Bag b, Bag c)
f Bag a
b1
    (r2 :: Bag b
r2, s2 :: Bag c
s2) = (a -> (Bag b, Bag c)) -> Bag a -> (Bag b, Bag c)
forall a b c. (a -> (Bag b, Bag c)) -> Bag a -> (Bag b, Bag c)
concatMapBagPair a -> (Bag b, Bag c)
f Bag a
b2
concatMapBagPair f :: a -> (Bag b, Bag c)
f (ListBag xs :: [a]
xs)    = (a -> (Bag b, Bag c) -> (Bag b, Bag c))
-> (Bag b, Bag c) -> [a] -> (Bag b, Bag c)
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> (Bag b, Bag c) -> (Bag b, Bag c)
go (Bag b
forall a. Bag a
emptyBag, Bag c
forall a. Bag a
emptyBag) [a]
xs
  where
    go :: a -> (Bag b, Bag c) -> (Bag b, Bag c)
go a :: a
a (s1 :: Bag b
s1, s2 :: Bag c
s2) = (Bag b -> Bag b -> Bag b
forall a. Bag a -> Bag a -> Bag a
unionBags Bag b
r1 Bag b
s1, Bag c -> Bag c -> Bag c
forall a. Bag a -> Bag a -> Bag a
unionBags Bag c
r2 Bag c
s2)
      where
        (r1 :: Bag b
r1, r2 :: Bag c
r2) = a -> (Bag b, Bag c)
f a
a

mapMaybeBag :: (a -> Maybe b) -> Bag a -> Bag b
mapMaybeBag :: (a -> Maybe b) -> Bag a -> Bag b
mapMaybeBag _ EmptyBag        = Bag b
forall a. Bag a
EmptyBag
mapMaybeBag f :: a -> Maybe b
f (UnitBag x :: a
x)     = case a -> Maybe b
f a
x of
                                  Nothing -> Bag b
forall a. Bag a
EmptyBag
                                  Just y :: b
y  -> b -> Bag b
forall a. a -> Bag a
UnitBag b
y
mapMaybeBag f :: a -> Maybe b
f (TwoBags b1 :: Bag a
b1 b2 :: Bag a
b2) = Bag b -> Bag b -> Bag b
forall a. Bag a -> Bag a -> Bag a
unionBags ((a -> Maybe b) -> Bag a -> Bag b
forall a b. (a -> Maybe b) -> Bag a -> Bag b
mapMaybeBag a -> Maybe b
f Bag a
b1) ((a -> Maybe b) -> Bag a -> Bag b
forall a b. (a -> Maybe b) -> Bag a -> Bag b
mapMaybeBag a -> Maybe b
f Bag a
b2)
mapMaybeBag f :: a -> Maybe b
f (ListBag xs :: [a]
xs)    = [b] -> Bag b
forall a. [a] -> Bag a
ListBag ((a -> Maybe b) -> [a] -> [b]
forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe a -> Maybe b
f [a]
xs)

mapBagM :: Monad m => (a -> m b) -> Bag a -> m (Bag b)
mapBagM :: (a -> m b) -> Bag a -> m (Bag b)
mapBagM _ EmptyBag        = Bag b -> m (Bag b)
forall (m :: * -> *) a. Monad m => a -> m a
return Bag b
forall a. Bag a
EmptyBag
mapBagM f :: a -> m b
f (UnitBag x :: a
x)     = do b
r <- a -> m b
f a
x
                               Bag b -> m (Bag b)
forall (m :: * -> *) a. Monad m => a -> m a
return (b -> Bag b
forall a. a -> Bag a
UnitBag b
r)
mapBagM f :: a -> m b
f (TwoBags b1 :: Bag a
b1 b2 :: Bag a
b2) = do Bag b
r1 <- (a -> m b) -> Bag a -> m (Bag b)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Bag a -> m (Bag b)
mapBagM a -> m b
f Bag a
b1
                               Bag b
r2 <- (a -> m b) -> Bag a -> m (Bag b)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Bag a -> m (Bag b)
mapBagM a -> m b
f Bag a
b2
                               Bag b -> m (Bag b)
forall (m :: * -> *) a. Monad m => a -> m a
return (Bag b -> Bag b -> Bag b
forall a. Bag a -> Bag a -> Bag a
TwoBags Bag b
r1 Bag b
r2)
mapBagM f :: a -> m b
f (ListBag    xs :: [a]
xs) = do [b]
rs <- (a -> m b) -> [a] -> m [b]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM a -> m b
f [a]
xs
                               Bag b -> m (Bag b)
forall (m :: * -> *) a. Monad m => a -> m a
return ([b] -> Bag b
forall a. [a] -> Bag a
ListBag [b]
rs)

mapBagM_ :: Monad m => (a -> m b) -> Bag a -> m ()
mapBagM_ :: (a -> m b) -> Bag a -> m ()
mapBagM_ _ EmptyBag        = () -> m ()
forall (m :: * -> *) a. Monad m => a -> m a
return ()
mapBagM_ f :: a -> m b
f (UnitBag x :: a
x)     = a -> m b
f a
x m b -> m () -> m ()
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> () -> m ()
forall (m :: * -> *) a. Monad m => a -> m a
return ()
mapBagM_ f :: a -> m b
f (TwoBags b1 :: Bag a
b1 b2 :: Bag a
b2) = (a -> m b) -> Bag a -> m ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> Bag a -> m ()
mapBagM_ a -> m b
f Bag a
b1 m () -> m () -> m ()
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> (a -> m b) -> Bag a -> m ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> Bag a -> m ()
mapBagM_ a -> m b
f Bag a
b2
mapBagM_ f :: a -> m b
f (ListBag    xs :: [a]
xs) = (a -> m b) -> [a] -> m ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
(a -> m b) -> t a -> m ()
mapM_ a -> m b
f [a]
xs

flatMapBagM :: Monad m => (a -> m (Bag b)) -> Bag a -> m (Bag b)
flatMapBagM :: (a -> m (Bag b)) -> Bag a -> m (Bag b)
flatMapBagM _ EmptyBag        = Bag b -> m (Bag b)
forall (m :: * -> *) a. Monad m => a -> m a
return Bag b
forall a. Bag a
EmptyBag
flatMapBagM f :: a -> m (Bag b)
f (UnitBag x :: a
x)     = a -> m (Bag b)
f a
x
flatMapBagM f :: a -> m (Bag b)
f (TwoBags b1 :: Bag a
b1 b2 :: Bag a
b2) = do Bag b
r1 <- (a -> m (Bag b)) -> Bag a -> m (Bag b)
forall (m :: * -> *) a b.
Monad m =>
(a -> m (Bag b)) -> Bag a -> m (Bag b)
flatMapBagM a -> m (Bag b)
f Bag a
b1
                                   Bag b
r2 <- (a -> m (Bag b)) -> Bag a -> m (Bag b)
forall (m :: * -> *) a b.
Monad m =>
(a -> m (Bag b)) -> Bag a -> m (Bag b)
flatMapBagM a -> m (Bag b)
f Bag a
b2
                                   Bag b -> m (Bag b)
forall (m :: * -> *) a. Monad m => a -> m a
return (Bag b
r1 Bag b -> Bag b -> Bag b
forall a. Bag a -> Bag a -> Bag a
`unionBags` Bag b
r2)
flatMapBagM f :: a -> m (Bag b)
f (ListBag    xs :: [a]
xs) = (a -> Bag b -> m (Bag b)) -> Bag b -> [a] -> m (Bag b)
forall (m :: * -> *) b a.
Monad m =>
(b -> a -> m a) -> a -> [b] -> m a
foldrM a -> Bag b -> m (Bag b)
k Bag b
forall a. Bag a
EmptyBag [a]
xs
  where
    k :: a -> Bag b -> m (Bag b)
k x :: a
x b2 :: Bag b
b2 = do { Bag b
b1 <- a -> m (Bag b)
f a
x; Bag b -> m (Bag b)
forall (m :: * -> *) a. Monad m => a -> m a
return (Bag b
b1 Bag b -> Bag b -> Bag b
forall a. Bag a -> Bag a -> Bag a
`unionBags` Bag b
b2) }

flatMapBagPairM :: Monad m => (a -> m (Bag b, Bag c)) -> Bag a -> m (Bag b, Bag c)
flatMapBagPairM :: (a -> m (Bag b, Bag c)) -> Bag a -> m (Bag b, Bag c)
flatMapBagPairM _ EmptyBag        = (Bag b, Bag c) -> m (Bag b, Bag c)
forall (m :: * -> *) a. Monad m => a -> m a
return (Bag b
forall a. Bag a
EmptyBag, Bag c
forall a. Bag a
EmptyBag)
flatMapBagPairM f :: a -> m (Bag b, Bag c)
f (UnitBag x :: a
x)     = a -> m (Bag b, Bag c)
f a
x
flatMapBagPairM f :: a -> m (Bag b, Bag c)
f (TwoBags b1 :: Bag a
b1 b2 :: Bag a
b2) = do (r1 :: Bag b
r1,s1 :: Bag c
s1) <- (a -> m (Bag b, Bag c)) -> Bag a -> m (Bag b, Bag c)
forall (m :: * -> *) a b c.
Monad m =>
(a -> m (Bag b, Bag c)) -> Bag a -> m (Bag b, Bag c)
flatMapBagPairM a -> m (Bag b, Bag c)
f Bag a
b1
                                       (r2 :: Bag b
r2,s2 :: Bag c
s2) <- (a -> m (Bag b, Bag c)) -> Bag a -> m (Bag b, Bag c)
forall (m :: * -> *) a b c.
Monad m =>
(a -> m (Bag b, Bag c)) -> Bag a -> m (Bag b, Bag c)
flatMapBagPairM a -> m (Bag b, Bag c)
f Bag a
b2
                                       (Bag b, Bag c) -> m (Bag b, Bag c)
forall (m :: * -> *) a. Monad m => a -> m a
return (Bag b
r1 Bag b -> Bag b -> Bag b
forall a. Bag a -> Bag a -> Bag a
`unionBags` Bag b
r2, Bag c
s1 Bag c -> Bag c -> Bag c
forall a. Bag a -> Bag a -> Bag a
`unionBags` Bag c
s2)
flatMapBagPairM f :: a -> m (Bag b, Bag c)
f (ListBag    xs :: [a]
xs) = (a -> (Bag b, Bag c) -> m (Bag b, Bag c))
-> (Bag b, Bag c) -> [a] -> m (Bag b, Bag c)
forall (m :: * -> *) b a.
Monad m =>
(b -> a -> m a) -> a -> [b] -> m a
foldrM a -> (Bag b, Bag c) -> m (Bag b, Bag c)
k (Bag b
forall a. Bag a
EmptyBag, Bag c
forall a. Bag a
EmptyBag) [a]
xs
  where
    k :: a -> (Bag b, Bag c) -> m (Bag b, Bag c)
k x :: a
x (r2 :: Bag b
r2,s2 :: Bag c
s2) = do { (r1 :: Bag b
r1,s1 :: Bag c
s1) <- a -> m (Bag b, Bag c)
f a
x
                     ; (Bag b, Bag c) -> m (Bag b, Bag c)
forall (m :: * -> *) a. Monad m => a -> m a
return (Bag b
r1 Bag b -> Bag b -> Bag b
forall a. Bag a -> Bag a -> Bag a
`unionBags` Bag b
r2, Bag c
s1 Bag c -> Bag c -> Bag c
forall a. Bag a -> Bag a -> Bag a
`unionBags` Bag c
s2) }

mapAndUnzipBagM :: Monad m => (a -> m (b,c)) -> Bag a -> m (Bag b, Bag c)
mapAndUnzipBagM :: (a -> m (b, c)) -> Bag a -> m (Bag b, Bag c)
mapAndUnzipBagM _ EmptyBag        = (Bag b, Bag c) -> m (Bag b, Bag c)
forall (m :: * -> *) a. Monad m => a -> m a
return (Bag b
forall a. Bag a
EmptyBag, Bag c
forall a. Bag a
EmptyBag)
mapAndUnzipBagM f :: a -> m (b, c)
f (UnitBag x :: a
x)     = do (r :: b
r,s :: c
s) <- a -> m (b, c)
f a
x
                                       (Bag b, Bag c) -> m (Bag b, Bag c)
forall (m :: * -> *) a. Monad m => a -> m a
return (b -> Bag b
forall a. a -> Bag a
UnitBag b
r, c -> Bag c
forall a. a -> Bag a
UnitBag c
s)
mapAndUnzipBagM f :: a -> m (b, c)
f (TwoBags b1 :: Bag a
b1 b2 :: Bag a
b2) = do (r1 :: Bag b
r1,s1 :: Bag c
s1) <- (a -> m (b, c)) -> Bag a -> m (Bag b, Bag c)
forall (m :: * -> *) a b c.
Monad m =>
(a -> m (b, c)) -> Bag a -> m (Bag b, Bag c)
mapAndUnzipBagM a -> m (b, c)
f Bag a
b1
                                       (r2 :: Bag b
r2,s2 :: Bag c
s2) <- (a -> m (b, c)) -> Bag a -> m (Bag b, Bag c)
forall (m :: * -> *) a b c.
Monad m =>
(a -> m (b, c)) -> Bag a -> m (Bag b, Bag c)
mapAndUnzipBagM a -> m (b, c)
f Bag a
b2
                                       (Bag b, Bag c) -> m (Bag b, Bag c)
forall (m :: * -> *) a. Monad m => a -> m a
return (Bag b -> Bag b -> Bag b
forall a. Bag a -> Bag a -> Bag a
TwoBags Bag b
r1 Bag b
r2, Bag c -> Bag c -> Bag c
forall a. Bag a -> Bag a -> Bag a
TwoBags Bag c
s1 Bag c
s2)
mapAndUnzipBagM f :: a -> m (b, c)
f (ListBag xs :: [a]
xs)    = do [(b, c)]
ts <- (a -> m (b, c)) -> [a] -> m [(b, c)]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM a -> m (b, c)
f [a]
xs
                                       let (rs :: [b]
rs,ss :: [c]
ss) = [(b, c)] -> ([b], [c])
forall a b. [(a, b)] -> ([a], [b])
unzip [(b, c)]
ts
                                       (Bag b, Bag c) -> m (Bag b, Bag c)
forall (m :: * -> *) a. Monad m => a -> m a
return ([b] -> Bag b
forall a. [a] -> Bag a
ListBag [b]
rs, [c] -> Bag c
forall a. [a] -> Bag a
ListBag [c]
ss)

mapAccumBagL ::(acc -> x -> (acc, y)) -- ^ combining function
            -> acc                    -- ^ initial state
            -> Bag x                  -- ^ inputs
            -> (acc, Bag y)           -- ^ final state, outputs
mapAccumBagL :: (acc -> x -> (acc, y)) -> acc -> Bag x -> (acc, Bag y)
mapAccumBagL _ s :: acc
s EmptyBag        = (acc
s, Bag y
forall a. Bag a
EmptyBag)
mapAccumBagL f :: acc -> x -> (acc, y)
f s :: acc
s (UnitBag x :: x
x)     = let (s1 :: acc
s1, x1 :: y
x1) = acc -> x -> (acc, y)
f acc
s x
x in (acc
s1, y -> Bag y
forall a. a -> Bag a
UnitBag y
x1)
mapAccumBagL f :: acc -> x -> (acc, y)
f s :: acc
s (TwoBags b1 :: Bag x
b1 b2 :: Bag x
b2) = let (s1 :: acc
s1, b1' :: Bag y
b1') = (acc -> x -> (acc, y)) -> acc -> Bag x -> (acc, Bag y)
forall acc x y.
(acc -> x -> (acc, y)) -> acc -> Bag x -> (acc, Bag y)
mapAccumBagL acc -> x -> (acc, y)
f acc
s  Bag x
b1
                                       (s2 :: acc
s2, b2' :: Bag y
b2') = (acc -> x -> (acc, y)) -> acc -> Bag x -> (acc, Bag y)
forall acc x y.
(acc -> x -> (acc, y)) -> acc -> Bag x -> (acc, Bag y)
mapAccumBagL acc -> x -> (acc, y)
f acc
s1 Bag x
b2
                                   in (acc
s2, Bag y -> Bag y -> Bag y
forall a. Bag a -> Bag a -> Bag a
TwoBags Bag y
b1' Bag y
b2')
mapAccumBagL f :: acc -> x -> (acc, y)
f s :: acc
s (ListBag xs :: [x]
xs)    = let (s' :: acc
s', xs' :: [y]
xs') = (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])
forall (t :: * -> *) a b c.
Traversable t =>
(a -> b -> (a, c)) -> a -> t b -> (a, t c)
mapAccumL acc -> x -> (acc, y)
f acc
s [x]
xs
                                   in (acc
s', [y] -> Bag y
forall a. [a] -> Bag a
ListBag [y]
xs')

mapAccumBagLM :: Monad m
            => (acc -> x -> m (acc, y)) -- ^ combining function
            -> acc                      -- ^ initial state
            -> Bag x                    -- ^ inputs
            -> m (acc, Bag y)           -- ^ final state, outputs
mapAccumBagLM :: (acc -> x -> m (acc, y)) -> acc -> Bag x -> m (acc, Bag y)
mapAccumBagLM _ s :: acc
s EmptyBag        = (acc, Bag y) -> m (acc, Bag y)
forall (m :: * -> *) a. Monad m => a -> m a
return (acc
s, Bag y
forall a. Bag a
EmptyBag)
mapAccumBagLM f :: acc -> x -> m (acc, y)
f s :: acc
s (UnitBag x :: x
x)     = do { (s1 :: acc
s1, x1 :: y
x1) <- acc -> x -> m (acc, y)
f acc
s x
x; (acc, Bag y) -> m (acc, Bag y)
forall (m :: * -> *) a. Monad m => a -> m a
return (acc
s1, y -> Bag y
forall a. a -> Bag a
UnitBag y
x1) }
mapAccumBagLM f :: acc -> x -> m (acc, y)
f s :: acc
s (TwoBags b1 :: Bag x
b1 b2 :: Bag x
b2) = do { (s1 :: acc
s1, b1' :: Bag y
b1') <- (acc -> x -> m (acc, y)) -> acc -> Bag x -> m (acc, Bag y)
forall (m :: * -> *) acc x y.
Monad m =>
(acc -> x -> m (acc, y)) -> acc -> Bag x -> m (acc, Bag y)
mapAccumBagLM acc -> x -> m (acc, y)
f acc
s  Bag x
b1
                                       ; (s2 :: acc
s2, b2' :: Bag y
b2') <- (acc -> x -> m (acc, y)) -> acc -> Bag x -> m (acc, Bag y)
forall (m :: * -> *) acc x y.
Monad m =>
(acc -> x -> m (acc, y)) -> acc -> Bag x -> m (acc, Bag y)
mapAccumBagLM acc -> x -> m (acc, y)
f acc
s1 Bag x
b2
                                       ; (acc, Bag y) -> m (acc, Bag y)
forall (m :: * -> *) a. Monad m => a -> m a
return (acc
s2, Bag y -> Bag y -> Bag y
forall a. Bag a -> Bag a -> Bag a
TwoBags Bag y
b1' Bag y
b2') }
mapAccumBagLM f :: acc -> x -> m (acc, y)
f s :: acc
s (ListBag xs :: [x]
xs)    = do { (s' :: acc
s', xs' :: [y]
xs') <- (acc -> x -> m (acc, y)) -> acc -> [x] -> m (acc, [y])
forall (m :: * -> *) acc x y.
Monad m =>
(acc -> x -> m (acc, y)) -> acc -> [x] -> m (acc, [y])
mapAccumLM acc -> x -> m (acc, y)
f acc
s [x]
xs
                                       ; (acc, Bag y) -> m (acc, Bag y)
forall (m :: * -> *) a. Monad m => a -> m a
return (acc
s', [y] -> Bag y
forall a. [a] -> Bag a
ListBag [y]
xs') }

listToBag :: [a] -> Bag a
listToBag :: [a] -> Bag a
listToBag [] = Bag a
forall a. Bag a
EmptyBag
listToBag [x :: a
x] = a -> Bag a
forall a. a -> Bag a
UnitBag a
x
listToBag vs :: [a]
vs = [a] -> Bag a
forall a. [a] -> Bag a
ListBag [a]
vs

bagToList :: Bag a -> [a]
bagToList :: Bag a -> [a]
bagToList b :: Bag a
b = (a -> [a] -> [a]) -> [a] -> Bag a -> [a]
forall a r. (a -> r -> r) -> r -> Bag a -> r
foldrBag (:) [] Bag a
b

instance (Outputable a) => Outputable (Bag a) where
    ppr :: Bag a -> SDoc
ppr bag :: Bag a
bag = SDoc -> SDoc
braces ((a -> SDoc) -> [a] -> SDoc
forall a. (a -> SDoc) -> [a] -> SDoc
pprWithCommas a -> SDoc
forall a. Outputable a => a -> SDoc
ppr (Bag a -> [a]
forall a. Bag a -> [a]
bagToList Bag a
bag))

instance Data a => Data (Bag a) where
  gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Bag a -> c (Bag a)
gfoldl k :: forall d b. Data d => c (d -> b) -> d -> c b
k z :: forall g. g -> c g
z b :: Bag a
b = ([a] -> Bag a) -> c ([a] -> Bag a)
forall g. g -> c g
z [a] -> Bag a
forall a. [a] -> Bag a
listToBag c ([a] -> Bag a) -> [a] -> c (Bag a)
forall d b. Data d => c (d -> b) -> d -> c b
`k` Bag a -> [a]
forall a. Bag a -> [a]
bagToList Bag a
b -- traverse abstract type abstractly
  toConstr :: Bag a -> Constr
toConstr _   = String -> Constr
abstractConstr (String -> Constr) -> String -> Constr
forall a b. (a -> b) -> a -> b
$ "Bag("String -> String -> String
forall a. [a] -> [a] -> [a]
++TypeRep -> String
forall a. Show a => a -> String
show (a -> TypeRep
forall a. Typeable a => a -> TypeRep
typeOf (a
forall a. HasCallStack => a
undefined::a))String -> String -> String
forall a. [a] -> [a] -> [a]
++")"
  gunfold :: (forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Bag a)
gunfold _ _  = String -> Constr -> c (Bag a)
forall a. HasCallStack => String -> a
error "gunfold"
  dataTypeOf :: Bag a -> DataType
dataTypeOf _ = String -> DataType
mkNoRepType "Bag"
  dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c (Bag a))
dataCast1 x :: forall d. Data d => c (t d)
x  = c (t a) -> Maybe (c (Bag a))
forall k1 k2 (c :: k1 -> *) (t :: k2 -> k1) (t' :: k2 -> k1)
       (a :: k2).
(Typeable t, Typeable t') =>
c (t a) -> Maybe (c (t' a))
gcast1 c (t a)
forall d. Data d => c (t d)
x

instance Functor Bag where
    fmap :: (a -> b) -> Bag a -> Bag b
fmap = (a -> b) -> Bag a -> Bag b
forall a b. (a -> b) -> Bag a -> Bag b
mapBag

instance Foldable.Foldable Bag where
    foldr :: (a -> b -> b) -> b -> Bag a -> b
foldr = (a -> b -> b) -> b -> Bag a -> b
forall a r. (a -> r -> r) -> r -> Bag a -> r
foldrBag