packages feed

unordered-containers 0.2.7.2 → 0.2.8.0

raw patch · 8 files changed

+196/−27 lines, 8 filesdep ~hashable

Dependency ranges changed: hashable

Files

CHANGES.md view
@@ -1,3 +1,13 @@+## 0.2.8.0++ * Add `Eq1/2`, `Show1/2`, `Read1` instances with `base-4.9`++ * `Eq (HashSet a)` doesn't require `Hashable a` anymore, only `Eq a`.++ * Add `Hashable1/2` with `hashable-1.2.6.0`++ * Add `differenceWith` function.+ ## 0.2.7.2   * Don't use -fregs-graphs
Data/HashMap/Base.hs view
@@ -45,6 +45,7 @@        -- * Difference and intersection     , difference+    , differenceWith     , intersection     , intersectionWith     , intersectionWithKey@@ -89,6 +90,7 @@     , updateOrConcatWith     , updateOrConcatWithKey     , filterMapAux+    , equalKeys     ) where  #if __GLASGOW_HASKELL__ < 710@@ -125,7 +127,15 @@ import qualified GHC.Exts as Exts #endif +#if MIN_VERSION_base(4,9,0)+import Data.Functor.Classes+#endif +#if MIN_VERSION_hashable(1,2,5)+import qualified Data.Hashable.Lifted as H+#endif++-- | A set of values.  A set cannot contain duplicate values. ------------------------------------------------------------------------  -- | Convenience function.  Compute a hash value for the given value.@@ -203,6 +213,25 @@ type Bitmap = Word type Shift  = Int +#if MIN_VERSION_base(4,9,0)+instance Show2 HashMap where+    liftShowsPrec2 spk slk spv slv d m =+        showsUnaryWith (liftShowsPrec sp sl) "fromList" d (toList m)+      where+        sp = liftShowsPrec2 spk slk spv slv+        sl = liftShowList2 spk slk spv slv++instance Show k => Show1 (HashMap k) where+    liftShowsPrec = liftShowsPrec2 showsPrec showList++instance (Eq k, Hashable k, Read k) => Read1 (HashMap k) where+    liftReadsPrec rp rl = readsData $+        readsUnaryWith (liftReadsPrec rp' rl') "fromList" fromList+      where+        rp' = liftReadsPrec rp rl+        rl' = liftReadList rp rl+#endif+ instance (Eq k, Hashable k, Read k, Read e) => Read (HashMap k e) where     readPrec = parens $ prec 10 $ do       Ident "fromList" <- lexP@@ -218,26 +247,102 @@ instance Traversable (HashMap k) where     traverse f = traverseWithKey (const f) +#if MIN_VERSION_base(4,9,0)+instance Eq2 HashMap where+    liftEq2 = equal++instance Eq k => Eq1 (HashMap k) where+    liftEq = equal (==)+#endif+ instance (Eq k, Eq v) => Eq (HashMap k v) where-    (==) = equal+    (==) = equal (==) (==) -equal :: (Eq k, Eq v) => HashMap k v -> HashMap k v -> Bool-equal t1 t2 = go (toList' t1 []) (toList' t2 [])+equal :: (k -> k' -> Bool) -> (v -> v' -> Bool)+      -> HashMap k v -> HashMap k' v' -> Bool+equal eqk eqv t1 t2 = go (toList' t1 []) (toList' t2 [])   where     -- If the two trees are the same, then their lists of 'Leaf's and     -- 'Collision's read from left to right should be the same (modulo the     -- order of elements in 'Collision').      go (Leaf k1 l1 : tl1) (Leaf k2 l2 : tl2)-      | k1 == k2 && l1 == l2+      | k1 == k2 && leafEq l1 l2       = go tl1 tl2     go (Collision k1 ary1 : tl1) (Collision k2 ary2 : tl2)       | k1 == k2 && A.length ary1 == A.length ary2 &&-        L.null (A.toList ary1 L.\\ A.toList ary2)+        isPermutationBy leafEq (A.toList ary1) (A.toList ary2)       = go tl1 tl2     go [] [] = True     go _  _  = False +    leafEq (L k v) (L k' v') = eqk k k' && eqv v v'++-- Note: previous implemenation isPermutation = null (as // bs)+-- was O(n^2) too.+--+-- This assumes lists are of equal length+isPermutationBy :: (a -> b -> Bool) -> [a] -> [b] -> Bool+isPermutationBy f = go+  where+    f' = flip f++    go [] [] = True+    go (x : xs) (y : ys)+        | f x y     = go xs ys+        | otherwise = go (deleteBy f' y xs) (deleteBy f x ys)+    go [] (_ : _) = False+    go (_ : _) [] = False++-- Data.List.deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]+deleteBy                :: (a -> b -> Bool) -> a -> [b] -> [b]+deleteBy _  _ []        = []+deleteBy eq x (y:ys)    = if x `eq` y then ys else y : deleteBy eq x ys++-- Same as 'equal' but doesn't compare the values.+equalKeys :: (k -> k' -> Bool) -> HashMap k v -> HashMap k' v' -> Bool+equalKeys eq t1 t2 = go (toList' t1 []) (toList' t2 [])+  where+    go (Leaf k1 l1 : tl1) (Leaf k2 l2 : tl2)+      | k1 == k2 && leafEq l1 l2+      = go tl1 tl2+    go (Collision k1 ary1 : tl1) (Collision k2 ary2 : tl2)+      | k1 == k2 && A.length ary1 == A.length ary2 &&+        isPermutationBy leafEq (A.toList ary1) (A.toList ary2)+      = go tl1 tl2+    go [] [] = True+    go _  _  = False++    leafEq (L k _) (L k' _) = eq k k'++#if MIN_VERSION_hashable(1,2,5)+instance H.Hashable2 HashMap where+    liftHashWithSalt2 hk hv salt hm = go salt (toList' hm [])+      where+        -- go :: Int -> [HashMap k v] -> Int+        go s [] = s+        go s (Leaf _ l : tl)+          = s `hashLeafWithSalt` l `go` tl+        -- For collisions we hashmix hash value+        -- and then array of values' hashes sorted+        go s (Collision h a : tl)+          = (s `H.hashWithSalt` h) `hashCollisionWithSalt` a `go` tl+        go s (_ : tl) = s `go` tl++        -- hashLeafWithSalt :: Int -> Leaf k v -> Int+        hashLeafWithSalt s (L k v) = (s `hk` k) `hv` v++        -- hashCollisionWithSalt :: Int -> A.Array (Leaf k v) -> Int+        hashCollisionWithSalt s+          = L.foldl' H.hashWithSalt s . arrayHashesSorted s++        -- arrayHashesSorted :: Int -> A.Array (Leaf k v) -> [Int]+        arrayHashesSorted s = L.sort . L.map (hashLeafWithSalt s) . A.toList++instance (Hashable k) => H.Hashable1 (HashMap k) where+    liftHashWithSalt = H.liftHashWithSalt2 H.hashWithSalt+#endif+ instance (Hashable k, Hashable v) => Hashable (HashMap k v) where     hashWithSalt salt hm = go salt (toList' hm [])       where@@ -256,13 +361,10 @@          hashCollisionWithSalt :: Int -> A.Array (Leaf k v) -> Int         hashCollisionWithSalt s-          = L.foldl' H.hashWithSalt s . arrayHashesSorted--        arrayHashesSorted :: A.Array (Leaf k v) -> [Int]-        arrayHashesSorted = L.sort . L.map leafValueHash . A.toList+          = L.foldl' H.hashWithSalt s . arrayHashesSorted s -        leafValueHash :: Leaf k v -> Int-        leafValueHash (L _ v) = H.hash v+        arrayHashesSorted :: Int -> A.Array (Leaf k v) -> [Int]+        arrayHashesSorted s = L.sort . L.map (hashLeafWithSalt s) . A.toList    -- Helper to get 'Leaf's and 'Collision's as a list. toList' :: HashMap k v -> [HashMap k v] -> [HashMap k v]@@ -832,6 +934,18 @@                  Nothing -> insert k v m                  _       -> m {-# INLINABLE difference #-}++-- | /O(n*log m)/ Difference with a combining function. When two equal keys are+-- encountered, the combining function is applied to the values of these keys.+-- If it returns 'Nothing', the element is discarded (proper set difference). If+-- it returns (@'Just' y@), the element is updated with a new value @y@.+differenceWith :: (Eq k, Hashable k) => (v -> w -> Maybe v) -> HashMap k v -> HashMap k w -> HashMap k v+differenceWith f a b = foldlWithKey' go empty a+  where+    go m k v = case lookup k b of+                 Nothing -> insert k v m+                 Just w  -> maybe m (\y -> insert k y m) (f v w)+{-# INLINABLE differenceWith #-}  -- | /O(n*log m)/ Intersection of two maps. Return elements of the first -- map for keys existing in the second.
Data/HashMap/Lazy.hs view
@@ -64,6 +64,7 @@        -- * Difference and intersection     , difference+    , differenceWith     , intersection     , intersectionWith     , intersectionWithKey
Data/HashMap/Strict.hs view
@@ -64,6 +64,7 @@        -- * Difference and intersection     , difference+    , differenceWith     , intersection     , intersectionWith     , intersectionWithKey@@ -98,9 +99,9 @@ import qualified Data.HashMap.Array as A import qualified Data.HashMap.Base as HM import Data.HashMap.Base hiding (-    alter, adjust, fromList, fromListWith, insert, insertWith, intersectionWith,-    intersectionWithKey, map, mapWithKey, mapMaybe, mapMaybeWithKey, singleton,-    update, unionWith, unionWithKey)+    alter, adjust, fromList, fromListWith, insert, insertWith, differenceWith,+    intersectionWith, intersectionWithKey, map, mapWithKey, mapMaybe,+    mapMaybeWithKey, singleton, update, unionWith, unionWithKey) import Data.HashMap.Unsafe (runST)  -- $strictness@@ -393,6 +394,18 @@  ------------------------------------------------------------------------ -- * Difference and intersection++-- | /O(n*log m)/ Difference with a combining function. When two equal keys are+-- encountered, the combining function is applied to the values of these keys.+-- If it returns 'Nothing', the element is discarded (proper set difference). If+-- it returns (@'Just' y@), the element is updated with a new value @y@.+differenceWith :: (Eq k, Hashable k) => (v -> w -> Maybe v) -> HashMap k v -> HashMap k w -> HashMap k v+differenceWith f a b = foldlWithKey' go empty a+  where+    go m k v = case HM.lookup k b of+                 Nothing -> insert k v m+                 Just w  -> maybe m (\y -> insert k y m) (f v w)+{-# INLINABLE differenceWith #-}  -- | /O(n+m)/ Intersection of two maps. If a key occurs in both maps -- the provided function is used to combine the values from the two
Data/HashSet.hs view
@@ -74,7 +74,7 @@  import Control.DeepSeq (NFData(..)) import Data.Data hiding (Typeable)-import Data.HashMap.Base (HashMap, foldrWithKey)+import Data.HashMap.Base (HashMap, foldrWithKey, equalKeys) import Data.Hashable (Hashable(hashWithSalt)) #if __GLASGOW_HASKELL__ >= 711 import Data.Semigroup (Semigroup(..), Monoid(..))@@ -93,6 +93,14 @@ import qualified GHC.Exts as Exts #endif +#if MIN_VERSION_base(4,9,0)+import Data.Functor.Classes+#endif++#if MIN_VERSION_hashable(1,2,5)+import qualified Data.Hashable.Lifted as H+#endif+ -- | A set of values.  A set cannot contain duplicate values. newtype HashSet a = HashSet {       asMap :: HashMap a ()@@ -106,12 +114,15 @@     rnf = rnf . asMap     {-# INLINE rnf #-} -instance (Hashable a, Eq a) => Eq (HashSet a) where-    -- This performs two passes over the tree.-    a == b = foldr f True b && size a == size b-        where f i = (&& i `member` a)+instance (Eq a) => Eq (HashSet a) where+    HashSet a == HashSet b = equalKeys (==) a b     {-# INLINE (==) #-} +#if MIN_VERSION_base(4,9,0)+instance Eq1 HashSet where+    liftEq eq (HashSet a) (HashSet b) = equalKeys eq a b+#endif+ instance Foldable.Foldable HashSet where     foldr = Data.HashSet.foldr     {-# INLINE foldr #-}@@ -140,6 +151,12 @@      readListPrec = readListPrecDefault +#if MIN_VERSION_base(4,9,0)+instance Show1 HashSet where+    liftShowsPrec sp sl d m =+        showsUnaryWith (liftShowsPrec sp sl) "fromList" d (toList m)+#endif+ instance (Show a) => Show (HashSet a) where     showsPrec d m = showParen (d > 10) $       showString "fromList " . shows (toList m)@@ -153,6 +170,11 @@     dataTypeOf _   = hashSetDataType     dataCast1 f    = gcast1 f +#if MIN_VERSION_hashable(1,2,6)+instance H.Hashable1 HashSet where+    liftHashWithSalt h s = H.liftHashWithSalt2 h hashWithSalt s . asMap+#endif+ instance (Hashable a) => Hashable (HashSet a) where     hashWithSalt salt = hashWithSalt salt . asMap @@ -204,7 +226,7 @@ size = H.size . asMap {-# INLINE size #-} --- | /O(min(n,W))/ Return 'True' if the given value is present in this+-- | /O(log n)/ Return 'True' if the given value is present in this -- set, 'False' otherwise. member :: (Eq a, Hashable a) => a -> HashSet a -> Bool member a s = case H.lookup a (asMap s) of@@ -212,12 +234,12 @@                _      -> False {-# INLINABLE member #-} --- | /O(min(n,W))/ Add the specified value to this set.+-- | /O(log n)/ Add the specified value to this set. insert :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a insert a = HashSet . H.insert a () . asMap {-# INLINABLE insert #-} --- | /O(min(n,W))/ Remove the specified value from this set if+-- | /O(log n)/ Remove the specified value from this set if -- present. delete :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a delete a = HashSet . H.delete a . asMap
tests/HashMapProperties.hs view
@@ -54,8 +54,9 @@ pHashable xs is salt =     x == y ==> hashWithSalt salt x === hashWithSalt salt y   where-    ys = shuffle is xs-    x = HM.fromList xs+    xs' = L.nubBy (\(k,_) (k',_) -> k == k') xs+    ys = shuffle is xs'+    x = HM.fromList xs'     y = HM.fromList ys     -- Shuffle the list using indexes in the second     shuffle :: [Int] -> [a] -> [a]@@ -162,6 +163,12 @@ pDifference xs ys = M.difference (M.fromList xs) `eq_`                     HM.difference (HM.fromList xs) $ ys +pDifferenceWith :: [(Key, Int)] -> [(Key, Int)] -> Bool+pDifferenceWith xs ys = M.differenceWith f (M.fromList xs) `eq_`+                        HM.differenceWith f (HM.fromList xs) $ ys+  where+    f x y = if x == 0 then Nothing else Just (x - y)+ pIntersection :: [(Key, Int)] -> [(Key, Int)] -> Bool pIntersection xs ys = M.intersection (M.fromList xs) `eq_`                       HM.intersection (HM.fromList xs) $ ys@@ -283,6 +290,7 @@       ]     , testGroup "difference and intersection"       [ testProperty "difference" pDifference+      , testProperty "differenceWith" pDifferenceWith       , testProperty "intersection" pIntersection       , testProperty "intersectionWith" pIntersectionWith       , testProperty "intersectionWithKey" pIntersectionWithKey
tests/HashSetProperties.hs view
@@ -53,8 +53,9 @@ pHashable xs is salt =     x == y ==> hashWithSalt salt x === hashWithSalt salt y   where-    ys = shuffle is xs-    x = S.fromList xs+    xs' = L.nub xs+    ys = shuffle is xs'+    x = S.fromList xs'     y = S.fromList ys     shuffle idxs = L.map snd                  . L.sortBy (comparing fst)
unordered-containers.cabal view
@@ -1,5 +1,5 @@ name:           unordered-containers-version:        0.2.7.2+version:        0.2.8.0 synopsis:       Efficient hashing-based container types description:   Efficient hashing-based container types.  The containers have been