packages feed

unordered-containers 0.2.18.0 → 0.2.19.0

raw patch · 12 files changed

+330/−186 lines, 12 filesdep ~base

Dependency ranges changed: base

Files

CHANGES.md view
@@ -1,3 +1,15 @@+## [0.2.19.0] – April 2022++* [Make intersections much faster](https://github.com/haskell-unordered-containers/unordered-containers/pull/406)++* [Fix undefined behaviour on 32-bit platforms](https://github.com/haskell-unordered-containers/unordered-containers/pull/413)++* Speed up some array-appending operations: [#407](https://github.com/haskell-unordered-containers/unordered-containers/pull/407), [#409](https://github.com/haskell-unordered-containers/unordered-containers/pull/409)++* [Use MathJax format for complexity annotations](https://github.com/haskell-unordered-containers/unordered-containers/pull/411)++[0.2.19.0]: https://github.com/haskell-unordered-containers/unordered-containers/compare/v0.2.18.0...v0.2.19.0+ ## [0.2.18.0]  * [Fix strictness properties of `Strict.mapMaybe[WithKey]`](https://github.com/haskell-unordered-containers/unordered-containers/pull/385)
Data/HashMap/Internal.hs view
@@ -78,6 +78,7 @@     , intersection     , intersectionWith     , intersectionWithKey+    , intersectionWithKey#        -- * Folds     , foldr'@@ -143,16 +144,17 @@ import Control.DeepSeq            (NFData (..), NFData1 (..), NFData2 (..)) import Control.Monad.ST           (ST, runST) import Data.Bifoldable            (Bifoldable (..))-import Data.Bits                  (complement, popCount, unsafeShiftL,-                                   unsafeShiftR, (.&.), (.|.), countTrailingZeros)+import Data.Bits                  (complement, countTrailingZeros, popCount,+                                   shiftL, unsafeShiftL, unsafeShiftR, (.&.),+                                   (.|.)) import Data.Coerce                (coerce) import Data.Data                  (Constr, Data (..), DataType) import Data.Functor.Classes       (Eq1 (..), Eq2 (..), Ord1 (..), Ord2 (..),                                    Read1 (..), Show1 (..), Show2 (..)) import Data.Functor.Identity      (Identity (..))-import Data.HashMap.Internal.List (isPermutationBy, unorderedCompare) import Data.Hashable              (Hashable) import Data.Hashable.Lifted       (Hashable1, Hashable2)+import Data.HashMap.Internal.List (isPermutationBy, unorderedCompare) import Data.Semigroup             (Semigroup (..), stimesIdempotentMonoid) import GHC.Exts                   (Int (..), Int#, TYPE, (==#)) import GHC.Stack                  (HasCallStack)@@ -163,9 +165,9 @@ import qualified Data.Data                   as Data import qualified Data.Foldable               as Foldable import qualified Data.Functor.Classes        as FC-import qualified Data.HashMap.Internal.Array as A import qualified Data.Hashable               as H import qualified Data.Hashable.Lifted        as H+import qualified Data.HashMap.Internal.Array as A import qualified Data.List                   as List import qualified GHC.Exts                    as Exts import qualified Language.Haskell.TH.Syntax  as TH@@ -546,23 +548,23 @@ ------------------------------------------------------------------------ -- * Construction --- | /O(1)/ Construct an empty map.+-- | \(O(1)\) Construct an empty map. empty :: HashMap k v empty = Empty --- | /O(1)/ Construct a map with a single element.+-- | \(O(1)\) Construct a map with a single element. singleton :: (Hashable k) => k -> v -> HashMap k v singleton k v = Leaf (hash k) (L k v)  ------------------------------------------------------------------------ -- * Basic interface --- | /O(1)/ Return 'True' if this map is empty, 'False' otherwise.+-- | \(O(1)\) Return 'True' if this map is empty, 'False' otherwise. null :: HashMap k v -> Bool null Empty = True null _   = False --- | /O(n)/ Return the number of key-value mappings in this map.+-- | \(O(n)\) Return the number of key-value mappings in this map. size :: HashMap k v -> Int size t = go t 0   where@@ -572,7 +574,7 @@     go (Full ary)            n = A.foldl' (flip go) n ary     go (Collision _ ary)     n = n + A.length ary --- | /O(log n)/ Return 'True' if the specified key is present in the+-- | \(O(\log n)\) Return 'True' if the specified key is present in the -- map, 'False' otherwise. member :: (Eq k, Hashable k) => k -> HashMap k a -> Bool member k m = case lookup k m of@@ -580,7 +582,7 @@     Just _  -> True {-# INLINABLE member #-} --- | /O(log n)/ Return the value to which the specified key is mapped,+-- | \(O(\log n)\) Return the value to which the specified key is mapped, -- or 'Nothing' if this map contains no mapping for the key. lookup :: (Eq k, Hashable k) => k -> HashMap k v -> Maybe v -- GHC does not yet perform a worker-wrapper transformation on@@ -683,7 +685,7 @@         | otherwise = absent (# #) {-# INLINE lookupCont #-} --- | /O(log n)/ Return the value to which the specified key is mapped,+-- | \(O(\log n)\) Return the value to which the specified key is mapped, -- or 'Nothing' if this map contains no mapping for the key. -- -- This is a flipped version of 'lookup'.@@ -694,7 +696,7 @@ {-# INLINE (!?) #-}  --- | /O(log n)/ Return the value to which the specified key is mapped,+-- | \(O(\log n)\) Return the value to which the specified key is mapped, -- or the default value if this map contains no mapping for the key. -- -- @since 0.2.11@@ -707,7 +709,7 @@ {-# INLINABLE findWithDefault #-}  --- | /O(log n)/ Return the value to which the specified key is mapped,+-- | \(O(\log n)\) Return the value to which the specified key is mapped, -- or the default value if this map contains no mapping for the key. -- -- DEPRECATED: lookupDefault is deprecated as of version 0.2.11, replaced@@ -718,7 +720,7 @@ lookupDefault = findWithDefault {-# INLINE lookupDefault #-} --- | /O(log n)/ Return the value to which the specified key is mapped.+-- | \(O(\log n)\) Return the value to which the specified key is mapped. -- Calls 'error' if this map contains no mapping for the key. (!) :: (Eq k, Hashable k, HasCallStack) => HashMap k v -> k -> v (!) m k = case lookup k m of@@ -747,7 +749,7 @@     | otherwise         = BitmapIndexed b ary {-# INLINE bitmapIndexedOrFull #-} --- | /O(log n)/ Associate the specified value with the specified+-- | \(O(\log n)\) Associate the specified value with the specified -- key in this map.  If this map previously contained a mapping for -- the key, the old value is replaced. insert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v@@ -819,17 +821,9 @@         in Full (update32 ary i st')       where i = index h s     go h k x s t@(Collision hy v)-        | h == hy   = Collision h (snocNewLeaf (L k x) v)+        | h == hy   = Collision h (A.snoc v (L k x))         | otherwise =             go h k x s $ BitmapIndexed (mask hy s) (A.singleton t)-      where-        snocNewLeaf :: Leaf k v -> A.Array (Leaf k v) -> A.Array (Leaf k v)-        snocNewLeaf leaf ary = A.run $ do-          let n = A.length ary-          mary <- A.new_ (n + 1)-          A.copy ary 0 mary 0 n-          A.write mary n leaf-          return mary {-# NOINLINE insertNewKey #-}  @@ -940,7 +934,7 @@              | otherwise               = 0 {-# INLINE two #-} --- | /O(log n)/ Associate the value with the key in this map.  If+-- | \(O(\log n)\) Associate the value with the key in this map.  If -- this map previously contained a mapping for the key, the old value -- is replaced by the result of applying the given function to the new -- and old value.  Example:@@ -1008,12 +1002,8 @@ insertModifyingArr x f k0 ary0 = go k0 ary0 0 (A.length ary0)   where     go !k !ary !i !n-        | i >= n = A.run $ do-            -- Not found, append to the end.-            mary <- A.new_ (n + 1)-            A.copy ary 0 mary 0 n-            A.write mary n (L k x)-            return mary+          -- Not found, append to the end.+        | i >= n = A.snoc ary $ L k x         | otherwise = case A.index ary i of             (L kx y) | k == kx   -> case f y of                                       (# y' #) -> if ptrEq y y'@@ -1065,7 +1055,7 @@         | otherwise = go h k x s $ BitmapIndexed (mask hy s) (A.singleton t) {-# INLINABLE unsafeInsertWithKey #-} --- | /O(log n)/ Remove the mapping for the specified key from this map+-- | \(O(\log n)\) Remove the mapping for the specified key from this map -- if present. delete :: (Eq k, Hashable k) => k -> HashMap k v -> HashMap k v delete k m = delete' (hash k) k m@@ -1172,7 +1162,7 @@     go !_ !_ !_ !_ Empty = Empty -- error "Internal error: deleteKeyExists empty" {-# NOINLINE deleteKeyExists #-} --- | /O(log n)/ Adjust the value tied to a given key in this map only+-- | \(O(\log n)\) Adjust the value tied to a given key in this map only -- if it is present. Otherwise, leave the map alone. adjust :: (Eq k, Hashable k) => (v -> v) -> k -> HashMap k v -> HashMap k v -- This operation really likes to leak memory, so using this@@ -1222,7 +1212,7 @@         | otherwise = t {-# INLINABLE adjust# #-} --- | /O(log n)/  The expression @('update' f k map)@ updates the value @x@ at @k@+-- | \(O(\log n)\)  The expression @('update' f k map)@ updates the value @x@ at @k@ -- (if it is in the map). If @(f x)@ is 'Nothing', the element is deleted. -- If it is @('Just' y)@, the key @k@ is bound to the new value @y@. update :: (Eq k, Hashable k) => (a -> Maybe a) -> k -> HashMap k a -> HashMap k a@@ -1230,7 +1220,7 @@ {-# INLINABLE update #-}  --- | /O(log n)/  The expression @('alter' f k map)@ alters the value @x@ at @k@, or+-- | \(O(\log n)\)  The expression @('alter' f k map)@ alters the value @x@ at @k@, or -- absence thereof. -- -- 'alter' can be used to insert, delete, or update a value in a map. In short:@@ -1246,7 +1236,7 @@     Just v  -> insert k v m {-# INLINABLE alter #-} --- | /O(log n)/  The expression @('alterF' f k map)@ alters the value @x@ at+-- | \(O(\log n)\)  The expression @('alterF' f k map)@ alters the value @x@ at -- @k@, or absence thereof. -- --  'alterF' can be used to insert, delete, or update a value in a map.@@ -1391,7 +1381,7 @@            Present v _ -> Just v {-# INLINABLE alterFEager #-} --- | /O(n*log m)/ Inclusion of maps. A map is included in another map if the keys+-- | \(O(n \log m)\) Inclusion of maps. A map is included in another map if the keys -- are subsets and the corresponding values are equal: -- -- > isSubmapOf m1 m2 = keys m1 `isSubsetOf` keys m2 &&@@ -1410,7 +1400,7 @@ isSubmapOf = Exts.inline isSubmapOfBy (==) {-# INLINABLE isSubmapOf #-} --- | /O(n*log m)/ Inclusion of maps with value comparison. A map is included in+-- | \(O(n \log m)\) Inclusion of maps with value comparison. A map is included in -- another map if the keys are subsets and if the comparison function is true -- for the corresponding values: --@@ -1482,7 +1472,7 @@     go _ (Full {}) (BitmapIndexed {}) = False {-# INLINABLE isSubmapOfBy #-} --- | /O(min n m))/ Checks if a bitmap indexed node is a submap of another.+-- | \(O(\min n m))\) Checks if a bitmap indexed node is a submap of another. submapBitmapIndexed :: (HashMap k v1 -> HashMap k v2 -> Bool) -> Bitmap -> A.Array (HashMap k v1) -> Bitmap -> A.Array (HashMap k v2) -> Bool submapBitmapIndexed comp !b1 !ary1 !b2 !ary2 = subsetBitmaps && go 0 0 (b1Orb2 .&. negate b1Orb2)   where@@ -1509,7 +1499,7 @@ ------------------------------------------------------------------------ -- * Combine --- | /O(n+m)/ The union of two maps. If a key occurs in both maps, the+-- | \(O(n+m)\) The union of two maps. If a key occurs in both maps, the -- mapping from the first will be the mapping in the result. -- -- ==== __Examples__@@ -1520,7 +1510,7 @@ union = unionWith const {-# INLINABLE union #-} --- | /O(n+m)/ The union of two maps.  If a key occurs in both maps,+-- | \(O(n+m)\) The union of two maps.  If a key occurs in both maps, -- the provided function (first argument) will be used to compute the -- result. unionWith :: (Eq k, Hashable k) => (v -> v -> v) -> HashMap k v -> HashMap k v@@ -1528,7 +1518,7 @@ unionWith f = unionWithKey (const f) {-# INLINE unionWith #-} --- | /O(n+m)/ The union of two maps.  If a key occurs in both maps,+-- | \(O(n+m)\) The union of two maps.  If a key occurs in both maps, -- the provided function (first argument) will be used to compute the -- result. unionWithKey :: (Eq k, Hashable k) => (k -> v -> v -> v) -> HashMap k v -> HashMap k v@@ -1639,7 +1629,7 @@                 A.write mary i =<< A.indexM ary2 i2                 go (i+1) i1 (i2+1) b'           where-            m = 1 `unsafeShiftL` (countTrailingZeros b)+            m = 1 `unsafeShiftL` countTrailingZeros b             testBit x = x .&. m /= 0             b' = b .&. complement m     go 0 0 0 bCombined@@ -1682,7 +1672,7 @@ ------------------------------------------------------------------------ -- * Transformations --- | /O(n)/ Transform this map by applying a function to every value.+-- | \(O(n)\) Transform this map by applying a function to every value. mapWithKey :: (k -> v1 -> v2) -> HashMap k v1 -> HashMap k v2 mapWithKey f = go   where@@ -1696,7 +1686,7 @@                            A.map' (\ (L k v) -> L k (f k v)) ary {-# INLINE mapWithKey #-} --- | /O(n)/ Transform this map by applying a function to every value.+-- | \(O(n)\) Transform this map by applying a function to every value. map :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2 map f = mapWithKey (const f) {-# INLINE map #-}@@ -1704,7 +1694,7 @@ -- TODO: We should be able to use mutation to create the new -- 'HashMap'. --- | /O(n)/ Perform an 'Applicative' action for each key-value pair+-- | \(O(n)\) Perform an 'Applicative' action for each key-value pair -- in a 'HashMap' and produce a 'HashMap' of all the results. -- -- Note: the order in which the actions occur is unspecified. In particular,@@ -1725,7 +1715,7 @@         Collision h <$> A.traverse' (\ (L k v) -> L k <$> f k v) ary {-# INLINE traverseWithKey #-} --- | /O(n)/.+-- | \(O(n)\). -- @'mapKeys' f s@ is the map obtained by applying @f@ to each key of @s@. -- -- The size of the result may be smaller if @f@ maps two or more distinct@@ -1746,7 +1736,7 @@ ------------------------------------------------------------------------ -- * Difference and intersection --- | /O(n*log m)/ Difference of two maps. Return elements of the first map+-- | \(O(n \log m)\) Difference of two maps. Return elements of the first map -- not existing in the second. difference :: (Eq k, Hashable k) => HashMap k v -> HashMap k w -> HashMap k v difference a b = foldlWithKey' go empty a@@ -1756,7 +1746,7 @@                  _       -> m {-# INLINABLE difference #-} --- | /O(n*log m)/ Difference with a combining function. When two equal keys are+-- | \(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@.@@ -1768,44 +1758,168 @@                  Just w  -> maybe m (\y -> unsafeInsert k y m) (f v w) {-# INLINABLE differenceWith #-} --- | /O(n*log m)/ Intersection of two maps. Return elements of the first+-- | \(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-intersection a b = foldlWithKey' go empty a-  where-    go m k v = case lookup k b of-                 Just _ -> unsafeInsert k v m-                 _      -> m+intersection = Exts.inline intersectionWith const {-# INLINABLE intersection #-} --- | /O(n*log m)/ Intersection of two maps. If a key occurs in both maps+-- | \(O(n \log 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.-intersectionWith :: (Eq k, Hashable k) => (v1 -> v2 -> v3) -> HashMap k v1-                 -> HashMap k v2 -> HashMap k v3-intersectionWith f a b = foldlWithKey' go empty a-  where-    go m k v = case lookup k b of-                 Just w -> unsafeInsert k (f v w) m-                 _      -> m+intersectionWith :: (Eq k, Hashable k) => (v1 -> v2 -> v3) -> HashMap k v1 -> HashMap k v2 -> HashMap k v3+intersectionWith f = Exts.inline intersectionWithKey $ const f {-# INLINABLE intersectionWith #-} --- | /O(n*log m)/ Intersection of two maps. If a key occurs in both maps+-- | \(O(n \log 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.-intersectionWithKey :: (Eq k, Hashable k) => (k -> v1 -> v2 -> v3)-                    -> HashMap k v1 -> HashMap k v2 -> HashMap k v3-intersectionWithKey f a b = foldlWithKey' go empty a-  where-    go m k v = case lookup k b of-                 Just w -> unsafeInsert k (f k v w) m-                 _      -> m+intersectionWithKey :: (Eq k, Hashable k) => (k -> v1 -> v2 -> v3) -> HashMap k v1 -> HashMap k v2 -> HashMap k v3+intersectionWithKey f = intersectionWithKey# $ \k v1 v2 -> (# f k v1 v2 #) {-# INLINABLE intersectionWithKey #-} +intersectionWithKey# :: Eq k => (k -> v1 -> v2 -> (# v3 #)) -> HashMap k v1 -> HashMap k v2 -> HashMap k v3+intersectionWithKey# f = go 0+  where+    -- empty vs. anything+    go !_ _ Empty = Empty+    go _ Empty _ = Empty+    -- leaf vs. anything+    go s (Leaf h1 (L k1 v1)) t2 =+      lookupCont+        (\_ -> Empty)+        (\v _ -> case f k1 v1 v of (# v' #) -> Leaf h1 $ L k1 v')+        h1 k1 s t2+    go s t1 (Leaf h2 (L k2 v2)) =+      lookupCont+        (\_ -> Empty)+        (\v _ -> case f k2 v v2 of (# v' #) -> Leaf h2 $ L k2 v')+        h2 k2 s t1+    -- collision vs. collision+    go _ (Collision h1 ls1) (Collision h2 ls2) = intersectionCollisions f h1 h2 ls1 ls2+    -- branch vs. branch+    go s (BitmapIndexed b1 ary1) (BitmapIndexed b2 ary2) =+      intersectionArrayBy (go (s + bitsPerSubkey)) b1 b2 ary1 ary2+    go s (BitmapIndexed b1 ary1) (Full ary2) =+      intersectionArrayBy (go (s + bitsPerSubkey)) b1 fullNodeMask ary1 ary2+    go s (Full ary1) (BitmapIndexed b2 ary2) =+      intersectionArrayBy (go (s + bitsPerSubkey)) fullNodeMask b2 ary1 ary2+    go s (Full ary1) (Full ary2) =+      intersectionArrayBy (go (s + bitsPerSubkey)) fullNodeMask fullNodeMask ary1 ary2+    -- collision vs. branch+    go s (BitmapIndexed b1 ary1) t2@(Collision h2 _ls2)+      | b1 .&. m2 == 0 = Empty+      | otherwise = go (s + bitsPerSubkey) (A.index ary1 i) t2+      where+        m2 = mask h2 s+        i = sparseIndex b1 m2+    go s t1@(Collision h1 _ls1) (BitmapIndexed b2 ary2)+      | b2 .&. m1 == 0 = Empty+      | otherwise = go (s + bitsPerSubkey) t1 (A.index ary2 i)+      where+        m1 = mask h1 s+        i = sparseIndex b2 m1+    go s (Full ary1) t2@(Collision h2 _ls2) = go (s + bitsPerSubkey) (A.index ary1 i) t2+      where+        i = index h2 s+    go s t1@(Collision h1 _ls1) (Full ary2) = go (s + bitsPerSubkey) t1 (A.index ary2 i)+      where+        i = index h1 s+{-# INLINE intersectionWithKey# #-}++intersectionArrayBy ::+  ( HashMap k v1 ->+    HashMap k v2 ->+    HashMap k v3+  ) ->+  Bitmap ->+  Bitmap ->+  A.Array (HashMap k v1) ->+  A.Array (HashMap k v2) ->+  HashMap k v3+intersectionArrayBy f !b1 !b2 !ary1 !ary2+  | b1 .&. b2 == 0 = Empty+  | otherwise = runST $ do+    mary <- A.new_ $ popCount bIntersect+    -- iterate over nonzero bits of b1 .|. b2+    let go !i !i1 !i2 !b !bFinal+          | b == 0 = pure (i, bFinal)+          | testBit $ b1 .&. b2 = do+            x1 <- A.indexM ary1 i1+            x2 <- A.indexM ary2 i2+            case f x1 x2 of+              Empty -> go i (i1 + 1) (i2 + 1) b' (bFinal .&. complement m)+              _ -> do+                A.write mary i $! f x1 x2+                go (i + 1) (i1 + 1) (i2 + 1) b' bFinal+          | testBit b1 = go i (i1 + 1) i2 b' bFinal+          | otherwise = go i i1 (i2 + 1) b' bFinal+          where+            m = 1 `unsafeShiftL` countTrailingZeros b+            testBit x = x .&. m /= 0+            b' = b .&. complement m+    (len, bFinal) <- go 0 0 0 bCombined bIntersect+    case len of+      0 -> pure Empty+      1 -> A.read mary 0+      _ -> bitmapIndexedOrFull bFinal <$> (A.unsafeFreeze =<< A.shrink mary len)+  where+    bCombined = b1 .|. b2+    bIntersect = b1 .&. b2+{-# INLINE intersectionArrayBy #-}++intersectionCollisions :: Eq k => (k -> v1 -> v2 -> (# v3 #)) -> Hash -> Hash -> A.Array (Leaf k v1) -> A.Array (Leaf k v2) -> HashMap k v3+intersectionCollisions f h1 h2 ary1 ary2+  | h1 == h2 = runST $ do+    mary2 <- A.thaw ary2 0 $ A.length ary2+    mary <- A.new_ $ min (A.length ary1) (A.length ary2)+    let go i j+          | i >= A.length ary1 || j >= A.lengthM mary2 = pure j+          | otherwise = do+            L k1 v1 <- A.indexM ary1 i+            searchSwap k1 j mary2 >>= \case+              Just (L _k2 v2) -> do+                let !(# v3 #) = f k1 v1 v2+                A.write mary j $ L k1 v3+                go (i + 1) (j + 1)+              Nothing -> do+                go (i + 1) j+    len <- go 0 0+    case len of+      0 -> pure Empty+      1 -> Leaf h1 <$> A.read mary 0+      _ -> Collision h1 <$> (A.unsafeFreeze =<< A.shrink mary len)+  | otherwise = Empty+{-# INLINE intersectionCollisions #-}++-- | Say we have+-- @+-- 1 2 3 4+-- @+-- and we search for @3@. Then we can mutate the array to+-- @+-- undefined 2 1 4+-- @+-- We don't actually need to write undefined, we just have to make sure that the next search starts 1 after the current one.+searchSwap :: Eq k => k -> Int -> A.MArray s (Leaf k v) -> ST s (Maybe (Leaf k v))+searchSwap toFind start = go start toFind start+  where+    go i0 k i mary+      | i >= A.lengthM mary = pure Nothing+      | otherwise = do+        l@(L k' _v) <- A.read mary i+        if k == k'+          then do+            A.write mary i =<< A.read mary i0+            pure $ Just l+          else go i0 k (i + 1) mary+{-# INLINE searchSwap #-}++ ------------------------------------------------------------------------ -- * Folds --- | /O(n)/ Reduce this map by applying a binary operator to all+-- | \(O(n)\) Reduce this map by applying a binary operator to all -- elements, using the given starting value (typically the -- left-identity of the operator).  Each application of the operator -- is evaluated before using the result in the next application.@@ -1814,7 +1928,7 @@ foldl' f = foldlWithKey' (\ z _ v -> f z v) {-# INLINE foldl' #-} --- | /O(n)/ Reduce this map by applying a binary operator to all+-- | \(O(n)\) Reduce this map by applying a binary operator to all -- elements, using the given starting value (typically the -- right-identity of the operator).  Each application of the operator -- is evaluated before using the result in the next application.@@ -1823,7 +1937,7 @@ foldr' f = foldrWithKey' (\ _ v z -> f v z) {-# INLINE foldr' #-} --- | /O(n)/ Reduce this map by applying a binary operator to all+-- | \(O(n)\) Reduce this map by applying a binary operator to all -- elements, using the given starting value (typically the -- left-identity of the operator).  Each application of the operator -- is evaluated before using the result in the next application.@@ -1838,7 +1952,7 @@     go z (Collision _ ary)     = A.foldl' (\ z' (L k v) -> f z' k v) z ary {-# INLINE foldlWithKey' #-} --- | /O(n)/ Reduce this map by applying a binary operator to all+-- | \(O(n)\) Reduce this map by applying a binary operator to all -- elements, using the given starting value (typically the -- right-identity of the operator).  Each application of the operator -- is evaluated before using the result in the next application.@@ -1853,21 +1967,21 @@     go (Collision _ ary) !z    = A.foldr' (\ (L k v) z' -> f k v z') z ary {-# INLINE foldrWithKey' #-} --- | /O(n)/ Reduce this map by applying a binary operator to all+-- | \(O(n)\) Reduce this map by applying a binary operator to all -- elements, using the given starting value (typically the -- right-identity of the operator). foldr :: (v -> a -> a) -> a -> HashMap k v -> a foldr f = foldrWithKey (const f) {-# INLINE foldr #-} --- | /O(n)/ Reduce this map by applying a binary operator to all+-- | \(O(n)\) Reduce this map by applying a binary operator to all -- elements, using the given starting value (typically the -- left-identity of the operator). foldl :: (a -> v -> a) -> a -> HashMap k v -> a foldl f = foldlWithKey (\a _k v -> f a v) {-# INLINE foldl #-} --- | /O(n)/ Reduce this map by applying a binary operator to all+-- | \(O(n)\) Reduce this map by applying a binary operator to all -- elements, using the given starting value (typically the -- right-identity of the operator). foldrWithKey :: (k -> v -> a -> a) -> a -> HashMap k v -> a@@ -1880,7 +1994,7 @@     go (Collision _ ary) z     = A.foldr (\ (L k v) z' -> f k v z') z ary {-# INLINE foldrWithKey #-} --- | /O(n)/ Reduce this map by applying a binary operator to all+-- | \(O(n)\) Reduce this map by applying a binary operator to all -- elements, using the given starting value (typically the -- left-identity of the operator). foldlWithKey :: (a -> k -> v -> a) -> a -> HashMap k v -> a@@ -1893,7 +2007,7 @@     go z (Collision _ ary)     = A.foldl (\ z' (L k v) -> f z' k v) z ary {-# INLINE foldlWithKey #-} --- | /O(n)/ Reduce the map by applying a function to each element+-- | \(O(n)\) Reduce the map by applying a function to each element -- and combining the results with a monoid operation. foldMapWithKey :: Monoid m => (k -> v -> m) -> HashMap k v -> m foldMapWithKey f = go@@ -1908,7 +2022,7 @@ ------------------------------------------------------------------------ -- * Filter --- | /O(n)/ Transform this map by applying a function to every value+-- | \(O(n)\) Transform this map by applying a function to every value --   and retaining only some of them. mapMaybeWithKey :: (k -> v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2 mapMaybeWithKey f = filterMapAux onLeaf onColl@@ -1919,13 +2033,13 @@                        | otherwise = Nothing {-# INLINE mapMaybeWithKey #-} --- | /O(n)/ Transform this map by applying a function to every value+-- | \(O(n)\) Transform this map by applying a function to every value --   and retaining only some of them. mapMaybe :: (v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2 mapMaybe f = mapMaybeWithKey (const f) {-# INLINE mapMaybe #-} --- | /O(n)/ Filter this map by retaining only elements satisfying a+-- | \(O(n)\) Filter this map by retaining only elements satisfying a -- predicate. filterWithKey :: forall k v. (k -> v -> Bool) -> HashMap k v -> HashMap k v filterWithKey pred = filterMapAux onLeaf onColl@@ -2006,7 +2120,7 @@             | otherwise = step ary mary (i+1) j n {-# INLINE filterMapAux #-} --- | /O(n)/ Filter this map by retaining only elements which values+-- | \(O(n)\) Filter this map by retaining only elements which values -- satisfy a predicate. filter :: (v -> Bool) -> HashMap k v -> HashMap k v filter p = filterWithKey (\_ v -> p v)@@ -2018,13 +2132,13 @@ -- TODO: Improve fusion rules by modelled them after the Prelude ones -- on lists. --- | /O(n)/ Return a list of this map's keys.  The list is produced+-- | \(O(n)\) Return a list of this map's keys.  The list is produced -- lazily. keys :: HashMap k v -> [k] keys = List.map fst . toList {-# INLINE keys #-} --- | /O(n)/ Return a list of this map's values.  The list is produced+-- | \(O(n)\) Return a list of this map's values.  The list is produced -- lazily. elems :: HashMap k v -> [v] elems = List.map snd . toList@@ -2033,19 +2147,19 @@ ------------------------------------------------------------------------ -- ** Lists --- | /O(n)/ Return a list of this map's elements.  The list is+-- | \(O(n)\) Return a list of this map's elements.  The list is -- produced lazily. The order of its elements is unspecified. toList :: HashMap k v -> [(k, v)] toList t = Exts.build (\ c z -> foldrWithKey (curry c) z t) {-# INLINE toList #-} --- | /O(n)/ Construct a map with the supplied mappings.  If the list+-- | \(O(n)\) Construct a map with the supplied mappings.  If the list -- contains duplicate mappings, the later mappings take precedence. fromList :: (Eq k, Hashable k) => [(k, v)] -> HashMap k v fromList = List.foldl' (\ m (k, v) -> unsafeInsert k v m) empty {-# INLINABLE fromList #-} --- | /O(n*log n)/ Construct a map from a list of elements.  Uses+-- | \(O(n \log n)\) Construct a map from a list of elements.  Uses -- the provided function @f@ to merge duplicate entries with -- @(f newVal oldVal)@. --@@ -2079,7 +2193,7 @@ fromListWith f = List.foldl' (\ m (k, v) -> unsafeInsertWith f k v m) empty {-# INLINE fromListWith #-} --- | /O(n*log n)/ Construct a map from a list of elements.  Uses+-- | \(O(n \log n)\) Construct a map from a list of elements.  Uses -- the provided function to merge duplicate entries. -- -- === Examples@@ -2112,7 +2226,7 @@ ------------------------------------------------------------------------ -- Array operations --- | /O(n)/ Look up the value associated with the given key in an+-- | \(O(n)\) Look up the value associated with the given key in an -- array. lookupInArrayCont ::   forall rep (r :: TYPE rep) k v.@@ -2128,7 +2242,7 @@                 | otherwise -> go k ary (i+1) n {-# INLINE lookupInArrayCont #-} --- | /O(n)/ Lookup the value associated with the given key in this+-- | \(O(n)\) Lookup the value associated with the given key in this -- array.  Returns 'Nothing' if the key wasn't found. indexOf :: Eq k => k -> A.Array (Leaf k v) -> Maybe Int indexOf k0 ary0 = go k0 ary0 0 (A.length ary0)@@ -2164,12 +2278,8 @@ updateOrSnocWithKey f k0 v0 ary0 = go k0 v0 ary0 0 (A.length ary0)   where     go !k v !ary !i !n-        | i >= n = A.run $ do-            -- Not found, append to the end.-            mary <- A.new_ (n + 1)-            A.copy ary 0 mary 0 n-            A.write mary n (L k v)-            return mary+        -- Not found, append to the end.+        | i >= n = A.snoc ary $ L k v         | L kx y <- A.index ary i         , k == kx         , (# v2 #) <- f k v y@@ -2209,7 +2319,7 @@     return mary {-# INLINABLE updateOrConcatWithKey #-} --- | /O(n*m)/ Check if the first array is a subset of the second array.+-- | \(O(n*m)\) Check if the first array is a subset of the second array. subsetArray :: Eq k => (v1 -> v2 -> Bool) -> A.Array (Leaf k v1) -> A.Array (Leaf k v2) -> Bool subsetArray cmpV ary1 ary2 = A.length ary1 <= A.length ary2 && A.all inAry2 ary1   where@@ -2219,12 +2329,12 @@ ------------------------------------------------------------------------ -- Manually unrolled loops --- | /O(n)/ Update the element at the given position in this array.+-- | \(O(n)\) Update the element at the given position in this array. update32 :: A.Array e -> Int -> e -> A.Array e update32 ary idx b = runST (update32M ary idx b) {-# INLINE update32 #-} --- | /O(n)/ Update the element at the given position in this array.+-- | \(O(n)\) Update the element at the given position in this array. update32M :: A.Array e -> Int -> e -> ST s (A.Array e) update32M ary idx b = do     mary <- clone ary@@ -2232,7 +2342,7 @@     A.unsafeFreeze mary {-# INLINE update32M #-} --- | /O(n)/ Update the element at the given position in this array, by applying a function to it.+-- | \(O(n)\) Update the element at the given position in this array, by applying a function to it. update32With' :: A.Array e -> Int -> (e -> e) -> A.Array e update32With' ary idx f   | (# x #) <- A.index# ary idx@@ -2273,7 +2383,9 @@  -- | A bitmask with the 'bitsPerSubkey' least significant bits set. fullNodeMask :: Bitmap-fullNodeMask = complement (complement 0 `unsafeShiftL` maxChildren)+-- This needs to use 'shiftL' instead of 'unsafeShiftL', to avoid UB.+-- See issue #412.+fullNodeMask = complement (complement 0 `shiftL` maxChildren) {-# INLINE fullNodeMask #-}  -- | Check if two the two arguments are the same value.  N.B. This
Data/HashMap/Internal/Array.hs view
@@ -34,6 +34,7 @@     , new_     , singleton     , singletonM+    , snoc     , pair        -- * Basic interface@@ -76,6 +77,7 @@     , toList     , fromList     , fromList'+    , shrink     ) where  import Control.Applicative (liftA2)@@ -95,6 +97,7 @@ import Prelude             hiding (all, filter, foldMap, foldl, foldr, length,                             map, read, traverse) +import qualified GHC.Exts                   as Exts import qualified Language.Haskell.TH.Syntax as TH #if defined(ASSERTS) import qualified Prelude@@ -204,6 +207,20 @@ new_ :: Int -> ST s (MArray s a) new_ n = new n undefinedElem +-- | When 'Exts.shrinkSmallMutableArray#' is available, the returned array is the same as the array given, as it is shrunk in place.+-- Otherwise a copy is made.+shrink :: MArray s a -> Int -> ST s (MArray s a)+#if __GLASGOW_HASKELL__ >= 810+shrink mary _n@(I# n#) =+  CHECK_GT("shrink", _n, (0 :: Int))+  CHECK_LE("shrink", _n, (lengthM mary))+  ST $ \s -> case Exts.shrinkSmallMutableArray# (unMArray mary) n# s of+    s' -> (# s', mary #)+#else+shrink mary n = cloneM mary 0 n+#endif +{-# INLINE shrink #-}+ singleton :: a -> Array a singleton x = runST (singletonM x) {-# INLINE singleton #-}@@ -212,6 +229,15 @@ singletonM x = new 1 x >>= unsafeFreeze {-# INLINE singletonM #-} +snoc :: Array a -> a -> Array a+snoc ary x = run $ do+  mary <- new (n + 1) x+  copy ary 0 mary 0 n+  pure mary+  where+    n = length ary+{-# INLINE snoc #-}+ pair :: a -> a -> Array a pair x y = run $ do     ary <- new 2 x@@ -297,13 +323,13 @@ trim mary n = cloneM mary 0 n >>= unsafeFreeze {-# INLINE trim #-} --- | /O(n)/ Insert an element at the given position in this array,+-- | \(O(n)\) Insert an element at the given position in this array, -- increasing its size by one. insert :: Array e -> Int -> e -> Array e insert ary idx b = runST (insertM ary idx b) {-# INLINE insert #-} --- | /O(n)/ Insert an element at the given position in this array,+-- | \(O(n)\) Insert an element at the given position in this array, -- increasing its size by one. insertM :: Array e -> Int -> e -> ST s (Array e) insertM ary idx b =@@ -315,12 +341,12 @@   where !count = length ary {-# INLINE insertM #-} --- | /O(n)/ Update the element at the given position in this array.+-- | \(O(n)\) Update the element at the given position in this array. update :: Array e -> Int -> e -> Array e update ary idx b = runST (updateM ary idx b) {-# INLINE update #-} --- | /O(n)/ Update the element at the given position in this array.+-- | \(O(n)\) Update the element at the given position in this array. updateM :: Array e -> Int -> e -> ST s (Array e) updateM ary idx b =     CHECK_BOUNDS("updateM", count, idx)@@ -330,7 +356,7 @@   where !count = length ary {-# INLINE updateM #-} --- | /O(n)/ Update the element at the given positio in this array, by+-- | \(O(n)\) Update the element at the given positio in this array, by -- applying a function to it.  Evaluates the element to WHNF before -- inserting it into the array. updateWith' :: Array e -> Int -> (e -> e) -> Array e@@ -339,7 +365,7 @@   = update ary idx $! f x {-# INLINE updateWith' #-} --- | /O(1)/ Update the element at the given position in this array,+-- | \(O(1)\) Update the element at the given position in this array, -- without copying. unsafeUpdateM :: Array e -> Int -> e -> ST s () unsafeUpdateM ary idx b =@@ -418,13 +444,13 @@             (# s2, mary# #) -> (# s2, MArray mary# #) {-# INLINE thaw #-} --- | /O(n)/ Delete an element at the given position in this array,+-- | \(O(n)\) Delete an element at the given position in this array, -- decreasing its size by one. delete :: Array e -> Int -> Array e delete ary idx = runST (deleteM ary idx) {-# INLINE delete #-} --- | /O(n)/ Delete an element at the given position in this array,+-- | \(O(n)\) Delete an element at the given position in this array, -- decreasing its size by one. deleteM :: Array e -> Int -> ST s (Array e) deleteM ary idx = do
Data/HashMap/Internal/Strict.hs view
@@ -38,7 +38,7 @@ -- especially when key comparison is expensive, as in the case of -- strings. ----- Many operations have a average-case complexity of /O(log n)/.  The+-- Many operations have a average-case complexity of \(O(\log n)\).  The -- implementation uses a large base (i.e. 32) so in practice these -- operations are constant time. module Data.HashMap.Internal.Strict@@ -128,16 +128,17 @@ import Data.Coerce           (coerce) import Data.Functor.Identity (Identity (..)) -- See Note [Imports from Data.HashMap.Internal]+import Data.Hashable         (Hashable) import Data.HashMap.Internal (Hash, HashMap (..), Leaf (..), LookupRes (..),                               bitsPerSubkey, fullNodeMask, hash, index, mask,                               ptrEq, sparseIndex)-import Data.Hashable         (Hashable) import Prelude               hiding (lookup, map)  -- See Note [Imports from Data.HashMap.Internal] import qualified Data.HashMap.Internal       as HM import qualified Data.HashMap.Internal.Array as A import qualified Data.List                   as List+import qualified GHC.Exts                    as Exts  {- Note [Imports from Data.HashMap.Internal]@@ -164,21 +165,21 @@ ------------------------------------------------------------------------ -- * Construction --- | /O(1)/ Construct a map with a single element.+-- | \(O(1)\) Construct a map with a single element. singleton :: (Hashable k) => k -> v -> HashMap k v singleton k !v = HM.singleton k v  ------------------------------------------------------------------------ -- * Basic interface --- | /O(log n)/ Associate the specified value with the specified+-- | \(O(\log n)\) Associate the specified value with the specified -- key in this map.  If this map previously contained a mapping for -- the key, the old value is replaced. insert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v insert k !v = HM.insert k v {-# INLINABLE insert #-} --- | /O(log n)/ Associate the value with the key in this map.  If+-- | \(O(\log n)\) Associate the value with the key in this map.  If -- this map previously contained a mapping for the key, the old value -- is replaced by the result of applying the given function to the new -- and old value.  Example:@@ -259,7 +260,7 @@         | otherwise = go h k x s $ BitmapIndexed (mask hy s) (A.singleton t) {-# INLINABLE unsafeInsertWithKey #-} --- | /O(log n)/ Adjust the value tied to a given key in this map only+-- | \(O(\log n)\) Adjust the value tied to a given key in this map only -- if it is present. Otherwise, leave the map alone. adjust :: (Eq k, Hashable k) => (v -> v) -> k -> HashMap k v -> HashMap k v adjust f k0 m0 = go h0 k0 0 m0@@ -288,14 +289,14 @@         | otherwise = t {-# INLINABLE adjust #-} --- | /O(log n)/  The expression @('update' f k map)@ updates the value @x@ at @k@+-- | \(O(\log n)\)  The expression @('update' f k map)@ updates the value @x@ at @k@ -- (if it is in the map). If @(f x)@ is 'Nothing', the element is deleted. -- If it is @('Just' y)@, the key @k@ is bound to the new value @y@. update :: (Eq k, Hashable k) => (a -> Maybe a) -> k -> HashMap k a -> HashMap k a update f = alter (>>= f) {-# INLINABLE update #-} --- | /O(log n)/  The expression @('alter' f k map)@ alters the value @x@ at @k@, or+-- | \(O(\log n)\)  The expression @('alter' f k map)@ alters the value @x@ at @k@, or -- absence thereof. -- -- 'alter' can be used to insert, delete, or update a value in a map. In short:@@ -310,7 +311,7 @@     Just v  -> insert k v m {-# INLINABLE alter #-} --- | /O(log n)/  The expression (@'alterF' f k map@) alters the value @x@ at+-- | \(O(\log n)\)  The expression (@'alterF' f k map@) alters the value @x@ at -- @k@, or absence thereof. -- -- 'alterF' can be used to insert, delete, or update a value in a map.@@ -436,14 +437,14 @@ ------------------------------------------------------------------------ -- * Combine --- | /O(n+m)/ The union of two maps.  If a key occurs in both maps,+-- | \(O(n+m)\) The union of two maps.  If a key occurs in both maps, -- the provided function (first argument) will be used to compute the result. unionWith :: (Eq k, Hashable k) => (v -> v -> v) -> HashMap k v -> HashMap k v           -> HashMap k v unionWith f = unionWithKey (const f) {-# INLINE unionWith #-} --- | /O(n+m)/ The union of two maps.  If a key occurs in both maps,+-- | \(O(n+m)\) The union of two maps.  If a key occurs in both maps, -- the provided function (first argument) will be used to compute the result. unionWithKey :: (Eq k, Hashable k) => (k -> v -> v -> v) -> HashMap k v -> HashMap k v           -> HashMap k v@@ -532,7 +533,7 @@ ------------------------------------------------------------------------ -- * Transformations --- | /O(n)/ Transform this map by applying a function to every value.+-- | \(O(n)\) Transform this map by applying a function to every value. mapWithKey :: (k -> v1 -> v2) -> HashMap k v1 -> HashMap k v2 mapWithKey f = go   where@@ -544,7 +545,7 @@         Collision h $ A.map' (\ (L k v) -> let !v' = f k v in L k v') ary {-# INLINE mapWithKey #-} --- | /O(n)/ Transform this map by applying a function to every value.+-- | \(O(n)\) Transform this map by applying a function to every value. map :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2 map f = mapWithKey (const f) {-# INLINE map #-}@@ -553,7 +554,7 @@ ------------------------------------------------------------------------ -- * Filter --- | /O(n)/ Transform this map by applying a function to every value+-- | \(O(n)\) Transform this map by applying a function to every value --   and retaining only some of them. mapMaybeWithKey :: (k -> v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2 mapMaybeWithKey f = HM.filterMapAux onLeaf onColl@@ -564,13 +565,13 @@                        | otherwise = Nothing {-# INLINE mapMaybeWithKey #-} --- | /O(n)/ Transform this map by applying a function to every value+-- | \(O(n)\) Transform this map by applying a function to every value --   and retaining only some of them. mapMaybe :: (v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2 mapMaybe f = mapMaybeWithKey (const f) {-# INLINE mapMaybe #-} --- | /O(n)/ Perform an 'Applicative' action for each key-value pair+-- | \(O(n)\) Perform an 'Applicative' action for each key-value pair -- in a 'HashMap' and produce a 'HashMap' of all the results. Each 'HashMap' -- will be strict in all its values. --@@ -599,7 +600,7 @@ ------------------------------------------------------------------------ -- * Difference and intersection --- | /O(n*log m)/ Difference with a combining function. When two equal keys are+-- | \(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@.@@ -611,41 +612,33 @@                  Just w  -> maybe m (\ !y -> HM.unsafeInsert k y m) (f v w) {-# INLINABLE differenceWith #-} --- | /O(n+m)/ Intersection of two maps. If a key occurs in both maps+-- | \(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. intersectionWith :: (Eq k, Hashable k) => (v1 -> v2 -> v3) -> HashMap k v1                  -> HashMap k v2 -> HashMap k v3-intersectionWith f a b = HM.foldlWithKey' go HM.empty a-  where-    go m k v = case HM.lookup k b of-                 Just w -> let !x = f v w in HM.unsafeInsert k x m-                 _      -> m+intersectionWith f = Exts.inline intersectionWithKey $ const f {-# INLINABLE intersectionWith #-} --- | /O(n+m)/ Intersection of two maps. If a key occurs in both maps+-- | \(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. intersectionWithKey :: (Eq k, Hashable k) => (k -> v1 -> v2 -> v3)                     -> HashMap k v1 -> HashMap k v2 -> HashMap k v3-intersectionWithKey f a b = HM.foldlWithKey' go HM.empty a-  where-    go m k v = case HM.lookup k b of-                 Just w -> let !x = f k v w in HM.unsafeInsert k x m-                 _      -> m+intersectionWithKey f = HM.intersectionWithKey# $ \k v1 v2 -> let !v3 = f k v1 v2 in (# v3 #) {-# INLINABLE intersectionWithKey #-}  ------------------------------------------------------------------------ -- ** Lists --- | /O(n*log n)/ Construct a map with the supplied mappings.  If the+-- | \(O(n \log n)\) Construct a map with the supplied mappings.  If the -- list contains duplicate mappings, the later mappings take -- precedence. fromList :: (Eq k, Hashable k) => [(k, v)] -> HashMap k v fromList = List.foldl' (\ m (k, !v) -> HM.unsafeInsert k v m) HM.empty {-# INLINABLE fromList #-} --- | /O(n*log n)/ Construct a map from a list of elements.  Uses+-- | \(O(n \log n)\) Construct a map from a list of elements.  Uses -- the provided function @f@ to merge duplicate entries with -- @(f newVal oldVal)@. --@@ -679,7 +672,7 @@ fromListWith f = List.foldl' (\ m (k, v) -> unsafeInsertWith f k v m) HM.empty {-# INLINE fromListWith #-} --- | /O(n*log n)/ Construct a map from a list of elements.  Uses+-- | \(O(n \log n)\) Construct a map from a list of elements.  Uses -- the provided function to merge duplicate entries. -- -- === Examples@@ -742,13 +735,8 @@ updateOrSnocWithKey f k0 v0 ary0 = go k0 v0 ary0 0 (A.length ary0)   where     go !k v !ary !i !n-        | i >= n = A.run $ do-            -- Not found, append to the end.-            mary <- A.new_ (n + 1)-            A.copy ary 0 mary 0 n-            let !l = v `seq` L k v-            A.write mary n l-            return mary+        -- Not found, append to the end.+        | i >= n = A.snoc ary $! L k $! v         | otherwise = case A.index ary i of             (L kx y) | k == kx   -> let !v' = f k v y in A.update ary i (L k v')                      | otherwise -> go k v ary (i+1) n
Data/HashMap/Lazy.hs view
@@ -19,7 +19,7 @@ -- especially when key comparison is expensive, as in the case of -- strings. ----- Many operations have a average-case complexity of /O(log n)/.  The+-- Many operations have a average-case complexity of \(O(\log n)\).  The -- implementation uses a large base (i.e. 32) so in practice these -- operations are constant time. module Data.HashMap.Lazy
Data/HashMap/Strict.hs view
@@ -18,7 +18,7 @@ -- especially when key comparison is expensive, as in the case of -- strings. ----- Many operations have a average-case complexity of /O(log n)/.  The+-- Many operations have a average-case complexity of \(O(\log n)\).  The -- implementation uses a large base (i.e. 16) so in practice these -- operations are constant time. module Data.HashMap.Strict
Data/HashSet.hs view
@@ -86,7 +86,7 @@ especially when value comparisons are expensive, as in the case of strings. -Many operations have a average-case complexity of /O(log n)/.  The+Many operations have a average-case complexity of \(O(\log n)\).  The implementation uses a large base (i.e. 16) so in practice these operations are constant time. -}
Data/HashSet/Internal.hs view
@@ -36,7 +36,7 @@ -- especially when value comparison is expensive, as in the case of -- strings. ----- Many operations have a average-case complexity of /O(log n)/.  The+-- Many operations have a average-case complexity of \(O(\log n)\).  The -- implementation uses a large base (i.e. 32) so in practice these -- operations are constant time. @@ -93,10 +93,10 @@ import Control.DeepSeq       (NFData (..), NFData1 (..), liftRnf2) import Data.Data             (Constr, Data (..), DataType) import Data.Functor.Classes-import Data.HashMap.Internal (HashMap, equalKeys, equalKeys1, foldMapWithKey,-                              foldlWithKey, foldrWithKey) import Data.Hashable         (Hashable (hashWithSalt)) import Data.Hashable.Lifted  (Hashable1 (..), Hashable2 (..))+import Data.HashMap.Internal (HashMap, equalKeys, equalKeys1, foldMapWithKey,+                              foldlWithKey, foldrWithKey) import Data.Semigroup        (Semigroup (..), stimesIdempotentMonoid) import Prelude               hiding (filter, foldl, foldr, map, null) import Text.Read@@ -177,7 +177,7 @@  -- | '<>' = 'union' ----- /O(n+m)/+-- \(O(n+m)\) -- -- To obtain good performance, the smaller set must be presented as -- the first argument.@@ -196,7 +196,7 @@ -- -- 'mappend' = 'union' ----- /O(n+m)/+-- \(O(n+m)\) -- -- To obtain good performance, the smaller set must be presented as -- the first argument.@@ -247,14 +247,14 @@ hashSetDataType :: DataType hashSetDataType = Data.mkDataType "Data.HashSet.Internal.HashSet" [fromListConstr] --- | /O(1)/ Construct an empty set.+-- | \(O(1)\) Construct an empty set. -- -- >>> HashSet.empty -- fromList [] empty :: HashSet a empty = HashSet H.empty --- | /O(1)/ Construct a set with a single element.+-- | \(O(1)\) Construct a set with a single element. -- -- >>> HashSet.singleton 1 -- fromList [1]@@ -262,21 +262,21 @@ singleton a = HashSet (H.singleton a ()) {-# INLINABLE singleton #-} --- | /O(1)/ Convert to set to the equivalent 'HashMap' with @()@ values.+-- | \(O(1)\) Convert to set to the equivalent 'HashMap' with @()@ values. -- -- >>> HashSet.toMap (HashSet.singleton 1) -- fromList [(1,())] toMap :: HashSet a -> HashMap a () toMap = asMap --- | /O(1)/ Convert from the equivalent 'HashMap' with @()@ values.+-- | \(O(1)\) Convert from the equivalent 'HashMap' with @()@ values. -- -- >>> HashSet.fromMap (HashMap.singleton 1 ()) -- fromList [1] fromMap :: HashMap a () -> HashSet a fromMap = HashSet --- | /O(n)/ Produce a 'HashSet' of all the keys in the given 'HashMap'.+-- | \(O(n)\) Produce a 'HashSet' of all the keys in the given 'HashMap'. -- -- >>> HashSet.keysSet (HashMap.fromList [(1, "a"), (2, "b")] -- fromList [1,2]@@ -285,7 +285,7 @@ keysSet :: HashMap k a -> HashSet k keysSet m = fromMap (() <$ m) --- | /O(n*log m)/ Inclusion of sets.+-- | \(O(n \log m)\) Inclusion of sets. -- -- ==== __Examples__ --@@ -299,7 +299,7 @@ isSubsetOf :: (Eq a, Hashable a) => HashSet a -> HashSet a -> Bool isSubsetOf s1 s2 = H.isSubmapOfBy (\_ _ -> True) (asMap s1) (asMap s2) --- | /O(n+m)/ Construct a set containing all elements from both sets.+-- | \(O(n+m)\) Construct a set containing all elements from both sets. -- -- To obtain good performance, the smaller set must be presented as -- the first argument.@@ -317,7 +317,7 @@ unions = List.foldl' union empty {-# INLINE unions #-} --- | /O(1)/ Return 'True' if this set is empty, 'False' otherwise.+-- | \(O(1)\) Return 'True' if this set is empty, 'False' otherwise. -- -- >>> HashSet.null HashSet.empty -- True@@ -327,7 +327,7 @@ null = H.null . asMap {-# INLINE null #-} --- | /O(n)/ Return the number of elements in this set.+-- | \(O(n)\) Return the number of elements in this set. -- -- >>> HashSet.size HashSet.empty -- 0@@ -337,7 +337,7 @@ size = H.size . asMap {-# INLINE size #-} --- | /O(log n)/ 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. -- -- >>> HashSet.member 1 (Hashset.fromList [1,2,3])@@ -350,7 +350,7 @@                _      -> False {-# INLINABLE member #-} --- | /O(log n)/ Add the specified value to this set.+-- | \(O(\log n)\) Add the specified value to this set. -- -- >>> HashSet.insert 1 HashSet.empty -- fromList [1]@@ -358,7 +358,7 @@ insert a = HashSet . H.insert a () . asMap {-# INLINABLE insert #-} --- | /O(log n)/ Remove the specified value from this set if present.+-- | \(O(\log n)\) Remove the specified value from this set if present. -- -- >>> HashSet.delete 1 (HashSet.fromList [1,2,3]) -- fromList [2,3]@@ -368,7 +368,7 @@ delete a = HashSet . H.delete a . asMap {-# INLINABLE delete #-} --- | /O(n)/ Transform this set by applying a function to every value.+-- | \(O(n)\) Transform this set by applying a function to every value. -- The resulting set may be smaller than the source. -- -- >>> HashSet.map show (HashSet.fromList [1,2,3])@@ -377,7 +377,7 @@ map f = fromList . List.map f . toList {-# INLINE map #-} --- | /O(n)/ Difference of two sets. Return elements of the first set+-- | \(O(n)\) Difference of two sets. Return elements of the first set -- not existing in the second. -- -- >>> HashSet.difference (HashSet.fromList [1,2,3]) (HashSet.fromList [2,3,4])@@ -386,7 +386,7 @@ difference (HashSet a) (HashSet b) = HashSet (H.difference a b) {-# INLINABLE difference #-} --- | /O(n)/ Intersection of two sets. Return elements present in both+-- | \(O(n)\) Intersection of two sets. Return elements present in both -- the first set and the second. -- -- >>> HashSet.intersection (HashSet.fromList [1,2,3]) (HashSet.fromList [2,3,4])@@ -395,7 +395,7 @@ intersection (HashSet a) (HashSet b) = HashSet (H.intersection a b) {-# INLINABLE intersection #-} --- | /O(n)/ Reduce this set by applying a binary operator to all+-- | \(O(n)\) Reduce this set by applying a binary operator to all -- elements, using the given starting value (typically the -- left-identity of the operator).  Each application of the operator -- is evaluated before before using the result in the next@@ -405,7 +405,7 @@   where g z k _ = f z k {-# INLINE foldl' #-} --- | /O(n)/ Reduce this set by applying a binary operator to all+-- | \(O(n)\) Reduce this set by applying a binary operator to all -- elements, using the given starting value (typically the -- right-identity of the operator). Each application of the operator -- is evaluated before before using the result in the next@@ -415,7 +415,7 @@   where g k _ z = f k z {-# INLINE foldr' #-} --- | /O(n)/ Reduce this set by applying a binary operator to all+-- | \(O(n)\) Reduce this set by applying a binary operator to all -- elements, using the given starting value (typically the -- right-identity of the operator). foldr :: (b -> a -> a) -> a -> HashSet b -> a@@ -423,7 +423,7 @@   where g k _ z = f k z {-# INLINE foldr #-} --- | /O(n)/ Reduce this set by applying a binary operator to all+-- | \(O(n)\) Reduce this set by applying a binary operator to all -- elements, using the given starting value (typically the -- left-identity of the operator). foldl :: (a -> b -> a) -> a -> HashSet b -> a@@ -431,20 +431,20 @@   where g z k _ = f z k {-# INLINE foldl #-} --- | /O(n)/ Filter this set by retaining only elements satisfying a+-- | \(O(n)\) Filter this set by retaining only elements satisfying a -- predicate. filter :: (a -> Bool) -> HashSet a -> HashSet a filter p = HashSet . H.filterWithKey q . asMap   where q k _ = p k {-# INLINE filter #-} --- | /O(n)/ Return a list of this set's elements.  The list is+-- | \(O(n)\) Return a list of this set's elements.  The list is -- produced lazily. toList :: HashSet a -> [a] toList t = Exts.build (\ c z -> foldrWithKey (const . c) z (asMap t)) {-# INLINE toList #-} --- | /O(n*min(W, n))/ Construct a set from a list of elements.+-- | \(O(n \min(W, n))\) Construct a set from a list of elements. fromList :: (Eq a, Hashable a) => [a] -> HashSet a fromList = HashSet . List.foldl' (\ m k -> H.insert k () m) H.empty {-# INLINE fromList #-}
benchmarks/Benchmarks.hs view
@@ -318,13 +318,17 @@             [ bench "Int" $ whnf (HM.union hmi) hmi2             , bench "ByteString" $ whnf (HM.union hmbs) hmbsSubset             ]+          +          , bgroup "intersection"+            [ bench "Int" $ whnf (HM.intersection hmi) hmi2+            , bench "ByteString" $ whnf (HM.intersection hmbs) hmbsSubset+            ]              -- Transformations           , bench "map" $ whnf (HM.map (\ v -> v + 1)) hmi              -- * Difference and intersection           , bench "difference" $ whnf (HM.difference hmi) hmi2-          , bench "intersection" $ whnf (HM.intersection hmi) hmi2              -- Folds           , bench "foldl'" $ whnf (HM.foldl' (+) 0) hmi
tests/Properties/HashMapLazy.hs view
@@ -42,7 +42,7 @@  -- Key type that generates more hash collisions. newtype Key = K { unK :: Int }-            deriving (Arbitrary, Eq, Ord, Read, Show)+            deriving (Arbitrary, Eq, Ord, Read, Show, Num)  instance Hashable Key where     hashWithSalt salt k = hashWithSalt salt (unK k) `mod` 20@@ -318,8 +318,10 @@     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+pIntersection xs ys = +  M.intersection (M.fromList xs)+    `eq_` HM.intersection (HM.fromList xs)+    $ ys  pIntersectionWith :: [(Key, Int)] -> [(Key, Int)] -> Bool pIntersectionWith xs ys = M.intersectionWith (-) (M.fromList xs) `eq_`
tests/Strictness.hs view
@@ -8,8 +8,8 @@ import Control.Arrow                (second) import Control.Monad                (guard) import Data.Foldable                (foldl')-import Data.HashMap.Strict          (HashMap) import Data.Hashable                (Hashable (hashWithSalt))+import Data.HashMap.Strict          (HashMap) import Data.Maybe                   (fromMaybe, isJust) import Test.ChasingBottoms.IsBottom import Test.QuickCheck              (Arbitrary (arbitrary), Property, (.&&.),
unordered-containers.cabal view
@@ -1,5 +1,5 @@ name:           unordered-containers-version:        0.2.18.0+version:        0.2.19.0 synopsis:       Efficient hashing-based container types description:   Efficient hashing-based container types.  The containers have been