1 files changed, 13 insertions, 0 deletions
diff --git a/src/Data.hs b/src/Data.hs
index 1371902..fc39814 100644
--- a/src/Data.hs
+++ b/src/Data.hs
@@ -111,3 +111,16 @@ vecGenerate = \n f -> go n f SZ
 
 unsafeCoerceRefl :: a :~: b
 unsafeCoerceRefl = unsafeCoerce Refl
+
+data Bag t = BNone | BOne t | BTwo (Bag t) (Bag t) | BMany [Bag t]
+  deriving (Show, Functor, Foldable, Traversable)
+
+instance Applicative Bag where
+  pure = BOne
+  BNone <*> _ = BNone
+  BOne f <*> b = f <$> b
+  BTwo b1 b2 <*> b = BTwo (b1 <*> b) (b2 <*> b)
+  BMany bs <*> b = BMany (map (<*> b) bs)
+
+instance Semigroup (Bag t) where (<>) = BTwo
+instance Monoid (Bag t) where mempty = BNone