module Bag_Sol (Bag, empty, null, fromList, insert, union, diff, isSubbag, count) where

import Prelude hiding (null)
import qualified Data.Map as M

{-H12.3-}

newtype Bag a = Bag (M.Map a Integer)

empty :: Bag a
empty = Bag M.empty

insert :: Ord a => a -> Bag a -> Bag a
insert x = union (fromList [x])

union :: Ord a => Bag a -> Bag a -> Bag a
union (Bag m) (Bag n) = Bag $ M.unionWith (+) m n

diff :: Ord a => Bag a -> Bag a -> Bag a
diff (Bag m) (Bag n) = Bag $ M.differenceWith f m n
  where f x y = if y < x then Just (x - y) else Nothing

isSubbag :: Ord a => Bag a -> Bag a -> Bool
isSubbag (Bag m) (Bag n) = M.isSubmapOfBy (<=) m n

count :: Ord a => a -> Bag a -> Integer
count x (Bag m) = maybe 0 id $ M.lookup x m


-- nicht von Aufgabenstellung gefordert, aber trotzdem praktische Funktionen
null :: Bag a -> Bool
null (Bag m) = M.null m

fromList :: Ord a => [a] -> Bag a
fromList = Bag . M.unionsWith (+) . map single
  where single c = M.singleton c 1