1 files changed, 20 insertions, 0 deletions
diff --git a/src/Data/Bag.hs b/src/Data/Bag.hs
new file mode 100644
index 0000000..9cdce89
--- /dev/null
+++ b/src/Data/Bag.hs
@@ -0,0 +1,20 @@
+{-# 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)