multiset 0.1 → 0.3.4.3
raw patch · 8 files changed
Files
- CHANGELOG +28/−0
- Data/IntMultiSet.hs +121/−68
- Data/MultiSet.hs +148/−56
- LICENSE +1/−1
- include/Typeable.h +25/−59
- multiset.cabal +48/−9
- test/Main.hs +5/−0
- test/multiset-properties.hs +19/−0
+ CHANGELOG view
@@ -0,0 +1,28 @@+0.3.4.3 (2019-12-15)+ * #39: Improve Foldable instance++0.3.4.2 (2018-11-21)+ * #38: Fix stimes++0.3.4.1 (2018-09-23)+ * Add support for containers-0.6.0.1 (shipped with GHC 8.6.1)++0.3.4 (2018-05-28)+ * #29: Add Semigroup instances (needed for GHC 8.4)+ * Add NfData instances++0.3.3 (2016-05-30)+ * Document precondition of occurrence > 0 on from*List functions.+ * #18: Compatibility with GHC 8.0+ * #13: Fix warnings about redundant imports+ * #22: Fixed warnings about unnecessary constraints++0.3.2: (2016-01-12)+ * #7: Work around doctest issue of ambiguous modules++0.3.1: (2016-01-11)+ * #4: Fix maxView to use deleteFindMax instead of deleteFindMin++0.3.0: (2015-06-29)+ * #3: Return Maybe instead of `fail`-ing in a monad +
Data/IntMultiSet.hs view
@@ -1,3 +1,7 @@+{-# LANGUAGE CPP #-}+#if __GLASGOW_HASKELL__+{-# LANGUAGE DeriveDataTypeable, StandaloneDeriving #-}+#endif ----------------------------------------------------------------------------- -- | -- Module : Data.IntMultiSet@@ -7,17 +11,17 @@ -- Stability : provisional -- Portability : portable ----- An efficient implementation of multisets of integers, also somtimes called bags.+-- An efficient implementation of multisets of integers, also sometimes called bags. -- -- A multiset is like a set, but it can contain multiple copies of the same element. -- -- Since many function names (but not the type name) clash with -- "Prelude" names, this module is usually imported @qualified@, e.g. ----- > import Data.MultiSet (MultiSet)--- > import qualified Data.MultiSet as MultiSet+-- > import Data.IntMultiSet (IntMultiSet)+-- > import qualified Data.IntMultiSet as IntMultiSet ----- The implementation of 'MultiSet' is based on the "Data.IntMap" module.+-- The implementation of 'IntMultiSet' is based on the "Data.IntMap" module. -- -- Many operations have a worst-case complexity of /O(min(n,W))/. -- This means that the operation can become linear in the number of@@ -54,6 +58,7 @@ -- * Combine , union, unions+ , maxUnion , difference , intersection @@ -126,15 +131,27 @@ ) where import Prelude hiding (filter,foldr,null,map,concatMap)+#if __GLASGOW_HASKELL__ < 710 import Data.Monoid (Monoid(..))+#endif+#if MIN_VERSION_base(4,9,0)+import qualified Data.List.NonEmpty (toList)+import Data.Semigroup (Semigroup(..))+#endif import Data.Typeable ()-import Data.IntMap (IntMap)+import Data.IntMap.Strict (IntMap) import Data.IntSet (IntSet) import Data.MultiSet (MultiSet)-import qualified Data.IntMap as Map+#if MIN_VERSION_containers(0,5,11)+import qualified Data.IntMap.Strict as Map hiding (showTreeWith)+import qualified Data.IntMap.Internal.Debug as Map (showTreeWith)+#else+import qualified Data.IntMap.Strict as Map+#endif import qualified Data.IntSet as Set import qualified Data.List as List import qualified Data.MultiSet as MultiSet+import Control.DeepSeq (NFData(..)) {- -- just for testing@@ -143,10 +160,12 @@ import qualified List -} +#if __GLASGOW_HASKELL__ < 800+import Data.Typeable+#endif #if __GLASGOW_HASKELL__ import Text.Read-import Data.Generics.Basics-import Data.Generics.Instances ()+import Data.Data (Data(..), mkNoRepType) #endif {--------------------------------------------------------------------@@ -167,9 +186,10 @@ newtype IntMultiSet = MS { unMS :: IntMap Occur } -- invariant: all values in the map are >= 1 +-- | Key type for IntMultiSet type Key = Int --- | The number of occurences of an element+-- | The number of occurrences of an element type Occur = Int instance Monoid IntMultiSet where@@ -177,6 +197,19 @@ mappend = union mconcat = unions +#if MIN_VERSION_base(4,9,0)+instance Semigroup IntMultiSet where+ (<>) = union+ sconcat = unions . Data.List.NonEmpty.toList+ stimes n ms@(MS m)+ | n <= 0 = empty+ | n == 1 = ms+ | otherwise = MS $ Map.map (* fromIntegral n) m+#endif++instance NFData IntMultiSet where+ rnf = rnf . unMS+ #if __GLASGOW_HASKELL__ {--------------------------------------------------------------------@@ -190,7 +223,7 @@ gfoldl f z set = z fromList `f` (toList set) toConstr _ = error "toConstr" gunfold _ _ = error "gunfold"- dataTypeOf _ = mkNorepType "Data.IntMultiSet.IntMultiSet"+ dataTypeOf _ = mkNoRepType "Data.IntMultiSet.IntMultiSet" #endif @@ -218,7 +251,7 @@ notMember :: Key -> IntMultiSet -> Bool notMember x = not . member x --- | /O(min(n,W))/. The number of occurences of an element in a multiset.+-- | /O(min(n,W))/. The number of occurrences of an element in a multiset. occur :: Key -> IntMultiSet -> Int occur x = Map.findWithDefault 0 x . unMS @@ -244,7 +277,7 @@ -- | /O(min(n,W))/. Insert an element in a multiset a given number of times. ----- Negative numbers remove occurences of the given element.+-- Negative numbers remove occurrences of the given element. insertMany :: Key -> Occur -> IntMultiSet -> IntMultiSet insertMany x n | n < 0 = MS . Map.update (deleteN (negate n)) x . unMS@@ -257,11 +290,11 @@ -- | /O(min(n,W))/. Delete an element from a multiset a given number of times. ----- Negative numbers add occurences of the given element.+-- Negative numbers add occurrences of the given element. deleteMany :: Key -> Occur -> IntMultiSet -> IntMultiSet deleteMany x n = insertMany x (negate n) --- | /O(min(n,W))/. Delete all occurences of an element from a multiset.+-- | /O(min(n,W))/. Delete all occurrences of an element from a multiset. deleteAll :: Key -> IntMultiSet -> IntMultiSet deleteAll x = MS . Map.delete x . unMS @@ -292,41 +325,45 @@ findMin :: IntMultiSet -> Key -- TODO: IntMap has a different findMin than Map --findMin = fst . Map.findMin . unMS-findMin = Map.findMin . unMS+--findMin = Map.findMin . unMS -- | /O(log n)/. The maximal element of a multiset. findMax :: IntMultiSet -> Key -- TODO: IntMap has a different findMin than Map --findMax = fst . Map.findMax . unMS-findMax = Map.findMax . unMS+--findMax = Map.findMax . unMS +-- Note: the documentation for IntMap.findMin/Max is incorrect+-- they return the VALUE at the minimal/maximal key++-- Here is a workarounds of IntMap's deficiencies/inconsistencies.++-- | /O(log n)/. The minimal key of an IntMap.+minKey :: IntMap a -> Int+minKey = maybe (error "IntMultiSet.findMin: empty multiset") (fst . fst) . Map.minViewWithKey++-- | /O(log n)/. The maximal key of an IntMap.+maxKey :: IntMap a -> Int+maxKey = maybe (error "IntMultiSet.findMax: empty multiset") (fst . fst) . Map.maxViewWithKey++findMin = minKey . unMS+findMax = maxKey . unMS++ -- | /O(log n)/. Delete the minimal element. deleteMin :: IntMultiSet -> IntMultiSet--- TODO: IntMap has a different updateMin---deleteMin = MS . Map.updateMin (deleteN 1) . unMS-deleteMin (MS m) = case Map.minView m of- Nothing -> empty- Just (1,m') -> MS m'- Just (_,m') -> MS $ Map.updateMin pred m'+deleteMin = MS . Map.updateMin (deleteN 1) . unMS -- | /O(log n)/. Delete the maximal element. deleteMax :: IntMultiSet -> IntMultiSet---deleteMax = MS . Map.updateMax (deleteN 1) . unMS-deleteMax (MS m) = case Map.maxView m of- Nothing -> empty- Just (1,m') -> MS m'- Just (_,m') -> MS $ Map.updateMax pred m'+deleteMax = MS . Map.updateMax (deleteN 1) . unMS --- | /O(log n)/. Delete all occurences of the minimal element.+-- | /O(log n)/. Delete all occurrences of the minimal element. deleteMinAll :: IntMultiSet -> IntMultiSet--- TODO IntMap's deleteMin will error on empty maps!-deleteMinAll m | null m = m deleteMinAll m = MS . Map.deleteMin . unMS $ m --- | /O(log n)/. Delete all occurences of the maximal element.+-- | /O(log n)/. Delete all occurrences of the maximal element. deleteMaxAll :: IntMultiSet -> IntMultiSet--- TODO IntMap's deleteMax will error on empty maps!-deleteMaxAll m | null m = m deleteMaxAll m = MS . Map.deleteMax . unMS $ m -- | /O(log n)/. Delete and find the minimal element.@@ -347,18 +384,28 @@ deleteFindMax set = (findMax set, deleteMax set) -- | /O(log n)/. Retrieves the minimal element of the multiset, and the set stripped from that element--- @fail@s (in the monad) when passed an empty multiset.-minView :: Monad m => IntMultiSet -> m (Key, IntMultiSet)+-- Returns @Nothing@ when passed an empty multiset.+--+-- Examples:+--+-- >>> minView $ fromList [100, 100, 200, 300]+-- Just (100,fromOccurList [(100,1),(200,1),(300,1)])+minView :: IntMultiSet -> Maybe (Key, IntMultiSet) minView x- | null x = fail "IntMultiSet.minView: empty multiset"- | otherwise = return (deleteFindMin x)+ | null x = Nothing+ | otherwise = Just (deleteFindMin x) -- | /O(log n)/. Retrieves the maximal element of the multiset, and the set stripped from that element -- @fail@s (in the monad) when passed an empty multiset.-maxView :: Monad m => IntMultiSet -> m (Key, IntMultiSet)+--+-- Examples:+--+-- >>> maxView $ fromList [100, 100, 200, 300]+-- Just (300,fromOccurList [(100,2),(200,1)])+maxView :: IntMultiSet -> Maybe (Key, IntMultiSet) maxView x- | null x = fail "IntMultiSet.maxView: empty multiset"- | otherwise = return (deleteFindMin x)+ | null x = Nothing+ | otherwise = Just (deleteFindMax x) {-------------------------------------------------------------------- Union, Difference, Intersection@@ -369,28 +416,29 @@ unions ts = foldlStrict union empty ts --- | /O(n+m)/. The union of two multisets, preferring the first multiset when--- equal elements are encountered.+-- | /O(n+m)/. The union of two multisets. The union adds the occurrences together.+-- -- The implementation uses the efficient /hedge-union/ algorithm. -- Hedge-union is more efficient on (bigset `union` smallset). union :: IntMultiSet -> IntMultiSet -> IntMultiSet union (MS m1) (MS m2) = MS $ Map.unionWith (+) m1 m2 +-- | /O(n+m)/. The union of two multisets.+-- The number of occurrences of each element in the union is+-- the maximum of the number of occurrences in the arguments (instead of the sum).+--+-- The implementation uses the efficient /hedge-union/ algorithm.+-- Hedge-union is more efficient on (bigset `union` smallset).+maxUnion :: IntMultiSet -> IntMultiSet -> IntMultiSet+maxUnion (MS m1) (MS m2) = MS $ Map.unionWith max m1 m2+ -- | /O(n+m)/. Difference of two multisets. -- The implementation uses an efficient /hedge/ algorithm comparable with /hedge-union/. difference :: IntMultiSet -> IntMultiSet -> IntMultiSet difference (MS m1) (MS m2) = MS $ Map.differenceWith (flip deleteN) m1 m2 -- | /O(n+m)/. The intersection of two multisets.--- Elements of the result come from the first multiset, so for example ----- > import qualified Data.MultiSet as MS--- > data AB = A | B deriving Show--- > instance Ord AB where compare _ _ = EQ--- > instance Eq AB where _ == _ = True--- > main = print (MS.singleton A `MS.intersection` MS.singleton B,--- > MS.singleton B `MS.intersection` MS.singleton A)--- -- prints @(fromList [A],fromList [B])@. intersection :: IntMultiSet -> IntMultiSet -> IntMultiSet intersection (MS m1) (MS m2) = MS $ Map.intersectionWith min m1 m2@@ -418,8 +466,7 @@ -- TODO: IntMap doesn't have a mapKeys function map f = fromOccurList . List.map (\(x,o) -> (f x, o)) . toOccurList --- | /O(n)/. The ---+-- | /O(n)/. -- @'mapMonotonic' f s == 'map' f s@, but works only when @f@ is strictly monotonic. -- /The precondition is not checked./ -- Semi-formally, we have:@@ -449,7 +496,7 @@ -- | /O(n)/. Apply a function to each element, and take the union of the results concatMap :: (Key -> [Key]) -> IntMultiSet -> IntMultiSet-concatMap f = fromOccurList . Map.foldWithKey mapF [] . unMS+concatMap f = fromOccurList . Map.foldrWithKey mapF [] . unMS where mapF x occ rest = List.map (\y -> (y,occ)) (f x) ++ rest -- | /O(n)/. Apply a function to each element, and take the union of the results@@ -479,13 +526,13 @@ -- | /O(t)/. Post-order fold. foldr :: (Key -> b -> b) -> b -> IntMultiSet -> b-foldr f z = Map.foldWithKey repF z . unMS+foldr f z = Map.foldrWithKey repF z . unMS where repF a 1 b = f a b repF a n b = repF a (n - 1) (f a b) --- | /O(n)/. Fold over the elements of a multiset with their occurences.+-- | /O(n)/. Fold over the elements of a multiset with their occurrences. foldOccur :: (Key -> Occur -> b -> b) -> b -> IntMultiSet -> b-foldOccur f z = Map.foldWithKey f z . unMS+foldOccur f z = Map.foldrWithKey f z . unMS {-------------------------------------------------------------------- List variations @@ -526,29 +573,33 @@ fromDistinctAscList xs = fromDistinctAscOccurList $ zip xs (repeat 1) {--------------------------------------------------------------------- Occurence lists + Occurrence lists --------------------------------------------------------------------} --- | /O(n)/. Convert the multiset to a list of element\/occurence pairs.+-- | /O(n)/. Convert the multiset to a list of element\/occurrence pairs. toOccurList :: IntMultiSet -> [(Int,Int)] toOccurList = toAscOccurList --- | /O(n)/. Convert the multiset to an ascending list of element\/occurence pairs.+-- | /O(n)/. Convert the multiset to an ascending list of element\/occurrence pairs. toAscOccurList :: IntMultiSet -> [(Int,Int)] toAscOccurList = Map.toAscList . unMS --- | /O(n*min(n,W))/. Create a multiset from a list of element\/occurence pairs.+-- | /O(n*min(n,W))/. Create a multiset from a list of element\/occurrence pairs.+-- Occurrences must be positive.+-- /The precondition (all occurrences > 0) is not checked./ fromOccurList :: [(Int,Int)] -> IntMultiSet fromOccurList = MS . Map.fromListWith (+) --- | /O(n)/. Build a multiset from an ascending list of element\/occurence pairs in linear time.--- /The precondition (input list is ascending) is not checked./+-- | /O(n)/. Build a multiset from an ascending list of element\/occurrence pairs in linear time.+-- Occurrences must be positive.+-- /The precondition (input list is ascending, all occurrences > 0) is not checked./ fromAscOccurList :: [(Int,Int)] -> IntMultiSet fromAscOccurList = MS . Map.fromAscListWith (+) --- | /O(n)/. Build a multiset from an ascending list of elements\/occurence pairs where each elements appears only once.--- /The precondition (input list is strictly ascending) is not checked./+-- | /O(n)/. Build a multiset from an ascending list of elements\/occurrence pairs where each elements appears only once.+-- Occurrences must be positive.+-- /The precondition (input list is strictly ascending, all occurrences > 0) is not checked./ fromDistinctAscOccurList :: [(Int,Int)] -> IntMultiSet fromDistinctAscOccurList = MS . Map.fromDistinctAscList @@ -565,8 +616,8 @@ fromMap = MS . Map.filter (>0) -- | /O(1)/. Convert an 'IntMap' from elements to occurrences to a multiset.--- Assumes that the 'IntMap' contains only values larger than one.--- /The precondition (all elements > 1) is not checked./+-- Assumes that the 'IntMap' contains only values larger than zero.+-- /The precondition (all elements > 0) is not checked./ fromOccurMap :: IntMap Int -> IntMultiSet fromOccurMap = MS @@ -594,7 +645,7 @@ {- -- compare s1 s2 = compare (toAscList s1) (toAscList s2) -- We want {x,x,y} < {x,y}- -- i.e. if the number of occurences differ, more occurences come first.+ -- i.e. if the number of occurrences differ, more occurrences come first. -- But also, {x,x} > {x} -- so this does not hold at the end of the list. --@@ -646,8 +697,10 @@ Typeable/Data --------------------------------------------------------------------} +#if __GLASGOW_HASKELL__ < 800 #include "Typeable.h" INSTANCE_TYPEABLE0(IntMultiSet,intMultiSetTc,"IntMultiSet")+#endif {-------------------------------------------------------------------- Split@@ -660,7 +713,7 @@ split a = (\(x,y) -> (MS x, MS y)) . Map.split a . unMS -- | /O(log n)/. Performs a 'split' but also returns the number of--- occurences of the pivot element in the original set.+-- occurrences of the pivot element in the original set. splitOccur :: Int -> IntMultiSet -> (IntMultiSet,Int,IntMultiSet) splitOccur a (MS t) = let (l,m,r) = Map.splitLookup a t in (MS l, maybe 0 id m, MS r)
Data/MultiSet.hs view
@@ -1,3 +1,8 @@+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE CPP #-}+#if __GLASGOW_HASKELL__+{-# LANGUAGE DeriveDataTypeable, StandaloneDeriving #-}+#endif ----------------------------------------------------------------------------- -- | -- Module : Data.MultiSet@@ -7,11 +12,11 @@ -- Stability : provisional -- Portability : portable ----- An efficient implementation of multisets, also somtimes called bags.+-- An efficient implementation of multisets, also sometimes called bags. -- -- A multiset is like a set, but it can contain multiple copies of the same element. -- Unless otherwise specified all insert and remove opertions affect only a single copy of an element.--- For example the minimal element before and after @deleteMin@ could be the same, only with one less occurence.+-- For example the minimal element before and after @deleteMin@ could be the same, only with one less occurrence. -- -- Since many function names (but not the type name) clash with -- "Prelude" names, this module is usually imported @qualified@, e.g.@@ -59,6 +64,7 @@ -- * Combine , union, unions+ , maxUnion , difference , intersection @@ -132,14 +138,29 @@ ) where import Prelude hiding (filter,foldr,null,map,concatMap)+#if __GLASGOW_HASKELL__ < 710 import Data.Monoid (Monoid(..))+#endif+#if MIN_VERSION_base(4,9,0)+import qualified Data.List.NonEmpty (toList)+import Data.Semigroup (Semigroup(..))+#if !MIN_VERSION_base(4,11,0)+import Data.Semigroup (stimesMonoid)+#endif+#endif import Data.Typeable ()-import qualified Data.Foldable as Foldable (Foldable(foldr))-import Data.Map (Map)+import qualified Data.Foldable as Foldable+import Data.Map.Strict (Map) import Data.Set (Set)-import qualified Data.Map as Map+#if MIN_VERSION_containers(0,5,11)+import qualified Data.Map.Strict as Map hiding (showTreeWith)+import qualified Data.Map.Internal.Debug as Map (showTreeWith)+#else+import qualified Data.Map.Strict as Map+#endif import qualified Data.Set as Set import qualified Data.List as List+import Control.DeepSeq (NFData(..)) {- -- just for testing@@ -148,10 +169,10 @@ import qualified List -} +import Data.Typeable #if __GLASGOW_HASKELL__ import Text.Read-import Data.Generics.Basics-import Data.Generics.Instances ()+import Data.Data (Data(..), mkNoRepType) #endif {--------------------------------------------------------------------@@ -172,7 +193,7 @@ newtype MultiSet a = MS { unMS :: Map a Occur } -- invariant: all values in the map are >= 1 --- | The number of occurences of an element+-- | The number of occurrences of an element type Occur = Int instance Ord a => Monoid (MultiSet a) where@@ -180,9 +201,56 @@ mappend = union mconcat = unions +#if MIN_VERSION_base(4,9,0)+instance Ord a => Semigroup (MultiSet a) where+ (<>) = union+ sconcat = unions . Data.List.NonEmpty.toList+ stimes n ms@(MS m)+ | n <= 0 = empty+ | n == 1 = ms+ | otherwise = MS $ Map.map (* fromIntegral n) m+#endif++-- | Note that 'elem' is slower than 'member'. instance Foldable.Foldable MultiSet where- foldr = fold+ foldr = Data.MultiSet.foldr+ foldl f z = Map.foldlWithKey repF z . unMS+ where repF acc x 1 = f acc x+ repF acc x n = repF (f acc x) x (n - 1)+ foldr1 f = foldr1 f . toList+ foldl1 f = foldl1 f . toList +#if MIN_VERSION_base(4,11,0)+ fold = Map.foldMapWithKey (\x n -> stimes n x) . unMS+ foldMap f = Map.foldMapWithKey (\x n -> stimes n (f x)) . unMS+#elif MIN_VERSION_base(4,9,0)+ fold = Map.foldMapWithKey (\x n -> stimesMonoid n x) . unMS+ foldMap f = Map.foldMapWithKey (\x n -> stimesMonoid n (f x)) . unMS+#endif++#if MIN_VERSION_base(4,6,0)+ foldr' f z = Map.foldrWithKey' repF z . unMS+ where repF x 1 !acc = f x acc+ repF x n !acc = repF x (n - 1) (f x acc)+ foldl' f z = Map.foldlWithKey' repF z . unMS+ where repF !acc x 1 = f acc x+ repF !acc x n = repF (f acc x) x (n - 1)+#endif++#if MIN_VERSION_base(4,8,0)+ toList = toList+ null = null+ length = size+ elem x = elem x . distinctElems+ maximum = findMax+ minimum = findMin+ sum = Map.foldlWithKey' (\s x n -> s + (x * fromIntegral n)) 0 . unMS+ product = Map.foldlWithKey' (\p x n -> p * (x ^ n)) 1 . unMS+#endif++instance NFData a => NFData (MultiSet a) where+ rnf = rnf . unMS+ #if __GLASGOW_HASKELL__ {--------------------------------------------------------------------@@ -196,7 +264,7 @@ gfoldl f z set = z fromList `f` (toList set) toConstr _ = error "toConstr" gunfold _ _ = error "gunfold"- dataTypeOf _ = mkNorepType "Data.MultiSet.MultiSet"+ dataTypeOf _ = mkNoRepType "Data.MultiSet.MultiSet" dataCast1 f = gcast1 f #endif@@ -211,7 +279,7 @@ -- | /O(n)/. The number of elements in the multiset. size :: MultiSet a -> Occur-size = sum . Map.elems . unMS+size = Map.foldl' (+) 0 . unMS -- | /O(1)/. The number of distinct elements in the multiset. distinctSize :: MultiSet a -> Occur@@ -225,7 +293,7 @@ notMember :: Ord a => a -> MultiSet a -> Bool notMember x = not . member x --- | /O(log n)/. The number of occurences of an element in a multiset.+-- | /O(log n)/. The number of occurrences of an element in a multiset. occur :: Ord a => a -> MultiSet a -> Occur occur x = Map.findWithDefault 0 x . unMS @@ -247,16 +315,16 @@ -- | /O(log n)/. Insert an element in a multiset. insert :: Ord a => a -> MultiSet a -> MultiSet a-insert x = MS . Map.insertWith' (+) x 1 . unMS+insert x = MS . Map.insertWith (+) x 1 . unMS -- | /O(log n)/. Insert an element in a multiset a given number of times. ----- Negative numbers remove occurences of the given element.+-- Negative numbers remove occurrences of the given element. insertMany :: Ord a => a -> Occur -> MultiSet a -> MultiSet a insertMany x n | n < 0 = MS . Map.update (deleteN (negate n)) x . unMS | n == 0 = id- | otherwise = MS . Map.insertWith' (+) x n . unMS+ | otherwise = MS . Map.insertWith (+) x n . unMS -- | /O(log n)/. Delete a single element from a multiset. delete :: Ord a => a -> MultiSet a -> MultiSet a@@ -264,11 +332,11 @@ -- | /O(log n)/. Delete an element from a multiset a given number of times. ----- Negative numbers add occurences of the given element.+-- Negative numbers add occurrences of the given element. deleteMany :: Ord a => a -> Occur -> MultiSet a -> MultiSet a deleteMany x n = insertMany x (negate n) --- | /O(log n)/. Delete all occurences of an element from a multiset.+-- | /O(log n)/. Delete all occurrences of an element from a multiset. deleteAll :: Ord a => a -> MultiSet a -> MultiSet a deleteAll x = MS . Map.delete x . unMS @@ -311,11 +379,11 @@ deleteMax :: MultiSet a -> MultiSet a deleteMax = MS . Map.updateMax (deleteN 1) . unMS --- | /O(log n)/. Delete all occurences of the minimal element.+-- | /O(log n)/. Delete all occurrences of the minimal element. deleteMinAll :: MultiSet a -> MultiSet a deleteMinAll = MS . Map.deleteMin . unMS --- | /O(log n)/. Delete all occurences of the maximal element.+-- | /O(log n)/. Delete all occurrences of the maximal element. deleteMaxAll :: MultiSet a -> MultiSet a deleteMaxAll = MS . Map.deleteMax . unMS @@ -337,19 +405,29 @@ -- | /O(log n)/. Retrieves the minimal element of the multiset, -- and the set with that element removed.--- @fail@s (in the monad) when passed an empty multiset.-minView :: Monad m => MultiSet a -> m (a, MultiSet a)+-- Returns @Nothing@ when passed an empty multiset.+--+-- Examples:+--+-- >>> minView $ fromList ['a', 'a', 'b', 'c']+-- Just ('a',fromOccurList [('a',1),('b',1),('c',1)])+minView :: MultiSet a -> Maybe (a, MultiSet a) minView x- | null x = fail "MultiSet.minView: empty multiset"- | otherwise = return (deleteFindMin x)+ | null x = Nothing+ | otherwise = Just (deleteFindMin x) -- | /O(log n)/. Retrieves the maximal element of the multiset, -- and the set with that element removed.--- @fail@s (in the monad) when passed an empty multiset.-maxView :: Monad m => MultiSet a -> m (a, MultiSet a)+-- Returns @Nothing@ when passed an empty multiset.+--+-- Examples:+--+-- >>> maxView $ fromList ['a', 'a', 'b', 'c']+-- Just ('c',fromOccurList [('a',2),('b',1)])+maxView :: MultiSet a -> Maybe (a, MultiSet a) maxView x- | null x = fail "MultiSet.maxView: empty multiset"- | otherwise = return (deleteFindMin x)+ | null x = Nothing+ | otherwise = Just (deleteFindMax x) {-------------------------------------------------------------------- Union, Difference, Intersection@@ -360,13 +438,22 @@ unions ts = foldlStrict union empty ts --- | /O(n+m)/. The union of two multisets, preferring the first multiset when--- equal elements are encountered.+-- | /O(n+m)/. The union of two multisets. The union adds the occurrences together.+-- -- The implementation uses the efficient /hedge-union/ algorithm. -- Hedge-union is more efficient on (bigset `union` smallset). union :: Ord a => MultiSet a -> MultiSet a -> MultiSet a union (MS m1) (MS m2) = MS $ Map.unionWith (+) m1 m2 +-- | /O(n+m)/. The union of two multisets.+-- The number of occurrences of each element in the union is+-- the maximum of the number of occurrences in the arguments (instead of the sum).+--+-- The implementation uses the efficient /hedge-union/ algorithm.+-- Hedge-union is more efficient on (bigset `union` smallset).+maxUnion :: Ord a => MultiSet a -> MultiSet a -> MultiSet a+maxUnion (MS m1) (MS m2) = MS $ Map.unionWith max m1 m2+ -- | /O(n+m)/. Difference of two multisets. -- The implementation uses an efficient /hedge/ algorithm comparable with /hedge-union/. difference :: Ord a => MultiSet a -> MultiSet a -> MultiSet a@@ -390,13 +477,13 @@ Filter and partition --------------------------------------------------------------------} -- | /O(n)/. Filter all elements that satisfy the predicate.-filter :: Ord a => (a -> Bool) -> MultiSet a -> MultiSet a+filter :: (a -> Bool) -> MultiSet a -> MultiSet a filter p = MS . Map.filterWithKey (\k _ -> p k) . unMS -- | /O(n)/. Partition the multiset into two multisets, one with all elements that satisfy -- the predicate and one with all elements that don't satisfy the predicate. -- See also 'split'.-partition :: Ord a => (a -> Bool) -> MultiSet a -> (MultiSet a,MultiSet a)+partition :: (a -> Bool) -> MultiSet a -> (MultiSet a,MultiSet a) partition p = (\(x,y) -> (MS x, MS y)) . Map.partitionWithKey (\k _ -> p k) . unMS {----------------------------------------------------------------------@@ -405,11 +492,10 @@ -- | /O(n*log n)/. -- @'map' f s@ is the multiset obtained by applying @f@ to each element of @s@.-map :: (Ord a, Ord b) => (a->b) -> MultiSet a -> MultiSet b+map :: (Ord b) => (a->b) -> MultiSet a -> MultiSet b map f = MS . Map.mapKeysWith (+) f . unMS --- | /O(n)/. The ---+-- | /O(n)/. -- @'mapMonotonic' f s == 'map' f s@, but works only when @f@ is strictly monotonic. -- /The precondition is not checked./ -- Semi-formally, we have:@@ -421,7 +507,7 @@ mapMonotonic f = MS . Map.mapKeysMonotonic f . unMS -- | /O(n)/. Map and collect the 'Just' results.-mapMaybe :: (Ord a, Ord b) => (a -> Maybe b) -> MultiSet a -> MultiSet b+mapMaybe :: (Ord b) => (a -> Maybe b) -> MultiSet a -> MultiSet b mapMaybe f = fromOccurList . mapMaybe' . toOccurList where mapMaybe' [] = [] mapMaybe' ((x,n):xs) = case f x of@@ -429,7 +515,7 @@ Nothing -> mapMaybe' xs -- | /O(n)/. Map and separate the 'Left' and 'Right' results.-mapEither :: (Ord a, Ord b, Ord c) => (a -> Either b c) -> MultiSet a -> (MultiSet b, MultiSet c)+mapEither :: (Ord b, Ord c) => (a -> Either b c) -> MultiSet a -> (MultiSet b, MultiSet c) mapEither f = (\(ls,rs) -> (fromOccurList ls, fromOccurList rs)) . mapEither' . toOccurList where mapEither' [] = ([],[]) mapEither' ((x,n):xs) = case f x of@@ -438,12 +524,12 @@ -- | /O(n)/. Apply a function to each element, and take the union of the results-concatMap :: (Ord a, Ord b) => (a -> [b]) -> MultiSet a -> MultiSet b-concatMap f = fromOccurList . Map.foldWithKey mapF [] . unMS+concatMap :: (Ord b) => (a -> [b]) -> MultiSet a -> MultiSet b+concatMap f = fromOccurList . Map.foldrWithKey mapF [] . unMS where mapF x occ rest = List.map (\y -> (y,occ)) (f x) ++ rest -- | /O(n)/. Apply a function to each element, and take the union of the results-unionsMap :: (Ord a, Ord b) => (a -> MultiSet b) -> MultiSet a -> MultiSet b+unionsMap :: (Ord b) => (a -> MultiSet b) -> MultiSet a -> MultiSet b unionsMap f = unions . List.map timesF . toOccurList where timesF (ms,1) = f ms timesF (ms,n) = MS . Map.map (*n) . unMS $ f ms@@ -455,7 +541,7 @@ times (ms,n) = MS . Map.map (*n) . unMS $ ms -- | /O(n)/. The monad bind operation, (>>=), for multisets.-bind :: (Ord a, Ord b) => MultiSet a -> (a -> MultiSet b) -> MultiSet b+bind :: (Ord b) => MultiSet a -> (a -> MultiSet b) -> MultiSet b bind = flip unionsMap {--------------------------------------------------------------------@@ -469,13 +555,13 @@ -- | /O(t)/. Post-order fold. foldr :: (a -> b -> b) -> b -> MultiSet a -> b-foldr f z = Map.foldWithKey repF z . unMS+foldr f z = Map.foldrWithKey repF z . unMS where repF a 1 b = f a b repF a n b = repF a (n - 1) (f a b) --- | /O(n)/. Fold over the elements of a multiset with their occurences.+-- | /O(n)/. Fold over the elements of a multiset with their occurrences. foldOccur :: (a -> Occur -> b -> b) -> b -> MultiSet a -> b-foldOccur f z = Map.foldWithKey f z . unMS+foldOccur f z = Map.foldrWithKey f z . unMS {-------------------------------------------------------------------- List variations @@ -516,29 +602,33 @@ fromDistinctAscList xs = fromDistinctAscOccurList $ zip xs (repeat 1) {--------------------------------------------------------------------- Occurence lists + Occurrence lists --------------------------------------------------------------------} --- | /O(n)/. Convert the multiset to a list of element\/occurence pairs.+-- | /O(n)/. Convert the multiset to a list of element\/occurrence pairs. toOccurList :: MultiSet a -> [(a,Occur)] toOccurList = toAscOccurList --- | /O(n)/. Convert the multiset to an ascending list of element\/occurence pairs.+-- | /O(n)/. Convert the multiset to an ascending list of element\/occurrence pairs. toAscOccurList :: MultiSet a -> [(a,Occur)] toAscOccurList = Map.toAscList . unMS --- | /O(n*log n)/. Create a multiset from a list of element\/occurence pairs.+-- | /O(n*log n)/. Create a multiset from a list of element\/occurrence pairs.+-- Occurrences must be positive.+-- /The precondition (all occurrences > 0) is not checked./ fromOccurList :: Ord a => [(a,Occur)] -> MultiSet a fromOccurList = MS . Map.fromListWith (+) --- | /O(n)/. Build a multiset from an ascending list of element\/occurence pairs in linear time.--- /The precondition (input list is ascending) is not checked./+-- | /O(n)/. Build a multiset from an ascending list of element\/occurrence pairs in linear time.+-- Occurrences must be positive.+-- /The precondition (input list is ascending, all occurrences > 0) is not checked./ fromAscOccurList :: Eq a => [(a,Occur)] -> MultiSet a fromAscOccurList = MS . Map.fromAscListWith (+) --- | /O(n)/. Build a multiset from an ascending list of elements\/occurence pairs where each elements appears only once.--- /The precondition (input list is strictly ascending) is not checked./+-- | /O(n)/. Build a multiset from an ascending list of elements\/occurrence pairs where each elements appears only once.+-- Occurrences must be positive.+-- /The precondition (input list is strictly ascending, all occurrences > 0) is not checked./ fromDistinctAscOccurList :: [(a,Occur)] -> MultiSet a fromDistinctAscOccurList = MS . Map.fromDistinctAscList @@ -551,12 +641,12 @@ toMap = unMS -- | /O(n)/. Convert a 'Map' from elements to occurrences to a multiset.-fromMap :: Ord a => Map a Occur -> MultiSet a+fromMap :: Map a Occur -> MultiSet a fromMap = MS . Map.filter (>0) -- | /O(1)/. Convert a 'Map' from elements to occurrences to a multiset.--- Assumes that the 'Map' contains only values larger than one.--- /The precondition (all elements > 1) is not checked./+-- Assumes that the 'Map' contains only values larger than zero.+-- /The precondition (all elements > 0) is not checked./ fromOccurMap :: Map a Occur -> MultiSet a fromOccurMap = MS @@ -584,7 +674,7 @@ {- -- compare s1 s2 = compare (toAscList s1) (toAscList s2) -- We want {x,x,y} < {x,y}- -- i.e. if the number of occurences differ, more occurences come first.+ -- i.e. if the number of occurrences differ, more occurrences come first. -- But also, {x,x} > {x} -- so this does not hold at the end of the list. --@@ -636,8 +726,10 @@ Typeable/Data --------------------------------------------------------------------} +#if __GLASGOW_HASKELL__ < 800 #include "Typeable.h" INSTANCE_TYPEABLE1(MultiSet,multiSetTc,"MultiSet")+#endif {-------------------------------------------------------------------- Split@@ -650,7 +742,7 @@ split a = (\(x,y) -> (MS x, MS y)) . Map.split a . unMS -- | /O(log n)/. Performs a 'split' but also returns the number of--- occurences of the pivot element in the original set.+-- occurrences of the pivot element in the original set. splitOccur :: Ord a => a -> MultiSet a -> (MultiSet a,Occur,MultiSet a) splitOccur a (MS t) = let (l,m,r) = Map.splitLookup a t in (MS l, maybe 0 id m, MS r)
LICENSE view
@@ -1,4 +1,4 @@-Copyright (c) Twan van Laarhoven 2007.+Copyright (c) Twan van Laarhoven 2007-2009. All rights reserved.
include/Typeable.h view
@@ -3,70 +3,36 @@ // // INSTANCE_TYPEABLEn(tc,tcname,"tc") defines //-// instance Typeable/n/ tc-// instance Typeable a => Typeable/n-1/ (tc a)-// instance (Typeable a, Typeable b) => Typeable/n-2/ (tc a b)-// ...-// instance (Typeable a1, ..., Typeable an) => Typeable (tc a1 ... an)+// instance Typeable/n/ tc+// instance Typeable a => Typeable/n-1/ (tc a)+// instance (Typeable a, Typeable b) => Typeable/n-2/ (tc a b)+// ...+// instance (Typeable a1, ..., Typeable an) => Typeable (tc a1 ... an) // -------------------------------------------------------------------------- -} #ifndef TYPEABLE_H #define TYPEABLE_H -#define INSTANCE_TYPEABLE0(tycon,tcname,str) \-tcname :: TyCon; \-tcname = mkTyCon str; \-instance Typeable tycon where { typeOf _ = mkTyConApp tcname [] }--#ifdef __GLASGOW_HASKELL__---- // For GHC, the extra instances follow from general instance declarations--- // defined in Data.Typeable.--#define INSTANCE_TYPEABLE1(tycon,tcname,str) \-tcname :: TyCon; \-tcname = mkTyCon str; \-instance Typeable1 tycon where { typeOf1 _ = mkTyConApp tcname [] }--#define INSTANCE_TYPEABLE2(tycon,tcname,str) \-tcname :: TyCon; \-tcname = mkTyCon str; \-instance Typeable2 tycon where { typeOf2 _ = mkTyConApp tcname [] }--#define INSTANCE_TYPEABLE3(tycon,tcname,str) \-tcname :: TyCon; \-tcname = mkTyCon str; \-instance Typeable3 tycon where { typeOf3 _ = mkTyConApp tcname [] }--#else /* !__GLASGOW_HASKELL__ */--#define INSTANCE_TYPEABLE1(tycon,tcname,str) \-tcname :: TyCon; \-tcname = mkTyCon str; \-instance Typeable1 tycon where { typeOf1 _ = mkTyConApp tcname [] }; \-instance Typeable a => Typeable (tycon a) where { typeOf = typeOfDefault }--#define INSTANCE_TYPEABLE2(tycon,tcname,str) \-tcname :: TyCon; \-tcname = mkTyCon str; \-instance Typeable2 tycon where { typeOf2 _ = mkTyConApp tcname [] }; \-instance Typeable a => Typeable1 (tycon a) where { \- typeOf1 = typeOf1Default }; \-instance (Typeable a, Typeable b) => Typeable (tycon a b) where { \- typeOf = typeOfDefault }--#define INSTANCE_TYPEABLE3(tycon,tcname,str) \-tcname :: TyCon; \-tcname = mkTyCon str; \-instance Typeable3 tycon where { typeOf3 _ = mkTyConApp tcname [] }; \-instance Typeable a => Typeable2 (tycon a) where { \- typeOf2 = typeOf2Default }; \-instance (Typeable a, Typeable b) => Typeable1 (tycon a b) where { \- typeOf1 = typeOf1Default }; \-instance (Typeable a, Typeable b, Typeable c) => Typeable (tycon a b c) where { \- typeOf = typeOfDefault }--#endif /* !__GLASGOW_HASKELL__ */+#if __GLASGOW_HASKELL__ >= 707+#define INSTANCE_TYPEABLE0(tycon,tcname,str) deriving instance Typeable tycon+#define INSTANCE_TYPEABLE1(tycon,tcname,str) deriving instance Typeable tycon+#define INSTANCE_TYPEABLE2(tycon,tcname,str) deriving instance Typeable tycon+#elif defined(__GLASGOW_HASKELL__)+#define INSTANCE_TYPEABLE0(tycon,tcname,str) deriving instance Typeable tycon+#define INSTANCE_TYPEABLE1(tycon,tcname,str) deriving instance Typeable1 tycon+#define INSTANCE_TYPEABLE2(tycon,tcname,str) deriving instance Typeable2 tycon+#define INSTANCE_TYPEABLE3(tycon,tcname,str) deriving instance Typeable3 tycon+#else+#define INSTANCE_TYPEABLE0(tycon,tcname,str) tcname :: TyCon; tcname = mkTyCon str; \+ instance Typeable tycon where { typeOf _ = mkTyConApp tcname [] }+#define INSTANCE_TYPEABLE1(tycon,tcname,str) tcname :: TyCon; tcname = mkTyCon str; \+ instance Typeable1 tycon where { typeOf1 _ = mkTyConApp tcname [] }; \+ instance Typeable a => Typeable (tycon a) where { typeOf = typeOfDefault }+#define INSTANCE_TYPEABLE2(tycon,tcname,str) tcname :: TyCon; tcname = mkTyCon str; \+ instance Typeable2 tycon where { typeOf2 _ = mkTyConApp tcname [] }; \+ instance Typeable a => Typeable1 (tycon a) where { typeOf1 = typeOf1Default }; \+ instance (Typeable a, Typeable b) => Typeable (tycon a b) where { typeOf = typeOfDefault }+#endif #endif
multiset.cabal view
@@ -1,16 +1,55 @@ name: multiset-version: 0.1+version: 0.3.4.3 author: Twan van Laarhoven maintainer: twanvl@gmail.com-category: Data+bug-reports: https://github.com/twanvl/multiset/issues+category: Data Structures synopsis: The Data.MultiSet container type-description: A variation of Data.Set. Multisets, sometimes also called bags, can contain multiple copies of the same key.+description:+ A variation of Data.Set.+ Multisets, sometimes also called bags, can contain multiple copies of the same key. license: BSD3 license-file: LICENSE-build-depends: base, containers build-type: Simple-include-dirs: include-extensions: CPP-exposed-modules: Data.MultiSet, Data.IntMultiSet-extra-source-files: include/Typeable.h-ghc-options: -Wall+Cabal-version: >= 1.10+extra-source-files: include/Typeable.h CHANGELOG+tested-with: GHC == 8.6.4, GHC == 8.4.4, GHC == 8.2.2, GHC == 8.0.2,+ GHC == 7.10.3, GHC == 7.8.4, GHC == 7.6.3, GHC == 7.4.2,+ GHC == 7.2.2, GHC == 7.0.4++source-repository head+ type: git+ location: http://github.com/twanvl/multiset.git++Library+ default-language: Haskell2010+ exposed-modules: Data.MultiSet, Data.IntMultiSet++ include-dirs: include+ default-extensions: CPP+ ghc-options: -Wall+ build-depends: containers >= 0.5.4, base >= 4 && < 5, deepseq >=1.2 && <1.5++test-suite doctests+ default-language: Haskell2010+ type: exitcode-stdio-1.0+ ghc-options: -threaded+ hs-source-dirs: test+ main-is: Main.hs+ build-depends: base >= 4 && < 5+ , doctest+ if impl(ghc < 8.0)+ buildable: False++test-suite multiset-properties+ default-language: Haskell2010+ type: exitcode-stdio-1.0+ ghc-options: -threaded+ hs-source-dirs: test+ main-is: multiset-properties.hs+ build-depends: QuickCheck+ , base+ , checkers >= 0.5+ , multiset+ , tasty+ , tasty-quickcheck
+ test/Main.hs view
@@ -0,0 +1,5 @@+module Main (main) where++import Test.DocTest (doctest)++main = doctest ["-Iinclude", "Data/MultiSet.hs", "Data/IntMultiSet.hs"]
+ test/multiset-properties.hs view
@@ -0,0 +1,19 @@+import Data.Monoid (Sum(..))+import Data.MultiSet+import Test.QuickCheck (Arbitrary(..))+import qualified Test.QuickCheck.Classes+import qualified Test.QuickCheck.Checkers+import Test.QuickCheck.Checkers (EqProp(..))+import qualified Test.Tasty+import qualified Test.Tasty.QuickCheck++main = Test.Tasty.defaultMain+ (uncurry Test.Tasty.QuickCheck.testProperties+ (Test.QuickCheck.Classes.foldable+ (undefined :: MultiSet (Integer, Integer, [Integer], Integer, Integer))))++instance (Arbitrary a, Ord a) => Arbitrary (MultiSet a) where+ arbitrary = fromList <$> arbitrary++instance Eq a => EqProp (MultiSet a) where+ (=-=) = Test.QuickCheck.Checkers.eq