packages feed

multiset 0.2.2 → 0.3.4.3

raw patch · 7 files changed

Files

+ 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
@@ -11,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@@ -131,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.Strict (IntMap) import Data.IntSet (IntSet) import Data.MultiSet (MultiSet)+#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@@ -148,7 +160,9 @@ import qualified List -} +#if __GLASGOW_HASKELL__ < 800 import Data.Typeable+#endif #if __GLASGOW_HASKELL__ import Text.Read import Data.Data (Data(..), mkNoRepType)@@ -172,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@@ -182,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__  {--------------------------------------------------------------------@@ -223,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 @@ -249,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@@ -262,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 @@ -330,11 +358,11 @@ deleteMax :: IntMultiSet -> IntMultiSet 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 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 deleteMaxAll m = MS . Map.deleteMax . unMS $ m @@ -356,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@@ -378,7 +416,7 @@ unions ts   = foldlStrict union empty ts --- | /O(n+m)/. The union of two multisets. The union adds the occurences together.+-- | /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).@@ -386,8 +424,8 @@ union (MS m1) (MS m2) = MS $ Map.unionWith (+) m1 m2  -- | /O(n+m)/. The union of two multisets.--- The number of occurences of each element in the union is--- the maximum of the number of occurences in the arguments (instead of the sum).+-- 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).@@ -428,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:@@ -493,7 +530,7 @@  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.foldrWithKey f z . unMS @@ -536,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 @@ -575,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 @@ -604,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.   --@@ -656,8 +697,10 @@   Typeable/Data --------------------------------------------------------------------} +#if __GLASGOW_HASKELL__ < 800 #include "Typeable.h" INSTANCE_TYPEABLE0(IntMultiSet,intMultiSetTc,"IntMultiSet")+#endif  {--------------------------------------------------------------------   Split@@ -670,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,4 @@+{-# LANGUAGE BangPatterns #-} {-# LANGUAGE CPP #-} #if __GLASGOW_HASKELL__ {-# LANGUAGE DeriveDataTypeable, StandaloneDeriving #-}@@ -11,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.@@ -137,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 qualified Data.Foldable as Foldable import Data.Map.Strict (Map) import Data.Set (Set)+#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@@ -177,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@@ -185,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__  {--------------------------------------------------------------------@@ -216,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@@ -230,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 @@ -256,7 +319,7 @@  -- | /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@@ -269,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 @@ -316,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 @@ -342,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@@ -365,7 +438,7 @@ unions ts   = foldlStrict union empty ts --- | /O(n+m)/. The union of two multisets. The union adds the occurences together.+-- | /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).@@ -373,8 +446,8 @@ union (MS m1) (MS m2) = MS $ Map.unionWith (+) m1 m2  -- | /O(n+m)/. The union of two multisets.--- The number of occurences of each element in the union is--- the maximum of the number of occurences in the arguments (instead of the sum).+-- 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).@@ -404,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  {----------------------------------------------------------------------@@ -419,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:@@ -435,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@@ -443,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@@ -452,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 :: (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@@ -469,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  {--------------------------------------------------------------------@@ -487,7 +559,7 @@  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.foldrWithKey f z . unMS @@ -530,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 @@ -565,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 @@ -598,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.   --@@ -650,8 +726,10 @@   Typeable/Data --------------------------------------------------------------------} +#if __GLASGOW_HASKELL__ < 800 #include "Typeable.h" INSTANCE_TYPEABLE1(MultiSet,multiSetTc,"MultiSet")+#endif  {--------------------------------------------------------------------   Split@@ -664,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)
include/Typeable.h view
@@ -14,46 +14,25 @@ #ifndef TYPEABLE_H #define TYPEABLE_H -#ifdef __GLASGOW_HASKELL__----  // For GHC, we can use DeriveDataTypeable + StandaloneDeriving to---  // generate the instances.-+#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 /* !__GLASGOW_HASKELL__ */--#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 = 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 = 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 = 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__ */+#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,5 +1,5 @@ name:             multiset-version:          0.2.2+version:          0.3.4.3 author:           Twan van Laarhoven maintainer:       twanvl@gmail.com bug-reports:      https://github.com/twanvl/multiset/issues@@ -11,17 +11,45 @@ license:          BSD3 license-file:     LICENSE build-type:       Simple-Cabal-version:    >= 1.6-extra-source-files: include/Typeable.h+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-  extensions:         CPP+  default-extensions: CPP   ghc-options:        -Wall-  build-depends:      containers >= 0.5, base >= 4 && < 5+  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