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


data Bag a
  = BTwo (Bag a) (Bag a)
  | BOne a
  | BZero
  deriving (Functor, Foldable, Traversable)

instance Semigroup (Bag a) where (<>) = BTwo
instance Monoid (Bag a) where mempty = BZero

instance Applicative Bag where
  pure = BOne

  BZero <*> _ = BZero
  _ <*> BZero = BZero
  BOne f <*> b = f <$> b
  BTwo b1 b2 <*> b = BTwo (b1 <*> b) (b2 <*> b)