Hello community,
here is the log from the commit of package ghc-unordered-containers for
openSUSE:Factory checked in at 2017-04-14 13:38:59
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Comparing /work/SRC/openSUSE:Factory/ghc-unordered-containers (Old)
and /work/SRC/openSUSE:Factory/.ghc-unordered-containers.new (New)
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Package is "ghc-unordered-containers"
Fri Apr 14 13:38:59 2017 rev:10 rq:485170 version:0.2.8.0
Changes:
--------
---
/work/SRC/openSUSE:Factory/ghc-unordered-containers/ghc-unordered-containers.changes
2017-01-18 21:44:36.088864755 +0100
+++
/work/SRC/openSUSE:Factory/.ghc-unordered-containers.new/ghc-unordered-containers.changes
2017-04-14 13:39:00.604460824 +0200
@@ -1,0 +2,5 @@
+Mon Mar 27 12:41:23 UTC 2017 - [email protected]
+
+- Update to version 0.2.8.0 with cabal2obs.
+
+-------------------------------------------------------------------
Old:
----
unordered-containers-0.2.7.2.tar.gz
New:
----
unordered-containers-0.2.8.0.tar.gz
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Other differences:
------------------
++++++ ghc-unordered-containers.spec ++++++
--- /var/tmp/diff_new_pack.wDMwpC/_old 2017-04-14 13:39:01.508333079 +0200
+++ /var/tmp/diff_new_pack.wDMwpC/_new 2017-04-14 13:39:01.512332514 +0200
@@ -19,7 +19,7 @@
%global pkg_name unordered-containers
%bcond_with tests
Name: ghc-%{pkg_name}
-Version: 0.2.7.2
+Version: 0.2.8.0
Release: 0
Summary: Efficient hashing-based container types
License: BSD-3-Clause
++++++ unordered-containers-0.2.7.2.tar.gz ->
unordered-containers-0.2.8.0.tar.gz ++++++
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/unordered-containers-0.2.7.2/CHANGES.md
new/unordered-containers-0.2.8.0/CHANGES.md
--- old/unordered-containers-0.2.7.2/CHANGES.md 2016-12-24 04:26:14.000000000
+0100
+++ new/unordered-containers-0.2.8.0/CHANGES.md 2017-03-18 00:38:19.000000000
+0100
@@ -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
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/unordered-containers-0.2.7.2/Data/HashMap/Base.hs
new/unordered-containers-0.2.8.0/Data/HashMap/Base.hs
--- old/unordered-containers-0.2.7.2/Data/HashMap/Base.hs 2016-12-24
04:26:14.000000000 +0100
+++ new/unordered-containers-0.2.8.0/Data/HashMap/Base.hs 2017-03-18
00:38:19.000000000 +0100
@@ -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 &&
+ 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 &&
- 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 _) (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]
@@ -833,6 +935,18 @@
_ -> 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.
intersection :: (Eq k, Hashable k) => HashMap k v -> HashMap k w -> HashMap k v
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/unordered-containers-0.2.7.2/Data/HashMap/Lazy.hs
new/unordered-containers-0.2.8.0/Data/HashMap/Lazy.hs
--- old/unordered-containers-0.2.7.2/Data/HashMap/Lazy.hs 2016-12-24
04:26:14.000000000 +0100
+++ new/unordered-containers-0.2.8.0/Data/HashMap/Lazy.hs 2017-03-18
00:38:19.000000000 +0100
@@ -64,6 +64,7 @@
-- * Difference and intersection
, difference
+ , differenceWith
, intersection
, intersectionWith
, intersectionWithKey
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/unordered-containers-0.2.7.2/Data/HashMap/Strict.hs
new/unordered-containers-0.2.8.0/Data/HashMap/Strict.hs
--- old/unordered-containers-0.2.7.2/Data/HashMap/Strict.hs 2016-12-24
04:26:14.000000000 +0100
+++ new/unordered-containers-0.2.8.0/Data/HashMap/Strict.hs 2017-03-18
00:38:19.000000000 +0100
@@ -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
@@ -394,6 +395,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
-- maps.
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/unordered-containers-0.2.7.2/Data/HashSet.hs
new/unordered-containers-0.2.8.0/Data/HashSet.hs
--- old/unordered-containers-0.2.7.2/Data/HashSet.hs 2016-12-24
04:26:14.000000000 +0100
+++ new/unordered-containers-0.2.8.0/Data/HashSet.hs 2017-03-18
00:38:19.000000000 +0100
@@ -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
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore'
old/unordered-containers-0.2.7.2/tests/HashMapProperties.hs
new/unordered-containers-0.2.8.0/tests/HashMapProperties.hs
--- old/unordered-containers-0.2.7.2/tests/HashMapProperties.hs 2016-12-24
04:26:14.000000000 +0100
+++ new/unordered-containers-0.2.8.0/tests/HashMapProperties.hs 2017-03-18
00:38:19.000000000 +0100
@@ -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
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore'
old/unordered-containers-0.2.7.2/tests/HashSetProperties.hs
new/unordered-containers-0.2.8.0/tests/HashSetProperties.hs
--- old/unordered-containers-0.2.7.2/tests/HashSetProperties.hs 2016-12-24
04:26:14.000000000 +0100
+++ new/unordered-containers-0.2.8.0/tests/HashSetProperties.hs 2017-03-18
00:38:19.000000000 +0100
@@ -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)
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore'
old/unordered-containers-0.2.7.2/unordered-containers.cabal
new/unordered-containers-0.2.8.0/unordered-containers.cabal
--- old/unordered-containers-0.2.7.2/unordered-containers.cabal 2016-12-24
04:26:14.000000000 +0100
+++ new/unordered-containers-0.2.8.0/unordered-containers.cabal 2017-03-18
00:38:19.000000000 +0100
@@ -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
