{-# LANGUAGE DeriveTraversable #-}
module Data.Bag where


-- | An ordered sequence that can be folded over.
data Bag a = BZero | BOne a | BTwo (Bag a) (Bag a) | BList [Bag a]
  deriving (Int -> Bag a -> ShowS
[Bag a] -> ShowS
Bag a -> String
(Int -> Bag a -> ShowS)
-> (Bag a -> String) -> ([Bag a] -> ShowS) -> Show (Bag a)
forall a. Show a => Int -> Bag a -> ShowS
forall a. Show a => [Bag a] -> ShowS
forall a. Show a => Bag a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall a. Show a => Int -> Bag a -> ShowS
showsPrec :: Int -> Bag a -> ShowS
$cshow :: forall a. Show a => Bag a -> String
show :: Bag a -> String
$cshowList :: forall a. Show a => [Bag a] -> ShowS
showList :: [Bag a] -> ShowS
Show, (forall a b. (a -> b) -> Bag a -> Bag b)
-> (forall a b. a -> Bag b -> Bag a) -> Functor Bag
forall a b. a -> Bag b -> Bag a
forall a b. (a -> b) -> Bag a -> Bag b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall a b. (a -> b) -> Bag a -> Bag b
fmap :: forall a b. (a -> b) -> Bag a -> Bag b
$c<$ :: forall a b. a -> Bag b -> Bag a
<$ :: forall a b. a -> Bag b -> Bag a
Functor, (forall m. Monoid m => Bag m -> m)
-> (forall m a. Monoid m => (a -> m) -> Bag a -> m)
-> (forall m a. Monoid m => (a -> m) -> Bag a -> m)
-> (forall a b. (a -> b -> b) -> b -> Bag a -> b)
-> (forall a b. (a -> b -> b) -> b -> Bag a -> b)
-> (forall b a. (b -> a -> b) -> b -> Bag a -> b)
-> (forall b a. (b -> a -> b) -> b -> Bag a -> b)
-> (forall a. (a -> a -> a) -> Bag a -> a)
-> (forall a. (a -> a -> a) -> Bag a -> a)
-> (forall a. Bag a -> [a])
-> (forall a. Bag a -> Bool)
-> (forall a. Bag a -> Int)
-> (forall a. Eq a => a -> Bag a -> Bool)
-> (forall a. Ord a => Bag a -> a)
-> (forall a. Ord a => Bag a -> a)
-> (forall a. Num a => Bag a -> a)
-> (forall a. Num a => Bag a -> a)
-> Foldable Bag
forall a. Eq a => a -> Bag a -> Bool
forall a. Num a => Bag a -> a
forall a. Ord a => Bag a -> a
forall m. Monoid m => Bag m -> m
forall a. Bag a -> Bool
forall a. Bag a -> Int
forall a. Bag a -> [a]
forall a. (a -> a -> a) -> Bag a -> a
forall m a. Monoid m => (a -> m) -> Bag a -> m
forall b a. (b -> a -> b) -> b -> Bag a -> b
forall a b. (a -> b -> b) -> b -> Bag a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
$cfold :: forall m. Monoid m => Bag m -> m
fold :: forall m. Monoid m => Bag m -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> Bag a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> Bag a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> Bag a -> m
foldMap' :: forall m a. Monoid m => (a -> m) -> Bag a -> m
$cfoldr :: forall a b. (a -> b -> b) -> b -> Bag a -> b
foldr :: forall a b. (a -> b -> b) -> b -> Bag a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> Bag a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> Bag a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> Bag a -> b
foldl :: forall b a. (b -> a -> b) -> b -> Bag a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> Bag a -> b
foldl' :: forall b a. (b -> a -> b) -> b -> Bag a -> b
$cfoldr1 :: forall a. (a -> a -> a) -> Bag a -> a
foldr1 :: forall a. (a -> a -> a) -> Bag a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> Bag a -> a
foldl1 :: forall a. (a -> a -> a) -> Bag a -> a
$ctoList :: forall a. Bag a -> [a]
toList :: forall a. Bag a -> [a]
$cnull :: forall a. Bag a -> Bool
null :: forall a. Bag a -> Bool
$clength :: forall a. Bag a -> Int
length :: forall a. Bag a -> Int
$celem :: forall a. Eq a => a -> Bag a -> Bool
elem :: forall a. Eq a => a -> Bag a -> Bool
$cmaximum :: forall a. Ord a => Bag a -> a
maximum :: forall a. Ord a => Bag a -> a
$cminimum :: forall a. Ord a => Bag a -> a
minimum :: forall a. Ord a => Bag a -> a
$csum :: forall a. Num a => Bag a -> a
sum :: forall a. Num a => Bag a -> a
$cproduct :: forall a. Num a => Bag a -> a
product :: forall a. Num a => Bag a -> a
Foldable, Functor Bag
Foldable Bag
(Functor Bag, Foldable Bag) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> Bag a -> f (Bag b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    Bag (f a) -> f (Bag a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> Bag a -> m (Bag b))
-> (forall (m :: * -> *) a. Monad m => Bag (m a) -> m (Bag a))
-> Traversable Bag
forall (t :: * -> *).
(Functor t, Foldable t) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a. Monad m => Bag (m a) -> m (Bag a)
forall (f :: * -> *) a. Applicative f => Bag (f a) -> f (Bag a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Bag a -> m (Bag b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Bag a -> f (Bag b)
$ctraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Bag a -> f (Bag b)
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Bag a -> f (Bag b)
$csequenceA :: forall (f :: * -> *) a. Applicative f => Bag (f a) -> f (Bag a)
sequenceA :: forall (f :: * -> *) a. Applicative f => Bag (f a) -> f (Bag a)
$cmapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Bag a -> m (Bag b)
mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Bag a -> m (Bag b)
$csequence :: forall (m :: * -> *) a. Monad m => Bag (m a) -> m (Bag a)
sequence :: forall (m :: * -> *) a. Monad m => Bag (m a) -> m (Bag a)
Traversable)

-- Really only here for 'pure'
instance Applicative Bag where
  pure :: forall a. a -> Bag a
pure = a -> Bag a
forall a. a -> Bag a
BOne
  Bag (a -> b)
BZero <*> :: forall a b. Bag (a -> b) -> Bag a -> Bag b
<*> Bag a
_ = Bag b
forall a. Bag a
BZero
  BOne a -> b
f <*> Bag a
t = a -> b
f (a -> b) -> Bag a -> Bag b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Bag a
t
  BTwo Bag (a -> b)
f1 Bag (a -> b)
f2 <*> Bag a
t = Bag b -> Bag b -> Bag b
forall a. Bag a -> Bag a -> Bag a
BTwo (Bag (a -> b)
f1 Bag (a -> b) -> Bag a -> Bag b
forall a b. Bag (a -> b) -> Bag a -> Bag b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Bag a
t) (Bag (a -> b)
f2 Bag (a -> b) -> Bag a -> Bag b
forall a b. Bag (a -> b) -> Bag a -> Bag b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Bag a
t)
  BList [Bag (a -> b)]
fs <*> Bag a
t = [Bag b] -> Bag b
forall a. [Bag a] -> Bag a
BList [Bag (a -> b)
f Bag (a -> b) -> Bag a -> Bag b
forall a b. Bag (a -> b) -> Bag a -> Bag b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Bag a
t | Bag (a -> b)
f <- [Bag (a -> b)]
fs]

instance Semigroup (Bag a) where <> :: Bag a -> Bag a -> Bag a
(<>) = Bag a -> Bag a -> Bag a
forall a. Bag a -> Bag a -> Bag a
BTwo
instance Monoid (Bag a) where mempty :: Bag a
mempty = Bag a
forall a. Bag a
BZero