Bags
> module Bag ( Bag(..),
> -- construction
> empty, singleton, union, unionMany,
> add, addMany,
> -- modification
> --intersect, minus,
> delete, deleteMany,
> -- map, partition, filter, foldl, foldr,
> -- conversion
> toList, fromList,
> -- size
> lengthBag, --genericLength,
> -- testing
> --null
> --isSingleton, intersecting, isSubsetOf,
> bagElem
> -- substitution
> --replaceMaybe, substitute
> )
> where
> import OrdAssList ( FM(..),
> empty, singleton,
> union_C, add_C, addMany_C,
> delete, deleteMany,
> toList, fromList, indicesFM, elemsFM,
> lookupWithDefault )
> renaming
> ( singleton to singletonFM )
Type definitions
> type Bag a = FM a Int
Construction
Note: empty needs no redefinition.
> --empty :: Bag a
> singleton :: a -> Bag a
> singleton a = singletonFM (a, 1)
> union :: Ord a => Bag a -> Bag a -> Bag a
> union = union_C (+)
> unionMany :: Ord a => [Bag a] -> Bag a
> unionMany = foldl union empty
> add :: Ord a => a -> Bag a -> Bag a
> add a = add_C (+) (a, 1)
> addMany :: Ord a => [a] -> Bag a -> Bag a
> addMany as = addMany_C (+) [ (a, 1) | a<-as ]
Modification
> --intersect :: Ord a => Bag a -> Bag a -> Bag a
Note: delete and deleteMany need no redefinition.
> --delete :: Ord a => a -> Bag a -> Bag a
> --deleteMany :: Ord a => Bag a -> [a] -> Bag a
> --minus :: Ord a => Bag a -> Bag a -> Bag a
> --map :: (a -> b) -> Bag a -> Bag a
> --partition :: (a -> Bool) -> Bag a -> (Bag a, Bag a)
> --foldl :: (a -> b -> a) -> a -> Bag b -> a
> --foldr :: (a -> b -> b) -> b -> Bag a -> b
Conversion
Note: toList and fromList need no redefinition.
> --toList :: Bag a -> [(a, Int)]
> --fromList :: Ord a => [(a, Int)] -> Bag a
Size
Note: lengthBag instead of length.
> lengthBag :: Bag a -> Int
> lengthBag = sum . elemsFM
> --genericLength :: Integral i => Bag a -> i
Testing
> --null :: Bag a -> Bool
> --isSingleton :: Bag a -> Bool
> --intersecting :: Ord a => Bag a -> Bag a -> Bool
> --isSubsetOf :: Ord a => Bag a -> Bag a -> Bool
Note: bagElem instead of elem.
> bagElem :: Ord a => a -> Bag a -> Int
> e `bagElem` s = lookupWithDefault s 0 e
Substitution
> --replaceMaybe :: Ord a => (a -> Maybe a) -> Bag a -> Bag a
> --substitute :: Ord a => a -> a -> Bag a -> Bag a