containers 0.6.5.1 → 0.6.6

raw patch · 32 files changed

+736/−1039 lines, 32 filesdep +template-haskelldep ~basePVP ok

version bump matches the API change (PVP)

Dependencies added: template-haskell

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• changelog.md +14/−1
• containers.cabal +3/−3
• include/containers.h +7/−18
• src/Data/Graph.hs +9/−16
• src/Data/IntMap.hs +4/−5
• src/Data/IntMap/Internal.hs +133/−198
• src/Data/IntMap/Lazy.hs +2/−2
• src/Data/IntMap/Merge/Lazy.hs +0/−13
• src/Data/IntMap/Merge/Strict.hs +0/−15
• src/Data/IntMap/Strict.hs +2/−2
• src/Data/IntMap/Strict/Internal.hs +48/−54
• src/Data/IntSet.hs +2/−2
• src/Data/IntSet/Internal.hs +69/−91
• src/Data/Map/Internal.hs +160/−205
• src/Data/Map/Internal/Debug.hs +3/−3
• src/Data/Map/Lazy.hs +3/−1
• src/Data/Map/Merge/Lazy.hs +1/−14
• src/Data/Map/Merge/Strict.hs +1/−14
• src/Data/Map/Strict.hs +3/−1
• src/Data/Map/Strict/Internal.hs +66/−67
• src/Data/Sequence.hs +1/−1
• src/Data/Sequence/Internal.hs +76/−90
• src/Data/Set.hs +1/−1
• src/Data/Set/Internal.hs +105/−114
• src/Data/Tree.hs +9/−27
• src/Utils/Containers/Internal/BitQueue.hs +1/−14
• src/Utils/Containers/Internal/BitUtil.hs +1/−32
• src/Utils/Containers/Internal/Coercions.hs +3/−3
• src/Utils/Containers/Internal/PtrEquality.hs +0/−9
• src/Utils/Containers/Internal/State.hs +6/−7
• src/Utils/Containers/Internal/StrictMaybe.hs +0/−5
• src/Utils/Containers/Internal/TypeError.hs +3/−11

@@ -1,5 +1,18 @@ # Changelog for [`containers` package](http://github.com/haskell/containers) +## FIXME++* Drop support for GHC versions before 8.0.2.++* Bump Cabal version for tests, and use `common` clauses to reduce+  duplication.++### New instances++* Add `Lift` instances for use with Template Haskell. Specifically:+  `Seq`, `ViewL`, and `ViewR` (in `Data.Sequence`), `Map`, `Set`,+  `IntMap`, `IntSet`, `Tree`, and `SCC` (in `Data.Graph`).+ ## 0.6.5.1  ### Bug fixes@@ -8,7 +21,7 @@   should be, and we have detailed tests to make sure they stay that way.   (Thanks, coot.) -* The `Ord IntSet` instance, which was broken in the last version, has been+* The `Ord IntSet` instance, which was broken in 0.6.3.1, has been   repaired.  ### New instance

@@ -1,5 +1,5 @@ name: containers-version: 0.6.5.1+version: 0.6.6 license: BSD3 license-file: LICENSE maintainer: libraries@haskell.org@@ -25,7 +25,7 @@     include/containers.h     changelog.md -tested-with: GHC==9.0.1, GHC==8.10.4, GHC==8.8.4, GHC==8.6.5, GHC==8.4.4, GHC==8.2.2, GHC==8.0.2, GHC==7.10.3, GHC==7.8.4, GHC==7.6.3+tested-with: GHC==9.2.2, GHC==9.0.2, GHC==8.10.7, GHC==8.8.4, GHC==8.6.5, GHC==8.4.4, GHC==8.2.2, GHC==8.0.2  source-repository head     type:     git@@ -33,7 +33,7 @@  Library     default-language: Haskell2010-    build-depends: base >= 4.6 && < 5, array >= 0.4.0.0, deepseq >= 1.2 && < 1.5+    build-depends: base >= 4.9.1 && < 5, array >= 0.4.0.0, deepseq >= 1.2 && < 1.5, template-haskell     hs-source-dirs: src     ghc-options: -O2 -Wall -fwarn-incomplete-uni-patterns -fwarn-incomplete-record-updates 

@@ -12,30 +12,19 @@ #include "MachDeps.h" #endif -/*- * Define INSTANCE_TYPEABLE[0-2]- */-#if __GLASGOW_HASKELL__ >= 707-#define INSTANCE_TYPEABLE0(tycon) deriving instance Typeable tycon-#define INSTANCE_TYPEABLE1(tycon) deriving instance Typeable tycon-#define INSTANCE_TYPEABLE2(tycon) deriving instance Typeable tycon-#elif defined(__GLASGOW_HASKELL__)-#define INSTANCE_TYPEABLE0(tycon) deriving instance Typeable tycon-#define INSTANCE_TYPEABLE1(tycon) deriving instance Typeable1 tycon-#define INSTANCE_TYPEABLE2(tycon) deriving instance Typeable2 tycon-#else-#define INSTANCE_TYPEABLE0(tycon)-#define INSTANCE_TYPEABLE1(tycon)-#define INSTANCE_TYPEABLE2(tycon)-#endif--#if __GLASGOW_HASKELL__ >= 800+#ifdef __GLASGOW_HASKELL__ #define DEFINE_PATTERN_SYNONYMS 1 #endif  #ifdef __GLASGOW_HASKELL__ # define USE_ST_MONAD 1+#ifndef WORDS_BIGENDIAN+/*+ * Unboxed arrays are broken on big-endian architectures.+ * See https://gitlab.haskell.org/ghc/ghc/-/issues/16998+ */ # define USE_UNBOXED_ARRAYS 1+#endif #endif  #endif

@@ -3,12 +3,13 @@ {-# LANGUAGE RankNTypes #-} {-# LANGUAGE DeriveDataTypeable #-} {-# LANGUAGE DeriveGeneric #-}+{-# LANGUAGE DeriveLift #-} {-# LANGUAGE StandaloneDeriving #-}-# if __GLASGOW_HASKELL__ >= 710+#  if __GLASGOW_HASKELL__ >= 802 {-# LANGUAGE Safe #-}-# else+#  else {-# LANGUAGE Trustworthy #-}-# endif+#  endif #endif  #include "containers.h"@@ -107,12 +108,7 @@  -- std interfaces import Control.Applicative-#if !MIN_VERSION_base(4,8,0)-import qualified Data.Foldable as F-import Data.Traversable-#else import Data.Foldable as F-#endif import Control.DeepSeq (NFData(rnf)) import Data.Maybe import Data.Array@@ -123,16 +119,14 @@ import qualified Data.Array as UA #endif import qualified Data.List as L-#if MIN_VERSION_base(4,9,0) import Data.Functor.Classes-#endif-#if (!MIN_VERSION_base(4,11,0)) && MIN_VERSION_base(4,9,0)+#if !MIN_VERSION_base(4,11,0) import Data.Semigroup (Semigroup (..)) #endif #ifdef __GLASGOW_HASKELL__ import GHC.Generics (Generic, Generic1) import Data.Data (Data)-import Data.Typeable+import Language.Haskell.TH.Syntax (Lift) #endif  -- Make sure we don't use Integer by mistake.@@ -158,8 +152,6 @@   deriving (Eq, Show, Read) #endif -INSTANCE_TYPEABLE1(SCC)- #ifdef __GLASGOW_HASKELL__ -- | @since 0.5.9 deriving instance Data vertex => Data (SCC vertex)@@ -169,9 +161,11 @@  -- | @since 0.5.9 deriving instance Generic (SCC vertex)++-- | @since FIXME+deriving instance Lift vertex => Lift (SCC vertex) #endif -#if MIN_VERSION_base(4,9,0) -- | @since 0.5.9 instance Eq1 SCC where   liftEq eq (AcyclicSCC v1) (AcyclicSCC v2) = eq v1 v2@@ -186,7 +180,6 @@   liftReadsPrec rp rl = readsData $     readsUnaryWith rp "AcyclicSCC" AcyclicSCC <>     readsUnaryWith (const rl) "CyclicSCC" CyclicSCC-#endif  -- | @since 0.5.9 instance F.Foldable SCC where

@@ -3,9 +3,8 @@ {-# LANGUAGE Safe #-} #endif #ifdef __GLASGOW_HASKELL__-{-# LANGUAGE DataKinds, FlexibleContexts #-}-#endif-#if __GLASGOW_HASKELL__ >= 800+{-# LANGUAGE DataKinds #-}+{-# LANGUAGE FlexibleContexts #-} {-# LANGUAGE MonoLocalBinds #-} #endif @@ -51,9 +50,9 @@ -- -- Operation comments contain the operation time complexity in -- the Big-O notation <http://en.wikipedia.org/wiki/Big_O_notation>.--- Many operations have a worst-case complexity of /O(min(n,W))/.+-- Many operations have a worst-case complexity of \(O(\min(n,W))\). -- This means that the operation can become linear in the number of--- elements with a maximum of /W/ -- the number of bits in an 'Int'+-- elements with a maximum of \(W\) -- the number of bits in an 'Int' -- (32 or 64). ----------------------------------------------------------------------------- 

@@ -1,16 +1,16 @@ {-# LANGUAGE CPP #-} {-# LANGUAGE BangPatterns #-} {-# LANGUAGE PatternGuards #-}-#if __GLASGOW_HASKELL__-{-# LANGUAGE MagicHash, DeriveDataTypeable, StandaloneDeriving #-}+#ifdef __GLASGOW_HASKELL__+{-# LANGUAGE DeriveLift #-}+{-# LANGUAGE MagicHash #-} {-# LANGUAGE ScopedTypeVariables #-}+{-# LANGUAGE StandaloneDeriving #-}+{-# LANGUAGE TypeFamilies #-} #endif #if !defined(TESTING) && defined(__GLASGOW_HASKELL__) {-# LANGUAGE Trustworthy #-} #endif-#if __GLASGOW_HASKELL__ >= 708-{-# LANGUAGE TypeFamilies #-}-#endif  {-# OPTIONS_HADDOCK not-home #-} {-# OPTIONS_GHC -fno-warn-incomplete-uni-patterns #-}@@ -293,34 +293,19 @@     , mapGentlyWhenMatched     ) where -#if MIN_VERSION_base(4,8,0) import Data.Functor.Identity (Identity (..)) import Control.Applicative (liftA2)-#else-import Control.Applicative (Applicative(pure, (<*>)), (<$>), liftA2)-import Data.Monoid (Monoid(..))-import Data.Traversable (Traversable(traverse))-import Data.Word (Word)-#endif-#if MIN_VERSION_base(4,9,0) import Data.Semigroup (Semigroup(stimes))-#endif-#if !(MIN_VERSION_base(4,11,0)) && MIN_VERSION_base(4,9,0)+#if !(MIN_VERSION_base(4,11,0)) import Data.Semigroup (Semigroup((<>))) #endif-#if MIN_VERSION_base(4,9,0) import Data.Semigroup (stimesIdempotentMonoid) import Data.Functor.Classes-#endif  import Control.DeepSeq (NFData(rnf)) import Data.Bits import qualified Data.Foldable as Foldable-#if !MIN_VERSION_base(4,8,0)-import Data.Foldable (Foldable())-#endif import Data.Maybe (fromMaybe)-import Data.Typeable import Prelude hiding (lookup, map, filter, foldr, foldl, null)  import Data.IntSet.Internal (Key)@@ -328,22 +313,16 @@ import Utils.Containers.Internal.BitUtil import Utils.Containers.Internal.StrictPair -#if __GLASGOW_HASKELL__+#ifdef __GLASGOW_HASKELL__+import Data.Coerce import Data.Data (Data(..), Constr, mkConstr, constrIndex, Fixity(Prefix),-                  DataType, mkDataType)+                  DataType, mkDataType, gcast1) import GHC.Exts (build)-#if !MIN_VERSION_base(4,8,0)-import Data.Functor ((<$))-#endif-#if __GLASGOW_HASKELL__ >= 708 import qualified GHC.Exts as GHCExts-#endif import Text.Read+import Language.Haskell.TH.Syntax (Lift) #endif import qualified Control.Category as Category-#if __GLASGOW_HASKELL__ >= 709-import Data.Coerce-#endif   -- A "Nat" is a natural machine word (an unsigned Int)@@ -392,6 +371,9 @@ type IntSetPrefix = Int type IntSetBitMap = Word +-- | @since FIXME+deriving instance Lift a => Lift (IntMap a)+ bitmapOf :: Int -> IntSetBitMap bitmapOf x = shiftLL 1 (x .&. IntSet.suffixBitMask) {-# INLINE bitmapOf #-}@@ -400,7 +382,7 @@   Operators --------------------------------------------------------------------} --- | /O(min(n,W))/. Find the value at a key.+-- | \(O(\min(n,W))\). Find the value at a key. -- Calls 'error' when the element can not be found. -- -- > fromList [(5,'a'), (3,'b')] ! 1    Error: element not in the map@@ -409,7 +391,7 @@ (!) :: IntMap a -> Key -> a (!) m k = find k m --- | /O(min(n,W))/. Find the value at a key.+-- | \(O(\min(n,W))\). Find the value at a key. -- Returns 'Nothing' when the element can not be found. -- -- > fromList [(5,'a'), (3,'b')] !? 1 == Nothing@@ -433,16 +415,12 @@ instance Monoid (IntMap a) where     mempty  = empty     mconcat = unions-#if !(MIN_VERSION_base(4,9,0))-    mappend = union-#else     mappend = (<>)  -- | @since 0.5.7 instance Semigroup (IntMap a) where     (<>)    = union     stimes  = stimesIdempotentMonoid-#endif  -- | Folds in order of increasing key. instance Foldable.Foldable IntMap where@@ -468,7 +446,6 @@   {-# INLINE foldl' #-}   foldr' = foldr'   {-# INLINE foldr' #-}-#if MIN_VERSION_base(4,8,0)   length = size   {-# INLINE length #-}   null   = null@@ -506,7 +483,6 @@   {-# INLINABLE sum #-}   product = foldl' (*) 1   {-# INLINABLE product #-}-#endif  -- | Traverses in order of increasing key. instance Traversable IntMap where@@ -547,7 +523,7 @@ {--------------------------------------------------------------------   Query --------------------------------------------------------------------}--- | /O(1)/. Is the map empty?+-- | \(O(1)\). Is the map empty? -- -- > Data.IntMap.null (empty)           == True -- > Data.IntMap.null (singleton 1 'a') == False@@ -557,7 +533,7 @@ null _   = False {-# INLINE null #-} --- | /O(n)/. Number of elements in the map.+-- | \(O(n)\). Number of elements in the map. -- -- > size empty                                   == 0 -- > size (singleton 1 'a')                       == 1@@ -569,7 +545,7 @@     go acc (Tip _ _) = 1 + acc     go acc Nil = acc --- | /O(min(n,W))/. Is the key a member of the map?+-- | \(O(\min(n,W))\). Is the key a member of the map? -- -- > member 5 (fromList [(5,'a'), (3,'b')]) == True -- > member 1 (fromList [(5,'a'), (3,'b')]) == False@@ -584,7 +560,7 @@     go (Tip kx _) = k == kx     go Nil = False --- | /O(min(n,W))/. Is the key not a member of the map?+-- | \(O(\min(n,W))\). Is the key not a member of the map? -- -- > notMember 5 (fromList [(5,'a'), (3,'b')]) == False -- > notMember 1 (fromList [(5,'a'), (3,'b')]) == True@@ -592,34 +568,31 @@ notMember :: Key -> IntMap a -> Bool notMember k m = not $ member k m --- | /O(min(n,W))/. Lookup the value at a key in the map. See also 'Data.Map.lookup'.+-- | \(O(\min(n,W))\). Lookup the value at a key in the map. See also 'Data.Map.lookup'. --- See Note: Local 'go' functions and capturing]+-- See Note: Local 'go' functions and capturing lookup :: Key -> IntMap a -> Maybe a lookup !k = go   where-    go (Bin p m l r) | nomatch k p m = Nothing-                     | zero k m  = go l-                     | otherwise = go r+    go (Bin _p m l r) | zero k m  = go l+                      | otherwise = go r     go (Tip kx x) | k == kx   = Just x                   | otherwise = Nothing     go Nil = Nothing - -- See Note: Local 'go' functions and capturing] find :: Key -> IntMap a -> a find !k = go   where-    go (Bin p m l r) | nomatch k p m = not_found-                     | zero k m  = go l-                     | otherwise = go r+    go (Bin _p m l r) | zero k m  = go l+                      | otherwise = go r     go (Tip kx x) | k == kx   = x                   | otherwise = not_found     go Nil = not_found      not_found = error ("IntMap.!: key " ++ show k ++ " is not an element of the map") --- | /O(min(n,W))/. The expression @('findWithDefault' def k map)@+-- | \(O(\min(n,W))\). The expression @('findWithDefault' def k map)@ -- returns the value at key @k@ or returns @def@ when the key is not an -- element of the map. --@@ -637,7 +610,7 @@                   | otherwise = def     go Nil = def --- | /O(log n)/. Find largest key smaller than the given one and return the+-- | \(O(\log n)\). Find largest key smaller than the given one and return the -- corresponding (key, value) pair. -- -- > lookupLT 3 (fromList [(3,'a'), (5,'b')]) == Nothing@@ -658,7 +631,7 @@       | otherwise = Just (ky, y)     go def Nil = unsafeFindMax def --- | /O(log n)/. Find smallest key greater than the given one and return the+-- | \(O(\log n)\). Find smallest key greater than the given one and return the -- corresponding (key, value) pair. -- -- > lookupGT 4 (fromList [(3,'a'), (5,'b')]) == Just (5, 'b')@@ -679,7 +652,7 @@       | otherwise = Just (ky, y)     go def Nil = unsafeFindMin def --- | /O(log n)/. Find largest key smaller or equal to the given one and return+-- | \(O(\log n)\). Find largest key smaller or equal to the given one and return -- the corresponding (key, value) pair. -- -- > lookupLE 2 (fromList [(3,'a'), (5,'b')]) == Nothing@@ -701,7 +674,7 @@       | otherwise = Just (ky, y)     go def Nil = unsafeFindMax def --- | /O(log n)/. Find smallest key greater or equal to the given one and return+-- | \(O(\log n)\). Find smallest key greater or equal to the given one and return -- the corresponding (key, value) pair. -- -- > lookupGE 3 (fromList [(3,'a'), (5,'b')]) == Just (3, 'a')@@ -741,7 +714,7 @@ {--------------------------------------------------------------------   Disjoint --------------------------------------------------------------------}--- | /O(n+m)/. Check whether the key sets of two maps are disjoint+-- | \(O(n+m)\). Check whether the key sets of two maps are disjoint -- (i.e. their 'intersection' is empty). -- -- > disjoint (fromList [(2,'a')]) (fromList [(1,()), (3,())])   == True@@ -797,7 +770,7 @@ {--------------------------------------------------------------------   Construction --------------------------------------------------------------------}--- | /O(1)/. The empty map.+-- | \(O(1)\). The empty map. -- -- > empty      == fromList [] -- > size empty == 0@@ -807,7 +780,7 @@   = Nil {-# INLINE empty #-} --- | /O(1)/. A map of one element.+-- | \(O(1)\). A map of one element. -- -- > singleton 1 'a'        == fromList [(1, 'a')] -- > size (singleton 1 'a') == 1@@ -820,7 +793,7 @@ {--------------------------------------------------------------------   Insert --------------------------------------------------------------------}--- | /O(min(n,W))/. Insert a new key\/value pair in the map.+-- | \(O(\min(n,W))\). Insert a new key\/value pair in the map. -- If the key is already present in the map, the associated value is -- replaced with the supplied value, i.e. 'insert' is equivalent to -- @'insertWith' 'const'@.@@ -840,7 +813,7 @@ insert k x Nil = Tip k x  -- right-biased insertion, used by 'union'--- | /O(min(n,W))/. Insert with a combining function.+-- | \(O(\min(n,W))\). Insert with a combining function. -- @'insertWith' f key value mp@ -- will insert the pair (key, value) into @mp@ if key does -- not exist in the map. If the key does exist, the function will@@ -854,7 +827,7 @@ insertWith f k x t   = insertWithKey (\_ x' y' -> f x' y') k x t --- | /O(min(n,W))/. Insert with a combining function.+-- | \(O(\min(n,W))\). Insert with a combining function. -- @'insertWithKey' f key value mp@ -- will insert the pair (key, value) into @mp@ if key does -- not exist in the map. If the key does exist, the function will@@ -875,7 +848,7 @@   | otherwise     = link k (Tip k x) ky t insertWithKey _ k x Nil = Tip k x --- | /O(min(n,W))/. The expression (@'insertLookupWithKey' f k x map@)+-- | \(O(\min(n,W))\). The expression (@'insertLookupWithKey' f k x map@) -- is a pair where the first element is equal to (@'lookup' k map@) -- and the second element equal to (@'insertWithKey' f k x map@). --@@ -906,7 +879,7 @@ {--------------------------------------------------------------------   Deletion --------------------------------------------------------------------}--- | /O(min(n,W))/. Delete a key and its value from the map. When the key is not+-- | \(O(\min(n,W))\). Delete a key and its value from the map. When the key is not -- a member of the map, the original map is returned. -- -- > delete 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"@@ -923,7 +896,7 @@   | otherwise     = t delete _k Nil = Nil --- | /O(min(n,W))/. Adjust a value at a specific key. When the key is not+-- | \(O(\min(n,W))\). Adjust a value at a specific key. When the key is not -- a member of the map, the original map is returned. -- -- > adjust ("new " ++) 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]@@ -934,7 +907,7 @@ adjust f k m   = adjustWithKey (\_ x -> f x) k m --- | /O(min(n,W))/. Adjust a value at a specific key. When the key is not+-- | \(O(\min(n,W))\). Adjust a value at a specific key. When the key is not -- a member of the map, the original map is returned. -- -- > let f key x = (show key) ++ ":new " ++ x@@ -943,8 +916,7 @@ -- > adjustWithKey f 7 empty                         == empty  adjustWithKey ::  (Key -> a -> a) -> Key -> IntMap a -> IntMap a-adjustWithKey f !k t@(Bin p m l r)-  | nomatch k p m = t+adjustWithKey f !k (Bin p m l r)   | zero k m      = Bin p m (adjustWithKey f k l) r   | otherwise     = Bin p m l (adjustWithKey f k r) adjustWithKey f k t@(Tip ky y)@@ -953,7 +925,7 @@ adjustWithKey _ _ Nil = Nil  --- | /O(min(n,W))/. The expression (@'update' f k map@) updates the value @x@+-- | \(O(\min(n,W))\). 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@. --@@ -966,7 +938,7 @@ update f   = updateWithKey (\_ x -> f x) --- | /O(min(n,W))/. The expression (@'update' f k map@) updates the value @x@+-- | \(O(\min(n,W))\). The expression (@'update' f k map@) updates the value @x@ -- at @k@ (if it is in the map). If (@f k x@) is 'Nothing', the element is -- deleted. If it is (@'Just' y@), the key @k@ is bound to the new value @y@. --@@ -976,8 +948,7 @@ -- > updateWithKey f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"  updateWithKey ::  (Key -> a -> Maybe a) -> Key -> IntMap a -> IntMap a-updateWithKey f !k t@(Bin p m l r)-  | nomatch k p m = t+updateWithKey f !k (Bin p m l r)   | zero k m      = binCheckLeft p m (updateWithKey f k l) r   | otherwise     = binCheckRight p m l (updateWithKey f k r) updateWithKey f k t@(Tip ky y)@@ -987,7 +958,7 @@   | otherwise     = t updateWithKey _ _ Nil = Nil --- | /O(min(n,W))/. Lookup and update.+-- | \(O(\min(n,W))\). Lookup and update. -- The function returns original value, if it is updated. -- This is different behavior than 'Data.Map.updateLookupWithKey'. -- Returns the original key value if the map entry is deleted.@@ -998,8 +969,7 @@ -- > updateLookupWithKey f 3 (fromList [(5,"a"), (3,"b")]) == (Just "b", singleton 5 "a")  updateLookupWithKey ::  (Key -> a -> Maybe a) -> Key -> IntMap a -> (Maybe a,IntMap a)-updateLookupWithKey f !k t@(Bin p m l r)-  | nomatch k p m = (Nothing,t)+updateLookupWithKey f !k (Bin p m l r)   | zero k m      = let !(found,l') = updateLookupWithKey f k l                     in (found,binCheckLeft p m l' r)   | otherwise     = let !(found,r') = updateLookupWithKey f k r@@ -1013,7 +983,7 @@   --- | /O(min(n,W))/. The expression (@'alter' f k map@) alters the value @x@ at @k@, or absence thereof.+-- | \(O(\min(n,W))\). 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 an 'IntMap'. -- In short : @'lookup' k ('alter' f k m) = f ('lookup' k m)@. alter :: (Maybe a -> Maybe a) -> Key -> IntMap a -> IntMap a@@ -1034,7 +1004,7 @@                       Just x -> Tip k x                       Nothing -> Nil --- | /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 inspect, insert, delete, -- or update a value in an 'IntMap'.  In short : @'lookup' k <$> 'alterF' f k m = f -- ('lookup' k m)@.@@ -1094,7 +1064,7 @@ unionsWith f ts   = Foldable.foldl' (unionWith f) empty ts --- | /O(n+m)/. The (left-biased) union of two maps.+-- | \(O(n+m)\). The (left-biased) union of two maps. -- It prefers the first map when duplicate keys are encountered, -- i.e. (@'union' == 'unionWith' 'const'@). --@@ -1104,7 +1074,7 @@ union m1 m2   = mergeWithKey' Bin const id id m1 m2 --- | /O(n+m)/. The union with a combining function.+-- | \(O(n+m)\). The union with a combining function. -- -- > unionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")] @@ -1112,7 +1082,7 @@ unionWith f m1 m2   = unionWithKey (\_ x y -> f x y) m1 m2 --- | /O(n+m)/. The union with a combining function.+-- | \(O(n+m)\). The union with a combining function. -- -- > let f key left_value right_value = (show key) ++ ":" ++ left_value ++ "|" ++ right_value -- > unionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "5:a|A"), (7, "C")]@@ -1124,7 +1094,7 @@ {--------------------------------------------------------------------   Difference --------------------------------------------------------------------}--- | /O(n+m)/. Difference between two maps (based on keys).+-- | \(O(n+m)\). Difference between two maps (based on keys). -- -- > difference (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 3 "b" @@ -1132,7 +1102,7 @@ difference m1 m2   = mergeWithKey (\_ _ _ -> Nothing) id (const Nil) m1 m2 --- | /O(n+m)/. Difference with a combining function.+-- | \(O(n+m)\). Difference with a combining function. -- -- > let f al ar = if al == "b" then Just (al ++ ":" ++ ar) else Nothing -- > differenceWith f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (7, "C")])@@ -1142,7 +1112,7 @@ differenceWith f m1 m2   = differenceWithKey (\_ x y -> f x y) m1 m2 --- | /O(n+m)/. Difference with a combining function. When two equal keys are+-- | \(O(n+m)\). Difference with a combining function. When two equal keys are -- encountered, the combining function is applied to the key and both values. -- 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@.@@ -1157,7 +1127,7 @@   -- TODO(wrengr): re-verify that asymptotic bound--- | /O(n+m)/. Remove all the keys in a given set from a map.+-- | \(O(n+m)\). Remove all the keys in a given set from a map. -- -- @ -- m \`withoutKeys\` s = 'filterWithKey' (\k _ -> k ``IntSet.notMember`` s) m@@ -1225,7 +1195,7 @@ {--------------------------------------------------------------------   Intersection --------------------------------------------------------------------}--- | /O(n+m)/. The (left-biased) intersection of two maps (based on keys).+-- | \(O(n+m)\). The (left-biased) intersection of two maps (based on keys). -- -- > intersection (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "a" @@ -1235,7 +1205,7 @@   -- TODO(wrengr): re-verify that asymptotic bound--- | /O(n+m)/. The restriction of a map to the keys in a set.+-- | \(O(n+m)\). The restriction of a map to the keys in a set. -- -- @ -- m \`restrictKeys\` s = 'filterWithKey' (\k _ -> k ``IntSet.member`` s) m@@ -1272,7 +1242,7 @@ restrictKeys Nil _ = Nil  --- | /O(min(n,W))/. Restrict to the sub-map with all keys matching+-- | \(O(\min(n,W))\). Restrict to the sub-map with all keys matching -- a key prefix. lookupPrefix :: IntSetPrefix -> IntMap a -> IntMap a lookupPrefix !kp t@(Bin p m l r)@@ -1301,7 +1271,7 @@ restrictBM _ Nil = Nil  --- | /O(n+m)/. The intersection with a combining function.+-- | \(O(n+m)\). The intersection with a combining function. -- -- > intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "aA" @@ -1309,7 +1279,7 @@ intersectionWith f m1 m2   = intersectionWithKey (\_ x y -> f x y) m1 m2 --- | /O(n+m)/. The intersection with a combining function.+-- | \(O(n+m)\). The intersection with a combining function. -- -- > let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ ar -- > intersectionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "5:a|A"@@ -1322,7 +1292,7 @@   MergeWithKey --------------------------------------------------------------------} --- | /O(n+m)/. A high-performance universal combining function. Using+-- | \(O(n+m)\). A high-performance universal combining function. Using -- 'mergeWithKey', all combining functions can be defined without any loss of -- efficiency (with exception of 'union', 'difference' and 'intersection', -- where sharing of some nodes is lost with 'mergeWithKey').@@ -1483,9 +1453,6 @@ -- -- @since 0.5.9 instance (Applicative f, Monad f) => Monad (WhenMissing f x) where-#if !MIN_VERSION_base(4,8,0)-  return = pure-#endif   m >>= f =     traverseMaybeMissing $ \k x -> do       res1 <- missingKey m k x@@ -1568,17 +1535,6 @@ {-# INLINE contramapSecondWhenMatched #-}  -#if !MIN_VERSION_base(4,8,0)-newtype Identity a = Identity {runIdentity :: a}--instance Functor Identity where-    fmap f (Identity x) = Identity (f x)--instance Applicative Identity where-    pure = Identity-    Identity f <*> Identity x = Identity (f x)-#endif- -- | A tactic for dealing with keys present in one map but not the -- other in 'merge'. --@@ -1657,9 +1613,6 @@ -- -- @since 0.5.9 instance (Monad f, Applicative f) => Monad (WhenMatched f x y) where-#if !MIN_VERSION_base(4,8,0)-  return = pure-#endif   m >>= f =     zipWithMaybeAMatched $ \k x y -> do       res <- runWhenMatched m k x y@@ -1854,7 +1807,7 @@ {-# INLINE filterAMissing #-}  --- | /O(n)/. Filter keys and values using an 'Applicative' predicate.+-- | \(O(n)\). Filter keys and values using an 'Applicative' predicate. filterWithKeyA   :: Applicative f => (Key -> a -> f Bool) -> IntMap a -> f (IntMap a) filterWithKeyA _ Nil           = pure Nil@@ -1895,7 +1848,7 @@ {-# INLINE traverseMaybeMissing #-}  --- | /O(n)/. Traverse keys\/values and collect the 'Just' results.+-- | \(O(n)\). Traverse keys\/values and collect the 'Just' results. -- -- @since 0.6.4 traverseMaybeWithKey@@ -2158,7 +2111,7 @@   Min\/Max --------------------------------------------------------------------} --- | /O(min(n,W))/. Update the value at the minimal key.+-- | \(O(\min(n,W))\). Update the value at the minimal key. -- -- > updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"3:b"), (5,"a")] -- > updateMinWithKey (\ _ _ -> Nothing)                     (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"@@ -2174,7 +2127,7 @@                         Nothing -> Nil     go _ Nil = error "updateMinWithKey Nil" --- | /O(min(n,W))/. Update the value at the maximal key.+-- | \(O(\min(n,W))\). Update the value at the maximal key. -- -- > updateMaxWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"b"), (5,"5:a")] -- > updateMaxWithKey (\ _ _ -> Nothing)                     (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"@@ -2193,7 +2146,7 @@  data View a = View {-# UNPACK #-} !Key a !(IntMap a) --- | /O(min(n,W))/. Retrieves the maximal (key,value) pair of the map, and+-- | \(O(\min(n,W))\). Retrieves the maximal (key,value) pair of the map, and -- the map stripped of that element, or 'Nothing' if passed an empty map. -- -- > maxViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((5,"a"), singleton 3 "b")@@ -2221,7 +2174,7 @@ -- See note on NOINLINE at minViewWithKeySure {-# NOINLINE maxViewWithKeySure #-} --- | /O(min(n,W))/. Retrieves the minimal (key,value) pair of the map, and+-- | \(O(\min(n,W))\). Retrieves the minimal (key,value) pair of the map, and -- the map stripped of that element, or 'Nothing' if passed an empty map. -- -- > minViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((3,"b"), singleton 5 "a")@@ -2257,7 +2210,7 @@ -- anyway, which should be good enough. {-# NOINLINE minViewWithKeySure #-} --- | /O(min(n,W))/. Update the value at the maximal key.+-- | \(O(\min(n,W))\). Update the value at the maximal key. -- -- > updateMax (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "Xa")] -- > updateMax (\ _ -> Nothing)         (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"@@ -2265,7 +2218,7 @@ updateMax :: (a -> Maybe a) -> IntMap a -> IntMap a updateMax f = updateMaxWithKey (const f) --- | /O(min(n,W))/. Update the value at the minimal key.+-- | \(O(\min(n,W))\). Update the value at the minimal key. -- -- > updateMin (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "Xb"), (5, "a")] -- > updateMin (\ _ -> Nothing)         (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"@@ -2273,29 +2226,29 @@ updateMin :: (a -> Maybe a) -> IntMap a -> IntMap a updateMin f = updateMinWithKey (const f) --- | /O(min(n,W))/. Retrieves the maximal key of the map, and the map+-- | \(O(\min(n,W))\). Retrieves the maximal key of the map, and the map -- stripped of that element, or 'Nothing' if passed an empty map. maxView :: IntMap a -> Maybe (a, IntMap a) maxView t = fmap (\((_, x), t') -> (x, t')) (maxViewWithKey t) --- | /O(min(n,W))/. Retrieves the minimal key of the map, and the map+-- | \(O(\min(n,W))\). Retrieves the minimal key of the map, and the map -- stripped of that element, or 'Nothing' if passed an empty map. minView :: IntMap a -> Maybe (a, IntMap a) minView t = fmap (\((_, x), t') -> (x, t')) (minViewWithKey t) --- | /O(min(n,W))/. Delete and find the maximal element.+-- | \(O(\min(n,W))\). Delete and find the maximal element. -- This function throws an error if the map is empty. Use 'maxViewWithKey' -- if the map may be empty. deleteFindMax :: IntMap a -> ((Key, a), IntMap a) deleteFindMax = fromMaybe (error "deleteFindMax: empty map has no maximal element") . maxViewWithKey --- | /O(min(n,W))/. Delete and find the minimal element.+-- | \(O(\min(n,W))\). Delete and find the minimal element. -- This function throws an error if the map is empty. Use 'minViewWithKey' -- if the map may be empty. deleteFindMin :: IntMap a -> ((Key, a), IntMap a) deleteFindMin = fromMaybe (error "deleteFindMin: empty map has no minimal element") . minViewWithKey --- | /O(min(n,W))/. The minimal key of the map. Returns 'Nothing' if the map is empty.+-- | \(O(\min(n,W))\). The minimal key of the map. Returns 'Nothing' if the map is empty. lookupMin :: IntMap a -> Maybe (Key, a) lookupMin Nil = Nothing lookupMin (Tip k v) = Just (k,v)@@ -2306,14 +2259,14 @@           go (Bin _ _ l' _) = go l'           go Nil            = Nothing --- | /O(min(n,W))/. The minimal key of the map. Calls 'error' if the map is empty.+-- | \(O(\min(n,W))\). The minimal key of the map. Calls 'error' if the map is empty. -- Use 'minViewWithKey' if the map may be empty. findMin :: IntMap a -> (Key, a) findMin t   | Just r <- lookupMin t = r   | otherwise = error "findMin: empty map has no minimal element" --- | /O(min(n,W))/. The maximal key of the map. Returns 'Nothing' if the map is empty.+-- | \(O(\min(n,W))\). The maximal key of the map. Returns 'Nothing' if the map is empty. lookupMax :: IntMap a -> Maybe (Key, a) lookupMax Nil = Nothing lookupMax (Tip k v) = Just (k,v)@@ -2324,21 +2277,21 @@           go (Bin _ _ _ r') = go r'           go Nil            = Nothing --- | /O(min(n,W))/. The maximal key of the map. Calls 'error' if the map is empty.+-- | \(O(\min(n,W))\). The maximal key of the map. Calls 'error' if the map is empty. -- Use 'maxViewWithKey' if the map may be empty. findMax :: IntMap a -> (Key, a) findMax t   | Just r <- lookupMax t = r   | otherwise = error "findMax: empty map has no maximal element" --- | /O(min(n,W))/. Delete the minimal key. Returns an empty map if the map is empty.+-- | \(O(\min(n,W))\). Delete the minimal key. Returns an empty map if the map is empty. -- -- Note that this is a change of behaviour for consistency with 'Data.Map.Map' &#8211; -- versions prior to 0.5 threw an error if the 'IntMap' was already empty. deleteMin :: IntMap a -> IntMap a deleteMin = maybe Nil snd . minView --- | /O(min(n,W))/. Delete the maximal key. Returns an empty map if the map is empty.+-- | \(O(\min(n,W))\). Delete the maximal key. Returns an empty map if the map is empty. -- -- Note that this is a change of behaviour for consistency with 'Data.Map.Map' &#8211; -- versions prior to 0.5 threw an error if the 'IntMap' was already empty.@@ -2349,13 +2302,13 @@ {--------------------------------------------------------------------   Submap --------------------------------------------------------------------}--- | /O(n+m)/. Is this a proper submap? (ie. a submap but not equal).+-- | \(O(n+m)\). Is this a proper submap? (ie. a submap but not equal). -- Defined as (@'isProperSubmapOf' = 'isProperSubmapOfBy' (==)@). isProperSubmapOf :: Eq a => IntMap a -> IntMap a -> Bool isProperSubmapOf m1 m2   = isProperSubmapOfBy (==) m1 m2 -{- | /O(n+m)/. Is this a proper submap? (ie. a submap but not equal).+{- | \(O(n+m)\). Is this a proper submap? (ie. a submap but not equal).  The expression (@'isProperSubmapOfBy' f m1 m2@) returns 'True' when  @keys m1@ and @keys m2@ are not equal,  all keys in @m1@ are in @m2@, and when @f@ returns 'True' when@@ -2404,13 +2357,13 @@ submapCmp _    Nil Nil = EQ submapCmp _    Nil _   = LT --- | /O(n+m)/. Is this a submap?+-- | \(O(n+m)\). Is this a submap? -- Defined as (@'isSubmapOf' = 'isSubmapOfBy' (==)@). isSubmapOf :: Eq a => IntMap a -> IntMap a -> Bool isSubmapOf m1 m2   = isSubmapOfBy (==) m1 m2 -{- | /O(n+m)/.+{- | \(O(n+m)\).  The expression (@'isSubmapOfBy' f m1 m2@) returns 'True' if  all keys in @m1@ are in @m2@, and when @f@ returns 'True' when  applied to their respective values. For example, the following@@ -2443,7 +2396,7 @@ {--------------------------------------------------------------------   Mapping --------------------------------------------------------------------}--- | /O(n)/. Map a function over all values in the map.+-- | \(O(n)\). Map a function over all values in the map. -- -- > map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")] @@ -2458,16 +2411,11 @@ {-# NOINLINE [1] map #-} {-# RULES "map/map" forall f g xs . map f (map g xs) = map (f . g) xs- #-}-#endif-#if __GLASGOW_HASKELL__ >= 709--- Safe coercions were introduced in 7.8, but did not play well with RULES yet.-{-# RULES "map/coerce" map coerce = coerce  #-} #endif --- | /O(n)/. Map a function over all values in the map.+-- | \(O(n)\). Map a function over all values in the map. -- -- > let f key x = (show key) ++ ":" ++ x -- > mapWithKey f (fromList [(5,"a"), (3,"b")]) == fromList [(3, "3:b"), (5, "5:a")]@@ -2491,7 +2439,7 @@  #-} #endif --- | /O(n)/.+-- | \(O(n)\). -- @'traverseWithKey' f s == 'fromList' <$> 'traverse' (\(k, v) -> (,) k <$> f k v) ('toList' m)@ -- That is, behaves exactly like a regular 'traverse' except that the traversing -- function also has access to the key associated with a value.@@ -2508,7 +2456,7 @@       | otherwise = liftA2 (Bin p m) (go l) (go r) {-# INLINE traverseWithKey #-} --- | /O(n)/. The function @'mapAccum'@ threads an accumulating+-- | \(O(n)\). The function @'mapAccum'@ threads an accumulating -- argument through the map in ascending order of keys. -- -- > let f a b = (a ++ b, b ++ "X")@@ -2517,7 +2465,7 @@ mapAccum :: (a -> b -> (a,c)) -> a -> IntMap b -> (a,IntMap c) mapAccum f = mapAccumWithKey (\a' _ x -> f a' x) --- | /O(n)/. The function @'mapAccumWithKey'@ threads an accumulating+-- | \(O(n)\). The function @'mapAccumWithKey'@ threads an accumulating -- argument through the map in ascending order of keys. -- -- > let f a k b = (a ++ " " ++ (show k) ++ "-" ++ b, b ++ "X")@@ -2527,7 +2475,7 @@ mapAccumWithKey f a t   = mapAccumL f a t --- | /O(n)/. The function @'mapAccumL'@ threads an accumulating+-- | \(O(n)\). The function @'mapAccumL'@ threads an accumulating -- argument through the map in ascending order of keys. mapAccumL :: (a -> Key -> b -> (a,c)) -> a -> IntMap b -> (a,IntMap c) mapAccumL f a t@@ -2544,7 +2492,7 @@       Tip k x     -> let (a',x') = f a k x in (a',Tip k x')       Nil         -> (a,Nil) --- | /O(n)/. The function @'mapAccumRWithKey'@ threads an accumulating+-- | \(O(n)\). The function @'mapAccumRWithKey'@ threads an accumulating -- argument through the map in descending order of keys. mapAccumRWithKey :: (a -> Key -> b -> (a,c)) -> a -> IntMap b -> (a,IntMap c) mapAccumRWithKey f a t@@ -2561,7 +2509,7 @@       Tip k x     -> let (a',x') = f a k x in (a',Tip k x')       Nil         -> (a,Nil) --- | /O(n*min(n,W))/.+-- | \(O(n \min(n,W))\). -- @'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@@ -2575,7 +2523,7 @@ mapKeys :: (Key->Key) -> IntMap a -> IntMap a mapKeys f = fromList . foldrWithKey (\k x xs -> (f k, x) : xs) [] --- | /O(n*min(n,W))/.+-- | \(O(n \min(n,W))\). -- @'mapKeysWith' c 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@@ -2589,7 +2537,7 @@ mapKeysWith c f   = fromListWith c . foldrWithKey (\k x xs -> (f k, x) : xs) [] --- | /O(n*min(n,W))/.+-- | \(O(n \min(n,W))\). -- @'mapKeysMonotonic' f s == 'mapKeys' f s@, but works only when @f@ -- is strictly monotonic. -- That is, for any values @x@ and @y@, if @x@ < @y@ then @f x@ < @f y@.@@ -2612,7 +2560,7 @@ {--------------------------------------------------------------------   Filter --------------------------------------------------------------------}--- | /O(n)/. Filter all values that satisfy some predicate.+-- | \(O(n)\). Filter all values that satisfy some predicate. -- -- > filter (> "a") (fromList [(5,"a"), (3,"b")]) == singleton 3 "b" -- > filter (> "x") (fromList [(5,"a"), (3,"b")]) == empty@@ -2622,7 +2570,7 @@ filter p m   = filterWithKey (\_ x -> p x) m --- | /O(n)/. Filter all keys\/values that satisfy some predicate.+-- | \(O(n)\). Filter all keys\/values that satisfy some predicate. -- -- > filterWithKey (\k _ -> k > 4) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a" @@ -2633,7 +2581,7 @@     go t@(Tip k x)   = if predicate k x then t else Nil     go (Bin p m l r) = bin p m (go l) (go r) --- | /O(n)/. Partition the map according to some predicate. The first+-- | \(O(n)\). Partition the map according to some predicate. The first -- map contains all elements that satisfy the predicate, the second all -- elements that fail the predicate. See also 'split'. --@@ -2645,7 +2593,7 @@ partition p m   = partitionWithKey (\_ x -> p x) m --- | /O(n)/. Partition the map according to some predicate. The first+-- | \(O(n)\). Partition the map according to some predicate. The first -- map contains all elements that satisfy the predicate, the second all -- elements that fail the predicate. See also 'split'. --@@ -2667,7 +2615,7 @@           | otherwise     -> (Nil :*: t)         Nil -> (Nil :*: Nil) --- | /O(n)/. Map values and collect the 'Just' results.+-- | \(O(n)\). Map values and collect the 'Just' results. -- -- > let f x = if x == "a" then Just "new a" else Nothing -- > mapMaybe f (fromList [(5,"a"), (3,"b")]) == singleton 5 "new a"@@ -2675,7 +2623,7 @@ mapMaybe :: (a -> Maybe b) -> IntMap a -> IntMap b mapMaybe f = mapMaybeWithKey (\_ x -> f x) --- | /O(n)/. Map keys\/values and collect the 'Just' results.+-- | \(O(n)\). Map keys\/values and collect the 'Just' results. -- -- > let f k _ = if k < 5 then Just ("key : " ++ (show k)) else Nothing -- > mapMaybeWithKey f (fromList [(5,"a"), (3,"b")]) == singleton 3 "key : 3"@@ -2688,7 +2636,7 @@   Nothing -> Nil mapMaybeWithKey _ Nil = Nil --- | /O(n)/. Map values and separate the 'Left' and 'Right' results.+-- | \(O(n)\). Map values and separate the 'Left' and 'Right' results. -- -- > let f a = if a < "c" then Left a else Right a -- > mapEither f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])@@ -2701,7 +2649,7 @@ mapEither f m   = mapEitherWithKey (\_ x -> f x) m --- | /O(n)/. Map keys\/values and separate the 'Left' and 'Right' results.+-- | \(O(n)\). Map keys\/values and separate the 'Left' and 'Right' results. -- -- > let f k a = if k < 5 then Left (k * 2) else Right (a ++ a) -- > mapEitherWithKey f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])@@ -2723,7 +2671,7 @@       Right z -> (Nil :*: Tip k z)     go _ Nil = (Nil :*: Nil) --- | /O(min(n,W))/. The expression (@'split' k map@) is a pair @(map1,map2)@+-- | \(O(\min(n,W))\). The expression (@'split' k map@) is a pair @(map1,map2)@ -- where all keys in @map1@ are lower than @k@ and all keys in -- @map2@ larger than @k@. Any key equal to @k@ is found in neither @map1@ nor @map2@. --@@ -2773,7 +2721,7 @@ mapGT f (SplitLookup lt fnd gt) = SplitLookup lt fnd (f gt) {-# INLINE mapGT #-} --- | /O(min(n,W))/. Performs a 'split' but also returns whether the pivot+-- | \(O(\min(n,W))\). Performs a 'split' but also returns whether the pivot -- key was found in the original map. -- -- > splitLookup 2 (fromList [(5,"a"), (3,"b")]) == (empty, Nothing, fromList [(3,"b"), (5,"a")])@@ -2810,7 +2758,7 @@ {--------------------------------------------------------------------   Fold --------------------------------------------------------------------}--- | /O(n)/. Fold the values in the map using the given right-associative+-- | \(O(n)\). Fold the values in the map using the given right-associative -- binary operator, such that @'foldr' f z == 'Prelude.foldr' f z . 'elems'@. -- -- For example,@@ -2832,7 +2780,7 @@     go z' (Bin _ _ l r) = go (go z' r) l {-# INLINE foldr #-} --- | /O(n)/. A strict version of 'foldr'. Each application of the operator is+-- | \(O(n)\). A strict version of 'foldr'. Each application of the operator is -- evaluated before using the result in the next application. This -- function is strict in the starting value. foldr' :: (a -> b -> b) -> b -> IntMap a -> b@@ -2848,7 +2796,7 @@     go z' (Bin _ _ l r) = go (go z' r) l {-# INLINE foldr' #-} --- | /O(n)/. Fold the values in the map using the given left-associative+-- | \(O(n)\). Fold the values in the map using the given left-associative -- binary operator, such that @'foldl' f z == 'Prelude.foldl' f z . 'elems'@. -- -- For example,@@ -2870,7 +2818,7 @@     go z' (Bin _ _ l r) = go (go z' l) r {-# INLINE foldl #-} --- | /O(n)/. A strict version of 'foldl'. Each application of the operator is+-- | \(O(n)\). A strict version of 'foldl'. Each application of the operator is -- evaluated before using the result in the next application. This -- function is strict in the starting value. foldl' :: (a -> b -> a) -> a -> IntMap b -> a@@ -2886,7 +2834,7 @@     go z' (Bin _ _ l r) = go (go z' l) r {-# INLINE foldl' #-} --- | /O(n)/. Fold the keys and values in the map using the given right-associative+-- | \(O(n)\). Fold the keys and values in the map using the given right-associative -- binary operator, such that -- @'foldrWithKey' f z == 'Prelude.foldr' ('uncurry' f) z . 'toAscList'@. --@@ -2909,7 +2857,7 @@     go z' (Bin _ _ l r) = go (go z' r) l {-# INLINE foldrWithKey #-} --- | /O(n)/. A strict version of 'foldrWithKey'. Each application of the operator is+-- | \(O(n)\). A strict version of 'foldrWithKey'. Each application of the operator is -- evaluated before using the result in the next application. This -- function is strict in the starting value. foldrWithKey' :: (Key -> a -> b -> b) -> b -> IntMap a -> b@@ -2925,7 +2873,7 @@     go z' (Bin _ _ l r) = go (go z' r) l {-# INLINE foldrWithKey' #-} --- | /O(n)/. Fold the keys and values in the map using the given left-associative+-- | \(O(n)\). Fold the keys and values in the map using the given left-associative -- binary operator, such that -- @'foldlWithKey' f z == 'Prelude.foldl' (\\z' (kx, x) -> f z' kx x) z . 'toAscList'@. --@@ -2948,7 +2896,7 @@     go z' (Bin _ _ l r) = go (go z' l) r {-# INLINE foldlWithKey #-} --- | /O(n)/. A strict version of 'foldlWithKey'. Each application of the operator is+-- | \(O(n)\). A strict version of 'foldlWithKey'. Each application of the operator is -- evaluated before using the result in the next application. This -- function is strict in the starting value. foldlWithKey' :: (a -> Key -> b -> a) -> a -> IntMap b -> a@@ -2964,7 +2912,7 @@     go z' (Bin _ _ l r) = go (go z' l) r {-# INLINE foldlWithKey' #-} --- | /O(n)/. Fold the keys and values in the map using the given monoid, such that+-- | \(O(n)\). Fold the keys and values in the map using the given monoid, such that -- -- @'foldMapWithKey' f = 'Prelude.fold' . 'mapWithKey' f@ --@@ -2984,7 +2932,7 @@ {--------------------------------------------------------------------   List variations --------------------------------------------------------------------}--- | /O(n)/.+-- | \(O(n)\). -- Return all elements of the map in the ascending order of their keys. -- Subject to list fusion. --@@ -2994,7 +2942,7 @@ elems :: IntMap a -> [a] elems = foldr (:) [] --- | /O(n)/. Return all keys of the map in ascending order. Subject to list+-- | \(O(n)\). Return all keys of the map in ascending order. Subject to list -- fusion. -- -- > keys (fromList [(5,"a"), (3,"b")]) == [3,5]@@ -3003,7 +2951,7 @@ keys  :: IntMap a -> [Key] keys = foldrWithKey (\k _ ks -> k : ks) [] --- | /O(n)/. An alias for 'toAscList'. Returns all key\/value pairs in the+-- | \(O(n)\). An alias for 'toAscList'. Returns all key\/value pairs in the -- map in ascending key order. Subject to list fusion. -- -- > assocs (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]@@ -3012,7 +2960,7 @@ assocs :: IntMap a -> [(Key,a)] assocs = toAscList --- | /O(n*min(n,W))/. The set of all keys of the map.+-- | \(O(n \min(n,W))\). The set of all keys of the map. -- -- > keysSet (fromList [(5,"a"), (3,"b")]) == Data.IntSet.fromList [3,5] -- > keysSet empty == Data.IntSet.empty@@ -3027,7 +2975,7 @@         computeBm acc (Tip kx _) = acc .|. IntSet.bitmapOf kx         computeBm _   Nil = error "Data.IntSet.keysSet: Nil" --- | /O(n)/. Build a map from a set of keys and a function which for each key+-- | \(O(n)\). Build a map from a set of keys and a function which for each key -- computes its value. -- -- > fromSet (\k -> replicate k 'a') (Data.IntSet.fromList [3, 5]) == fromList [(5,"aaaaa"), (3,"aaa")]@@ -3062,7 +3010,8 @@ {--------------------------------------------------------------------   Lists --------------------------------------------------------------------}-#if __GLASGOW_HASKELL__ >= 708++#ifdef __GLASGOW_HASKELL__ -- | @since 0.5.6.2 instance GHCExts.IsList (IntMap a) where   type Item (IntMap a) = (Key,a)@@ -3070,7 +3019,7 @@   toList   = toList #endif --- | /O(n)/. Convert the map to a list of key\/value pairs. Subject to list+-- | \(O(n)\). Convert the map to a list of key\/value pairs. Subject to list -- fusion. -- -- > toList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]@@ -3079,7 +3028,7 @@ toList :: IntMap a -> [(Key,a)] toList = toAscList --- | /O(n)/. Convert the map to a list of key\/value pairs where the+-- | \(O(n)\). Convert the map to a list of key\/value pairs where the -- keys are in ascending order. Subject to list fusion. -- -- > toAscList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]@@ -3087,7 +3036,7 @@ toAscList :: IntMap a -> [(Key,a)] toAscList = foldrWithKey (\k x xs -> (k,x):xs) [] --- | /O(n)/. Convert the map to a list of key\/value pairs where the keys+-- | \(O(n)\). Convert the map to a list of key\/value pairs where the keys -- are in descending order. Subject to list fusion. -- -- > toDescList (fromList [(5,"a"), (3,"b")]) == [(5,"a"), (3,"b")]@@ -3131,7 +3080,7 @@ #endif  --- | /O(n*min(n,W))/. Create a map from a list of key\/value pairs.+-- | \(O(n \min(n,W))\). Create a map from a list of key\/value pairs. -- -- > fromList [] == empty -- > fromList [(5,"a"), (3,"b"), (5, "c")] == fromList [(5,"c"), (3,"b")]@@ -3143,7 +3092,7 @@   where     ins t (k,x)  = insert k x t --- | /O(n*min(n,W))/. Create a map from a list of key\/value pairs with a combining function. See also 'fromAscListWith'.+-- | \(O(n \min(n,W))\). Create a map from a list of key\/value pairs with a combining function. See also 'fromAscListWith'. -- -- > fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"c")] == fromList [(3, "ab"), (5, "cba")] -- > fromListWith (++) [] == empty@@ -3152,7 +3101,7 @@ fromListWith f xs   = fromListWithKey (\_ x y -> f x y) xs --- | /O(n*min(n,W))/. Build a map from a list of key\/value pairs with a combining function. See also fromAscListWithKey'.+-- | \(O(n \min(n,W))\). Build a map from a list of key\/value pairs with a combining function. See also fromAscListWithKey'. -- -- > let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value -- > fromListWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"c")] == fromList [(3, "3:a|b"), (5, "5:c|5:b|a")]@@ -3164,7 +3113,7 @@   where     ins t (k,x) = insertWithKey f k x t --- | /O(n)/. Build a map from a list of key\/value pairs where+-- | \(O(n)\). Build a map from a list of key\/value pairs where -- the keys are in ascending order. -- -- > fromAscList [(3,"b"), (5,"a")]          == fromList [(3, "b"), (5, "a")]@@ -3174,7 +3123,7 @@ fromAscList = fromMonoListWithKey Nondistinct (\_ x _ -> x) {-# NOINLINE fromAscList #-} --- | /O(n)/. Build a map from a list of key\/value pairs where+-- | \(O(n)\). Build a map from a list of key\/value pairs where -- the keys are in ascending order, with a combining function on equal keys. -- /The precondition (input list is ascending) is not checked./ --@@ -3184,7 +3133,7 @@ fromAscListWith f = fromMonoListWithKey Nondistinct (\_ x y -> f x y) {-# NOINLINE fromAscListWith #-} --- | /O(n)/. Build a map from a list of key\/value pairs where+-- | \(O(n)\). Build a map from a list of key\/value pairs where -- the keys are in ascending order, with a combining function on equal keys. -- /The precondition (input list is ascending) is not checked./ --@@ -3195,7 +3144,7 @@ fromAscListWithKey f = fromMonoListWithKey Nondistinct f {-# NOINLINE fromAscListWithKey #-} --- | /O(n)/. Build a map from a list of key\/value pairs where+-- | \(O(n)\). Build a map from a list of key\/value pairs where -- the keys are in ascending order and all distinct. -- /The precondition (input list is strictly ascending) is not checked./ --@@ -3205,7 +3154,7 @@ fromDistinctAscList = fromMonoListWithKey Distinct (\_ x _ -> x) {-# NOINLINE fromDistinctAscList #-} --- | /O(n)/. Build a map from a list of key\/value pairs with monotonic keys+-- | \(O(n)\). Build a map from a list of key\/value pairs with monotonic keys -- and a combining function. -- -- The precise conditions under which this function works are subtle:@@ -3290,7 +3239,6 @@ nequal Nil Nil = False nequal _   _   = True -#if MIN_VERSION_base(4,9,0) -- | @since 0.5.9 instance Eq1 IntMap where   liftEq eq (Bin p1 m1 l1 r1) (Bin p2 m2 l2 r2)@@ -3299,7 +3247,6 @@     = (kx == ky) && (eq x y)   liftEq _eq Nil Nil = True   liftEq _eq _   _   = False-#endif  {--------------------------------------------------------------------   Ord@@ -3308,12 +3255,10 @@ instance Ord a => Ord (IntMap a) where     compare m1 m2 = compare (toList m1) (toList m2) -#if MIN_VERSION_base(4,9,0) -- | @since 0.5.9 instance Ord1 IntMap where   liftCompare cmp m n =     liftCompare (liftCompare cmp) (toList m) (toList n)-#endif  {--------------------------------------------------------------------   Functor@@ -3336,7 +3281,6 @@   showsPrec d m   = showParen (d > 10) $     showString "fromList " . shows (toList m) -#if MIN_VERSION_base(4,9,0) -- | @since 0.5.9 instance Show1 IntMap where     liftShowsPrec sp sl d m =@@ -3344,7 +3288,6 @@       where         sp' = liftShowsPrec sp sl         sl' = liftShowList sp sl-#endif  {--------------------------------------------------------------------   Read@@ -3364,7 +3307,6 @@     return (fromList xs,t) #endif -#if MIN_VERSION_base(4,9,0) -- | @since 0.5.9 instance Read1 IntMap where     liftReadsPrec rp rl = readsData $@@ -3372,15 +3314,8 @@       where         rp' = liftReadsPrec rp rl         rl' = liftReadList rp rl-#endif  {---------------------------------------------------------------------  Typeable---------------------------------------------------------------------}--INSTANCE_TYPEABLE1(IntMap)--{--------------------------------------------------------------------   Helpers --------------------------------------------------------------------} {--------------------------------------------------------------------@@ -3481,7 +3416,7 @@   Utilities --------------------------------------------------------------------} --- | /O(1)/.  Decompose a map into pieces based on the structure+-- | \(O(1)\).  Decompose a map into pieces based on the structure -- of the underlying tree. This function is useful for consuming a -- map in parallel. --@@ -3514,14 +3449,14 @@   Debugging --------------------------------------------------------------------} --- | /O(n)/. Show the tree that implements the map. The tree is shown+-- | \(O(n)\). Show the tree that implements the map. The tree is shown -- in a compressed, hanging format. showTree :: Show a => IntMap a -> String showTree s   = showTreeWith True False s  -{- | /O(n)/. The expression (@'showTreeWith' hang wide map@) shows+{- | \(O(n)\). The expression (@'showTreeWith' hang wide map@) shows  the tree that implements the map. If @hang@ is  'True', a /hanging/ tree is shown otherwise a rotated tree is shown. If  @wide@ is 'True', an extra wide version is shown.

@@ -40,8 +40,8 @@ -- -- == Detailed performance information ----- The amortized running time is given for each operation, with /n/ referring to--- the number of entries in the map and /W/ referring to the number of bits in+-- The amortized running time is given for each operation, with \(n\) referring to+-- the number of entries in the map and \(W\) referring to the number of bits in -- an 'Int' (32 or 64). -- -- Benchmarks comparing "Data.IntMap.Lazy" with other dictionary

@@ -1,19 +1,6 @@ {-# LANGUAGE CPP #-}-{-# LANGUAGE BangPatterns #-}-#if __GLASGOW_HASKELL__-{-# LANGUAGE DeriveDataTypeable, StandaloneDeriving #-}-#endif #if !defined(TESTING) && defined(__GLASGOW_HASKELL__) {-# LANGUAGE Safe #-}-#endif-#if __GLASGOW_HASKELL__ >= 708-{-# LANGUAGE RoleAnnotations #-}-{-# LANGUAGE TypeFamilies #-}-#define USE_MAGIC_PROXY 1-#endif--#if USE_MAGIC_PROXY-{-# LANGUAGE MagicHash #-} #endif  #include "containers.h"

@@ -1,21 +1,9 @@ {-# LANGUAGE CPP #-} {-# LANGUAGE BangPatterns #-}-#if __GLASGOW_HASKELL__-{-# LANGUAGE DeriveDataTypeable, StandaloneDeriving #-}-#endif #if !defined(TESTING) && defined(__GLASGOW_HASKELL__) {-# LANGUAGE Trustworthy #-} #endif-#if __GLASGOW_HASKELL__ >= 708-{-# LANGUAGE RoleAnnotations #-}-{-# LANGUAGE TypeFamilies #-}-#define USE_MAGIC_PROXY 1-#endif -#if USE_MAGIC_PROXY-{-# LANGUAGE MagicHash #-}-#endif- #include "containers.h"  -----------------------------------------------------------------------------@@ -112,9 +100,6 @@   , runWhenMissing   ) import Data.IntMap.Strict.Internal-#if !MIN_VERSION_base(4,8,0)-import Control.Applicative (Applicative (..), (<$>))-#endif import Prelude hiding (filter, map, foldl, foldr)  -- | Map covariantly over a @'WhenMissing' f k x@.

@@ -48,8 +48,8 @@ -- -- == Detailed performance information ----- The amortized running time is given for each operation, with /n/ referring to--- the number of entries in the map and /W/ referring to the number of bits in+-- The amortized running time is given for each operation, with \(n\) referring to+-- the number of entries in the map and \(W\) referring to the number of bits in -- an 'Int' (32 or 64). -- -- Benchmarks comparing "Data.IntMap.Strict" with other dictionary

@@ -48,8 +48,8 @@ -- -- == Detailed performance information ----- The amortized running time is given for each operation, with /n/ referring to--- the number of entries in the map and /W/ referring to the number of bits in+-- The amortized running time is given for each operation, with \(n\) referring to+-- the number of entries in the map and \(W\) referring to the number of bits in -- an 'Int' (32 or 64). -- -- Benchmarks comparing "Data.IntMap.Strict" with other dictionary@@ -345,20 +345,14 @@ import qualified Data.IntSet.Internal as IntSet import Utils.Containers.Internal.BitUtil import Utils.Containers.Internal.StrictPair-#if !MIN_VERSION_base(4,8,0)-import Data.Functor((<$>))-#endif import Control.Applicative (Applicative (..), liftA2) import qualified Data.Foldable as Foldable-#if !MIN_VERSION_base(4,8,0)-import Data.Foldable (Foldable())-#endif  {--------------------------------------------------------------------   Query --------------------------------------------------------------------} --- | /O(min(n,W))/. The expression @('findWithDefault' def k map)@+-- | \(O(\min(n,W))\). The expression @('findWithDefault' def k map)@ -- returns the value at key @k@ or returns @def@ when the key is not an -- element of the map. --@@ -379,7 +373,7 @@ {--------------------------------------------------------------------   Construction --------------------------------------------------------------------}--- | /O(1)/. A map of one element.+-- | \(O(1)\). A map of one element. -- -- > singleton 1 'a'        == fromList [(1, 'a')] -- > size (singleton 1 'a') == 1@@ -392,7 +386,7 @@ {--------------------------------------------------------------------   Insert --------------------------------------------------------------------}--- | /O(min(n,W))/. Insert a new key\/value pair in the map.+-- | \(O(\min(n,W))\). Insert a new key\/value pair in the map. -- If the key is already present in the map, the associated value is -- replaced with the supplied value, i.e. 'insert' is equivalent to -- @'insertWith' 'const'@.@@ -414,7 +408,7 @@     Nil -> Tip k x  -- right-biased insertion, used by 'union'--- | /O(min(n,W))/. Insert with a combining function.+-- | \(O(\min(n,W))\). Insert with a combining function. -- @'insertWith' f key value mp@ -- will insert the pair (key, value) into @mp@ if key does -- not exist in the map. If the key does exist, the function will@@ -428,7 +422,7 @@ insertWith f k x t   = insertWithKey (\_ x' y' -> f x' y') k x t --- | /O(min(n,W))/. Insert with a combining function.+-- | \(O(\min(n,W))\). Insert with a combining function. -- @'insertWithKey' f key value mp@ -- will insert the pair (key, value) into @mp@ if key does -- not exist in the map. If the key does exist, the function will@@ -454,7 +448,7 @@       | otherwise     -> link k (singleton k x) ky t     Nil -> singleton k x --- | /O(min(n,W))/. The expression (@'insertLookupWithKey' f k x map@)+-- | \(O(\min(n,W))\). The expression (@'insertLookupWithKey' f k x map@) -- is a pair where the first element is equal to (@'lookup' k map@) -- and the second element equal to (@'insertWithKey' f k x map@). --@@ -487,7 +481,7 @@ {--------------------------------------------------------------------   Deletion --------------------------------------------------------------------}--- | /O(min(n,W))/. Adjust a value at a specific key. When the key is not+-- | \(O(\min(n,W))\). Adjust a value at a specific key. When the key is not -- a member of the map, the original map is returned. -- -- > adjust ("new " ++) 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]@@ -498,7 +492,7 @@ adjust f k m   = adjustWithKey (\_ x -> f x) k m --- | /O(min(n,W))/. Adjust a value at a specific key. When the key is not+-- | \(O(\min(n,W))\). Adjust a value at a specific key. When the key is not -- a member of the map, the original map is returned. -- -- > let f key x = (show key) ++ ":new " ++ x@@ -518,7 +512,7 @@       | otherwise     -> t     Nil -> Nil --- | /O(min(n,W))/. The expression (@'update' f k map@) updates the value @x@+-- | \(O(\min(n,W))\). 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@. --@@ -531,7 +525,7 @@ update f   = updateWithKey (\_ x -> f x) --- | /O(min(n,W))/. The expression (@'update' f k map@) updates the value @x@+-- | \(O(\min(n,W))\). The expression (@'update' f k map@) updates the value @x@ -- at @k@ (if it is in the map). If (@f k x@) is 'Nothing', the element is -- deleted. If it is (@'Just' y@), the key @k@ is bound to the new value @y@. --@@ -554,7 +548,7 @@       | otherwise     -> t     Nil -> Nil --- | /O(min(n,W))/. Lookup and update.+-- | \(O(\min(n,W))\). Lookup and update. -- The function returns original value, if it is updated. -- This is different behavior than 'Data.Map.updateLookupWithKey'. -- Returns the original key value if the map entry is deleted.@@ -582,7 +576,7 @@   --- | /O(min(n,W))/. The expression (@'alter' f k map@) alters the value @x@ at @k@, or absence thereof.+-- | \(O(\min(n,W))\). 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 an 'IntMap'. -- In short : @'lookup' k ('alter' f k m) = f ('lookup' k m)@. alter :: (Maybe a -> Maybe a) -> Key -> IntMap a -> IntMap a@@ -605,7 +599,7 @@                            Just !x -> Tip k x                            Nothing -> Nil --- | /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 inspect, insert, delete, -- or update a value in an 'IntMap'.  In short : @'lookup' k <$> 'alterF' f k m = f -- ('lookup' k m)@.@@ -655,7 +649,7 @@ unionsWith f ts   = Foldable.foldl' (unionWith f) empty ts --- | /O(n+m)/. The union with a combining function.+-- | \(O(n+m)\). The union with a combining function. -- -- > unionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")] @@ -663,7 +657,7 @@ unionWith f m1 m2   = unionWithKey (\_ x y -> f x y) m1 m2 --- | /O(n+m)/. The union with a combining function.+-- | \(O(n+m)\). The union with a combining function. -- -- > let f key left_value right_value = (show key) ++ ":" ++ left_value ++ "|" ++ right_value -- > unionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "5:a|A"), (7, "C")]@@ -676,7 +670,7 @@   Difference --------------------------------------------------------------------} --- | /O(n+m)/. Difference with a combining function.+-- | \(O(n+m)\). Difference with a combining function. -- -- > let f al ar = if al == "b" then Just (al ++ ":" ++ ar) else Nothing -- > differenceWith f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (7, "C")])@@ -686,7 +680,7 @@ differenceWith f m1 m2   = differenceWithKey (\_ x y -> f x y) m1 m2 --- | /O(n+m)/. Difference with a combining function. When two equal keys are+-- | \(O(n+m)\). Difference with a combining function. When two equal keys are -- encountered, the combining function is applied to the key and both values. -- 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@.@@ -703,7 +697,7 @@   Intersection --------------------------------------------------------------------} --- | /O(n+m)/. The intersection with a combining function.+-- | \(O(n+m)\). The intersection with a combining function. -- -- > intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "aA" @@ -711,7 +705,7 @@ intersectionWith f m1 m2   = intersectionWithKey (\_ x y -> f x y) m1 m2 --- | /O(n+m)/. The intersection with a combining function.+-- | \(O(n+m)\). The intersection with a combining function. -- -- > let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ ar -- > intersectionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "5:a|A"@@ -724,7 +718,7 @@   MergeWithKey --------------------------------------------------------------------} --- | /O(n+m)/. A high-performance universal combining function. Using+-- | \(O(n+m)\). A high-performance universal combining function. Using -- 'mergeWithKey', all combining functions can be defined without any loss of -- efficiency (with exception of 'union', 'difference' and 'intersection', -- where sharing of some nodes is lost with 'mergeWithKey').@@ -773,7 +767,7 @@   Min\/Max --------------------------------------------------------------------} --- | /O(log n)/. Update the value at the minimal key.+-- | \(O(\log n)\). Update the value at the minimal key. -- -- > updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"3:b"), (5,"a")] -- > updateMinWithKey (\ _ _ -> Nothing)                     (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"@@ -789,7 +783,7 @@                         Nothing -> Nil     go _ Nil = error "updateMinWithKey Nil" --- | /O(log n)/. Update the value at the maximal key.+-- | \(O(\log n)\). Update the value at the maximal key. -- -- > updateMaxWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"b"), (5,"5:a")] -- > updateMaxWithKey (\ _ _ -> Nothing)                     (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"@@ -805,7 +799,7 @@                         Nothing -> Nil     go _ Nil = error "updateMaxWithKey Nil" --- | /O(log n)/. Update the value at the maximal key.+-- | \(O(\log n)\). Update the value at the maximal key. -- -- > updateMax (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "Xa")] -- > updateMax (\ _ -> Nothing)         (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"@@ -813,7 +807,7 @@ updateMax :: (a -> Maybe a) -> IntMap a -> IntMap a updateMax f = updateMaxWithKey (const f) --- | /O(log n)/. Update the value at the minimal key.+-- | \(O(\log n)\). Update the value at the minimal key. -- -- > updateMin (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "Xb"), (5, "a")] -- > updateMin (\ _ -> Nothing)         (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"@@ -825,7 +819,7 @@ {--------------------------------------------------------------------   Mapping --------------------------------------------------------------------}--- | /O(n)/. Map a function over all values in the map.+-- | \(O(n)\). Map a function over all values in the map. -- -- > map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")] @@ -844,7 +838,7 @@  #-} #endif --- | /O(n)/. Map a function over all values in the map.+-- | \(O(n)\). Map a function over all values in the map. -- -- > let f key x = (show key) ++ ":" ++ x -- > mapWithKey f (fromList [(5,"a"), (3,"b")]) == fromList [(3, "3:b"), (5, "5:a")]@@ -886,7 +880,7 @@  #-} #endif --- | /O(n)/.+-- | \(O(n)\). -- @'traverseWithKey' f s == 'fromList' <$> 'traverse' (\(k, v) -> (,) k <$> f k v) ('toList' m)@ -- That is, behaves exactly like a regular 'traverse' except that the traversing -- function also has access to the key associated with a value.@@ -903,7 +897,7 @@       | otherwise = liftA2 (Bin p m) (go l) (go r) {-# INLINE traverseWithKey #-} --- | /O(n)/. Traverse keys\/values and collect the 'Just' results.+-- | \(O(n)\). Traverse keys\/values and collect the 'Just' results. -- -- @since 0.6.4 traverseMaybeWithKey@@ -916,7 +910,7 @@       | m < 0     = liftA2 (flip (bin p m)) (go r) (go l)       | otherwise = liftA2 (bin p m) (go l) (go r) --- | /O(n)/. The function @'mapAccum'@ threads an accumulating+-- | \(O(n)\). The function @'mapAccum'@ threads an accumulating -- argument through the map in ascending order of keys. -- -- > let f a b = (a ++ b, b ++ "X")@@ -925,7 +919,7 @@ mapAccum :: (a -> b -> (a,c)) -> a -> IntMap b -> (a,IntMap c) mapAccum f = mapAccumWithKey (\a' _ x -> f a' x) --- | /O(n)/. The function @'mapAccumWithKey'@ threads an accumulating+-- | \(O(n)\). The function @'mapAccumWithKey'@ threads an accumulating -- argument through the map in ascending order of keys. -- -- > let f a k b = (a ++ " " ++ (show k) ++ "-" ++ b, b ++ "X")@@ -935,7 +929,7 @@ mapAccumWithKey f a t   = mapAccumL f a t --- | /O(n)/. The function @'mapAccumL'@ threads an accumulating+-- | \(O(n)\). The function @'mapAccumL'@ threads an accumulating -- argument through the map in ascending order of keys.  Strict in -- the accumulating argument and the both elements of the -- result of the function.@@ -956,7 +950,7 @@           Tip k x     -> let !(a',!x') = f a k x in (a' :*: Tip k x')           Nil         -> (a :*: Nil) --- | /O(n)/. The function @'mapAccumRWithKey'@ threads an accumulating+-- | \(O(n)\). The function @'mapAccumRWithKey'@ threads an accumulating -- argument through the map in descending order of keys. mapAccumRWithKey :: (a -> Key -> b -> (a,c)) -> a -> IntMap b -> (a,IntMap c) mapAccumRWithKey f0 a0 t0 = toPair $ go f0 a0 t0@@ -975,7 +969,7 @@           Tip k x     -> let !(a',!x') = f a k x in (a' :*: Tip k x')           Nil         -> (a :*: Nil) --- | /O(n*log n)/.+-- | \(O(n \log n)\). -- @'mapKeysWith' c 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@@ -991,7 +985,7 @@ {--------------------------------------------------------------------   Filter --------------------------------------------------------------------}--- | /O(n)/. Map values and collect the 'Just' results.+-- | \(O(n)\). Map values and collect the 'Just' results. -- -- > let f x = if x == "a" then Just "new a" else Nothing -- > mapMaybe f (fromList [(5,"a"), (3,"b")]) == singleton 5 "new a"@@ -999,7 +993,7 @@ mapMaybe :: (a -> Maybe b) -> IntMap a -> IntMap b mapMaybe f = mapMaybeWithKey (\_ x -> f x) --- | /O(n)/. Map keys\/values and collect the 'Just' results.+-- | \(O(n)\). Map keys\/values and collect the 'Just' results. -- -- > let f k _ = if k < 5 then Just ("key : " ++ (show k)) else Nothing -- > mapMaybeWithKey f (fromList [(5,"a"), (3,"b")]) == singleton 3 "key : 3"@@ -1012,7 +1006,7 @@   Nothing -> Nil mapMaybeWithKey _ Nil = Nil --- | /O(n)/. Map values and separate the 'Left' and 'Right' results.+-- | \(O(n)\). Map values and separate the 'Left' and 'Right' results. -- -- > let f a = if a < "c" then Left a else Right a -- > mapEither f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])@@ -1025,7 +1019,7 @@ mapEither f m   = mapEitherWithKey (\_ x -> f x) m --- | /O(n)/. Map keys\/values and separate the 'Left' and 'Right' results.+-- | \(O(n)\). Map keys\/values and separate the 'Left' and 'Right' results. -- -- > let f k a = if k < 5 then Left (k * 2) else Right (a ++ a) -- > mapEitherWithKey f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])@@ -1051,7 +1045,7 @@   Conversions --------------------------------------------------------------------} --- | /O(n)/. Build a map from a set of keys and a function which for each key+-- | \(O(n)\). Build a map from a set of keys and a function which for each key -- computes its value. -- -- > fromSet (\k -> replicate k 'a') (Data.IntSet.fromList [3, 5]) == fromList [(5,"aaaaa"), (3,"aaa")]@@ -1081,7 +1075,7 @@ {--------------------------------------------------------------------   Lists --------------------------------------------------------------------}--- | /O(n*min(n,W))/. Create a map from a list of key\/value pairs.+-- | \(O(n \min(n,W))\). Create a map from a list of key\/value pairs. -- -- > fromList [] == empty -- > fromList [(5,"a"), (3,"b"), (5, "c")] == fromList [(5,"c"), (3,"b")]@@ -1093,7 +1087,7 @@   where     ins t (k,x)  = insert k x t --- | /O(n*min(n,W))/. Create a map from a list of key\/value pairs with a combining function. See also 'fromAscListWith'.+-- | \(O(n \min(n,W))\). Create a map from a list of key\/value pairs with a combining function. See also 'fromAscListWith'. -- -- > fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")] -- > fromListWith (++) [] == empty@@ -1102,7 +1096,7 @@ fromListWith f xs   = fromListWithKey (\_ x y -> f x y) xs --- | /O(n*min(n,W))/. Build a map from a list of key\/value pairs with a combining function. See also fromAscListWithKey'.+-- | \(O(n \min(n,W))\). Build a map from a list of key\/value pairs with a combining function. See also fromAscListWithKey'. -- -- > fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")] -- > fromListWith (++) [] == empty@@ -1113,7 +1107,7 @@   where     ins t (k,x) = insertWithKey f k x t --- | /O(n)/. Build a map from a list of key\/value pairs where+-- | \(O(n)\). Build a map from a list of key\/value pairs where -- the keys are in ascending order. -- -- > fromAscList [(3,"b"), (5,"a")]          == fromList [(3, "b"), (5, "a")]@@ -1123,7 +1117,7 @@ fromAscList = fromMonoListWithKey Nondistinct (\_ x _ -> x) {-# NOINLINE fromAscList #-} --- | /O(n)/. Build a map from a list of key\/value pairs where+-- | \(O(n)\). Build a map from a list of key\/value pairs where -- the keys are in ascending order, with a combining function on equal keys. -- /The precondition (input list is ascending) is not checked./ --@@ -1133,7 +1127,7 @@ fromAscListWith f = fromMonoListWithKey Nondistinct (\_ x y -> f x y) {-# NOINLINE fromAscListWith #-} --- | /O(n)/. Build a map from a list of key\/value pairs where+-- | \(O(n)\). Build a map from a list of key\/value pairs where -- the keys are in ascending order, with a combining function on equal keys. -- /The precondition (input list is ascending) is not checked./ --@@ -1143,7 +1137,7 @@ fromAscListWithKey f = fromMonoListWithKey Nondistinct f {-# NOINLINE fromAscListWithKey #-} --- | /O(n)/. Build a map from a list of key\/value pairs where+-- | \(O(n)\). Build a map from a list of key\/value pairs where -- the keys are in ascending order and all distinct. -- /The precondition (input list is strictly ascending) is not checked./ --@@ -1153,7 +1147,7 @@ fromDistinctAscList = fromMonoListWithKey Distinct (\_ x _ -> x) {-# NOINLINE fromDistinctAscList #-} --- | /O(n)/. Build a map from a list of key\/value pairs with monotonic keys+-- | \(O(n)\). Build a map from a list of key\/value pairs with monotonic keys -- and a combining function. -- -- The precise conditions under which this function works are subtle:

@@ -31,9 +31,9 @@ -- -- == Performance information ----- Many operations have a worst-case complexity of /O(min(n,W))/.+-- Many operations have a worst-case complexity of \(O(\min(n,W))\). -- This means that the operation can become linear in the number of--- elements with a maximum of /W/ -- the number of bits in an 'Int'+-- elements with a maximum of \(W\) -- the number of bits in an 'Int' -- (32 or 64). -- --

@@ -1,15 +1,15 @@ {-# LANGUAGE CPP #-} {-# LANGUAGE BangPatterns #-} {-# LANGUAGE PatternGuards #-}-#if __GLASGOW_HASKELL__-{-# LANGUAGE MagicHash, DeriveDataTypeable, StandaloneDeriving #-}+#ifdef __GLASGOW_HASKELL__+{-# LANGUAGE DeriveLift #-}+{-# LANGUAGE MagicHash #-}+{-# LANGUAGE StandaloneDeriving #-}+{-# LANGUAGE TypeFamilies #-} #endif #if !defined(TESTING) && defined(__GLASGOW_HASKELL__) {-# LANGUAGE Trustworthy #-} #endif-#if __GLASGOW_HASKELL__ >= 708-{-# LANGUAGE TypeFamilies #-}-#endif  {-# OPTIONS_HADDOCK not-home #-} @@ -65,9 +65,9 @@ -- it is likely that many values lie close to each other. The asymptotics are -- not affected by this optimization. ----- Many operations have a worst-case complexity of /O(min(n,W))/.+-- Many operations have a worst-case complexity of \(O(\min(n,W))\). -- This means that the operation can become linear in the number of--- elements with a maximum of /W/ -- the number of bits in an 'Int'+-- elements with a maximum of \(W\) -- the number of bits in an 'Int' -- (32 or 64). -- -- @since 0.5.9@@ -193,20 +193,11 @@ import Data.Bits import qualified Data.List as List import Data.Maybe (fromMaybe)-#if !MIN_VERSION_base(4,8,0)-import Data.Monoid (Monoid(..))-import Data.Word (Word)-#endif-#if MIN_VERSION_base(4,9,0) import Data.Semigroup (Semigroup(stimes))-#endif-#if !(MIN_VERSION_base(4,11,0)) && MIN_VERSION_base(4,9,0)+#if !(MIN_VERSION_base(4,11,0)) import Data.Semigroup (Semigroup((<>))) #endif-#if MIN_VERSION_base(4,9,0) import Data.Semigroup (stimesIdempotentMonoid)-#endif-import Data.Typeable import Prelude hiding (filter, foldr, foldl, null, map)  import Utils.Containers.Internal.BitUtil@@ -220,17 +211,14 @@  #if __GLASGOW_HASKELL__ import qualified GHC.Exts-#if !(MIN_VERSION_base(4,8,0) && (WORD_SIZE_IN_BITS==64))+#  if !(WORD_SIZE_IN_BITS==64) import qualified GHC.Int-#endif+#  endif+import Language.Haskell.TH.Syntax (Lift) #endif  import qualified Data.Foldable as Foldable-#if MIN_VERSION_base(4,8,0) import Data.Functor.Identity (Identity(..))-#else-import Data.Foldable (Foldable())-#endif  infixl 9 \\{-This comment teaches CPP correct behaviour -} @@ -248,7 +236,7 @@ {--------------------------------------------------------------------   Operators --------------------------------------------------------------------}--- | /O(n+m)/. See 'difference'.+-- | \(O(n+m)\). See 'difference'. (\\) :: IntSet -> IntSet -> IntSet m1 \\ m2 = difference m1 m2 @@ -283,19 +271,20 @@ type BitMap = Word type Key    = Int +#ifdef __GLASGOW_HASKELL__+-- | @since FIXME+deriving instance Lift IntSet+#endif+ instance Monoid IntSet where     mempty  = empty     mconcat = unions-#if !(MIN_VERSION_base(4,9,0))-    mappend = union-#else     mappend = (<>)  -- | @since 0.5.7 instance Semigroup IntSet where     (<>)    = union     stimes  = stimesIdempotentMonoid-#endif  #if __GLASGOW_HASKELL__ @@ -325,13 +314,13 @@ {--------------------------------------------------------------------   Query --------------------------------------------------------------------}--- | /O(1)/. Is the set empty?+-- | \(O(1)\). Is the set empty? null :: IntSet -> Bool null Nil = True null _   = False {-# INLINE null #-} --- | /O(n)/. Cardinality of the set.+-- | \(O(n)\). Cardinality of the set. size :: IntSet -> Int size = go 0   where@@ -339,7 +328,7 @@     go acc (Tip _ bm) = acc + bitcount 0 bm     go acc Nil = acc --- | /O(min(n,W))/. Is the value a member of the set?+-- | \(O(\min(n,W))\). Is the value a member of the set?  -- See Note: Local 'go' functions and capturing. member :: Key -> IntSet -> Bool@@ -352,11 +341,11 @@     go (Tip y bm) = prefixOf x == y && bitmapOf x .&. bm /= 0     go Nil = False --- | /O(min(n,W))/. Is the element not in the set?+-- | \(O(\min(n,W))\). Is the element not in the set? notMember :: Key -> IntSet -> Bool notMember k = not . member k --- | /O(log n)/. Find largest element smaller than the given one.+-- | \(O(\log n)\). Find largest element smaller than the given one. -- -- > lookupLT 3 (fromList [3, 5]) == Nothing -- > lookupLT 5 (fromList [3, 5]) == Just 3@@ -377,7 +366,7 @@     go def Nil = unsafeFindMax def  --- | /O(log n)/. Find smallest element greater than the given one.+-- | \(O(\log n)\). Find smallest element greater than the given one. -- -- > lookupGT 4 (fromList [3, 5]) == Just 5 -- > lookupGT 5 (fromList [3, 5]) == Nothing@@ -398,7 +387,7 @@     go def Nil = unsafeFindMin def  --- | /O(log n)/. Find largest element smaller or equal to the given one.+-- | \(O(\log n)\). Find largest element smaller or equal to the given one. -- -- > lookupLE 2 (fromList [3, 5]) == Nothing -- > lookupLE 4 (fromList [3, 5]) == Just 3@@ -420,7 +409,7 @@     go def Nil = unsafeFindMax def  --- | /O(log n)/. Find smallest element greater or equal to the given one.+-- | \(O(\log n)\). Find smallest element greater or equal to the given one. -- -- > lookupGE 3 (fromList [3, 5]) == Just 3 -- > lookupGE 4 (fromList [3, 5]) == Just 5@@ -460,13 +449,13 @@ {--------------------------------------------------------------------   Construction --------------------------------------------------------------------}--- | /O(1)/. The empty set.+-- | \(O(1)\). The empty set. empty :: IntSet empty   = Nil {-# INLINE empty #-} --- | /O(1)/. A set of one element.+-- | \(O(1)\). A set of one element. singleton :: Key -> IntSet singleton x   = Tip (prefixOf x) (bitmapOf x)@@ -475,7 +464,7 @@ {--------------------------------------------------------------------   Insert --------------------------------------------------------------------}--- | /O(min(n,W))/. Add a value to the set. There is no left- or right bias for+-- | \(O(\min(n,W))\). Add a value to the set. There is no left- or right bias for -- IntSets. insert :: Key -> IntSet -> IntSet insert !x = insertBM (prefixOf x) (bitmapOf x)@@ -491,7 +480,7 @@   | otherwise = link kx (Tip kx bm) kx' t insertBM kx bm Nil = Tip kx bm --- | /O(min(n,W))/. Delete a value in the set. Returns the+-- | \(O(\min(n,W))\). Delete a value in the set. Returns the -- original set when the value was not present. delete :: Key -> IntSet -> IntSet delete !x = deleteBM (prefixOf x) (bitmapOf x)@@ -508,7 +497,7 @@   | otherwise = t deleteBM _ _ Nil = Nil --- | /O(min(n,W))/. @('alterF' f x s)@ can delete or insert @x@ in @s@ depending+-- | \(O(\min(n,W))\). @('alterF' f x s)@ can delete or insert @x@ in @s@ depending -- on whether it is already present in @s@. -- -- In short:@@ -541,9 +530,7 @@  #-} #endif -#if MIN_VERSION_base(4,8,0) {-# SPECIALIZE alterF :: (Bool -> Identity Bool) -> Key -> IntSet -> Identity IntSet #-}-#endif  {--------------------------------------------------------------------   Union@@ -554,7 +541,7 @@   = Foldable.foldl' union empty xs  --- | /O(n+m)/. The union of two sets.+-- | \(O(n+m)\). The union of two sets. union :: IntSet -> IntSet -> IntSet union t1@(Bin p1 m1 l1 r1) t2@(Bin p2 m2 l2 r2)   | shorter m1 m2  = union1@@ -579,7 +566,7 @@ {--------------------------------------------------------------------   Difference --------------------------------------------------------------------}--- | /O(n+m)/. Difference between two sets.+-- | \(O(n+m)\). Difference between two sets. difference :: IntSet -> IntSet -> IntSet difference t1@(Bin p1 m1 l1 r1) t2@(Bin p2 m2 l2 r2)   | shorter m1 m2  = difference1@@ -613,7 +600,7 @@ {--------------------------------------------------------------------   Intersection --------------------------------------------------------------------}--- | /O(n+m)/. The intersection of two sets.+-- | \(O(n+m)\). The intersection of two sets. intersection :: IntSet -> IntSet -> IntSet intersection t1@(Bin p1 m1 l1 r1) t2@(Bin p2 m2 l2 r2)   | shorter m1 m2  = intersection1@@ -652,7 +639,7 @@ {--------------------------------------------------------------------   Subset --------------------------------------------------------------------}--- | /O(n+m)/. Is this a proper subset? (ie. a subset but not equal).+-- | \(O(n+m)\). Is this a proper subset? (ie. a subset but not equal). isProperSubsetOf :: IntSet -> IntSet -> Bool isProperSubsetOf t1 t2   = case subsetCmp t1 t2 of@@ -691,7 +678,7 @@ subsetCmp Nil Nil = EQ subsetCmp Nil _   = LT --- | /O(n+m)/. Is this a subset?+-- | \(O(n+m)\). Is this a subset? -- @(s1 \`isSubsetOf\` s2)@ tells whether @s1@ is a subset of @s2@.  isSubsetOf :: IntSet -> IntSet -> Bool@@ -713,7 +700,7 @@ {--------------------------------------------------------------------   Disjoint --------------------------------------------------------------------}--- | /O(n+m)/. Check whether two sets are disjoint (i.e. their intersection+-- | \(O(n+m)\). Check whether two sets are disjoint (i.e. their intersection --   is empty). -- -- > disjoint (fromList [2,4,6])   (fromList [1,3])     == True@@ -761,7 +748,7 @@ {--------------------------------------------------------------------   Filter --------------------------------------------------------------------}--- | /O(n)/. Filter all elements that satisfy some predicate.+-- | \(O(n)\). Filter all elements that satisfy some predicate. filter :: (Key -> Bool) -> IntSet -> IntSet filter predicate t   = case t of@@ -774,7 +761,7 @@                          | otherwise           = bm         {-# INLINE bitPred #-} --- | /O(n)/. partition the set according to some predicate.+-- | \(O(n)\). partition the set according to some predicate. partition :: (Key -> Bool) -> IntSet -> (IntSet,IntSet) partition predicate0 t0 = toPair $ go predicate0 t0   where@@ -793,7 +780,7 @@             {-# INLINE bitPred #-}  --- | /O(min(n,W))/. The expression (@'split' x set@) is a pair @(set1,set2)@+-- | \(O(\min(n,W))\). The expression (@'split' x set@) is a pair @(set1,set2)@ -- where @set1@ comprises the elements of @set@ less than @x@ and @set2@ -- comprises the elements of @set@ greater than @x@. --@@ -827,7 +814,7 @@                   higherBitmap = complement (lowerBitmap + bitmapOf x')     go _ Nil = (Nil :*: Nil) --- | /O(min(n,W))/. Performs a 'split' but also returns whether the pivot+-- | \(O(\min(n,W))\). Performs a 'split' but also returns whether the pivot -- element was found in the original set. splitMember :: Key -> IntSet -> (IntSet,Bool,IntSet) splitMember x t =@@ -865,7 +852,7 @@   Min/Max ----------------------------------------------------------------------} --- | /O(min(n,W))/. Retrieves the maximal key of the set, and the set+-- | \(O(\min(n,W))\). Retrieves the maximal key of the set, and the set -- stripped of that element, or 'Nothing' if passed an empty set. maxView :: IntSet -> Maybe (Key, IntSet) maxView t =@@ -877,7 +864,7 @@     go (Tip kx bm) = case highestBitSet bm of bi -> (kx + bi, tip kx (bm .&. complement (bitmapOfSuffix bi)))     go Nil = error "maxView Nil" --- | /O(min(n,W))/. Retrieves the minimal key of the set, and the set+-- | \(O(\min(n,W))\). Retrieves the minimal key of the set, and the set -- stripped of that element, or 'Nothing' if passed an empty set. minView :: IntSet -> Maybe (Key, IntSet) minView t =@@ -889,20 +876,20 @@     go (Tip kx bm) = case lowestBitSet bm of bi -> (kx + bi, tip kx (bm .&. complement (bitmapOfSuffix bi)))     go Nil = error "minView Nil" --- | /O(min(n,W))/. Delete and find the minimal element.+-- | \(O(\min(n,W))\). Delete and find the minimal element. -- -- > deleteFindMin set = (findMin set, deleteMin set) deleteFindMin :: IntSet -> (Key, IntSet) deleteFindMin = fromMaybe (error "deleteFindMin: empty set has no minimal element") . minView --- | /O(min(n,W))/. Delete and find the maximal element.+-- | \(O(\min(n,W))\). Delete and find the maximal element. -- -- > deleteFindMax set = (findMax set, deleteMax set) deleteFindMax :: IntSet -> (Key, IntSet) deleteFindMax = fromMaybe (error "deleteFindMax: empty set has no maximal element") . maxView  --- | /O(min(n,W))/. The minimal element of the set.+-- | \(O(\min(n,W))\). The minimal element of the set. findMin :: IntSet -> Key findMin Nil = error "findMin: empty set has no minimal element" findMin (Tip kx bm) = kx + lowestBitSet bm@@ -913,7 +900,7 @@           find (Bin _ _ l' _) = find l'           find Nil            = error "findMin Nil" --- | /O(min(n,W))/. The maximal element of a set.+-- | \(O(\min(n,W))\). The maximal element of a set. findMax :: IntSet -> Key findMax Nil = error "findMax: empty set has no maximal element" findMax (Tip kx bm) = kx + highestBitSet bm@@ -925,14 +912,14 @@           find Nil            = error "findMax Nil"  --- | /O(min(n,W))/. Delete the minimal element. Returns an empty set if the set is empty.+-- | \(O(\min(n,W))\). Delete the minimal element. Returns an empty set if the set is empty. -- -- Note that this is a change of behaviour for consistency with 'Data.Set.Set' &#8211; -- versions prior to 0.5 threw an error if the 'IntSet' was already empty. deleteMin :: IntSet -> IntSet deleteMin = maybe Nil snd . minView --- | /O(min(n,W))/. Delete the maximal element. Returns an empty set if the set is empty.+-- | \(O(\min(n,W))\). Delete the maximal element. Returns an empty set if the set is empty. -- -- Note that this is a change of behaviour for consistency with 'Data.Set.Set' &#8211; -- versions prior to 0.5 threw an error if the 'IntSet' was already empty.@@ -943,7 +930,7 @@   Map ----------------------------------------------------------------------} --- | /O(n*min(n,W))/.+-- | \(O(n \min(n,W))\). -- @'map' f s@ is the set obtained by applying @f@ to each element of @s@. -- -- It's worth noting that the size of the result may be smaller if,@@ -952,7 +939,7 @@ map :: (Key -> Key) -> IntSet -> IntSet map f = fromList . List.map f . toList --- | /O(n)/. The+-- | \(O(n)\). The -- -- @'mapMonotonic' f s == 'map' f s@, but works only when @f@ is strictly increasing. -- /The precondition is not checked./@@ -972,7 +959,7 @@ {--------------------------------------------------------------------   Fold --------------------------------------------------------------------}--- | /O(n)/. Fold the elements in the set using the given right-associative+-- | \(O(n)\). Fold the elements in the set using the given right-associative -- binary operator. This function is an equivalent of 'foldr' and is present -- for compatibility only. --@@ -981,7 +968,7 @@ fold = foldr {-# INLINE fold #-} --- | /O(n)/. Fold the elements in the set using the given right-associative+-- | \(O(n)\). Fold the elements in the set using the given right-associative -- binary operator, such that @'foldr' f z == 'Prelude.foldr' f z . 'toAscList'@. -- -- For example,@@ -998,7 +985,7 @@     go z' (Bin _ _ l r) = go (go z' r) l {-# INLINE foldr #-} --- | /O(n)/. A strict version of 'foldr'. Each application of the operator is+-- | \(O(n)\). A strict version of 'foldr'. Each application of the operator is -- evaluated before using the result in the next application. This -- function is strict in the starting value. foldr' :: (Key -> b -> b) -> b -> IntSet -> b@@ -1012,7 +999,7 @@     go z' (Bin _ _ l r) = go (go z' r) l {-# INLINE foldr' #-} --- | /O(n)/. Fold the elements in the set using the given left-associative+-- | \(O(n)\). Fold the elements in the set using the given left-associative -- binary operator, such that @'foldl' f z == 'Prelude.foldl' f z . 'toAscList'@. -- -- For example,@@ -1029,7 +1016,7 @@     go z' (Bin _ _ l r) = go (go z' l) r {-# INLINE foldl #-} --- | /O(n)/. A strict version of 'foldl'. Each application of the operator is+-- | \(O(n)\). A strict version of 'foldl'. Each application of the operator is -- evaluated before using the result in the next application. This -- function is strict in the starting value. foldl' :: (a -> Key -> a) -> a -> IntSet -> a@@ -1046,7 +1033,7 @@ {--------------------------------------------------------------------   List variations --------------------------------------------------------------------}--- | /O(n)/. An alias of 'toAscList'. The elements of a set in ascending order.+-- | \(O(n)\). An alias of 'toAscList'. The elements of a set in ascending order. -- Subject to list fusion. elems :: IntSet -> [Key] elems@@ -1055,7 +1042,8 @@ {--------------------------------------------------------------------   Lists --------------------------------------------------------------------}-#if __GLASGOW_HASKELL__ >= 708++#ifdef __GLASGOW_HASKELL__ -- | @since 0.5.6.2 instance GHC.Exts.IsList IntSet where   type Item IntSet = Key@@ -1063,17 +1051,17 @@   toList   = toList #endif --- | /O(n)/. Convert the set to a list of elements. Subject to list fusion.+-- | \(O(n)\). Convert the set to a list of elements. Subject to list fusion. toList :: IntSet -> [Key] toList   = toAscList --- | /O(n)/. Convert the set to an ascending list of elements. Subject to list+-- | \(O(n)\). Convert the set to an ascending list of elements. Subject to list -- fusion. toAscList :: IntSet -> [Key] toAscList = foldr (:) [] --- | /O(n)/. Convert the set to a descending list of elements. Subject to list+-- | \(O(n)\). Convert the set to a descending list of elements. Subject to list -- fusion. toDescList :: IntSet -> [Key] toDescList = foldl (flip (:)) []@@ -1108,26 +1096,26 @@ #endif  --- | /O(n*min(n,W))/. Create a set from a list of integers.+-- | \(O(n \min(n,W))\). Create a set from a list of integers. fromList :: [Key] -> IntSet fromList xs   = Foldable.foldl' ins empty xs   where     ins t x  = insert x t --- | /O(n)/. Build a set from an ascending list of elements.+-- | \(O(n)\). Build a set from an ascending list of elements. -- /The precondition (input list is ascending) is not checked./ fromAscList :: [Key] -> IntSet fromAscList = fromMonoList {-# NOINLINE fromAscList #-} --- | /O(n)/. Build a set from an ascending list of distinct elements.+-- | \(O(n)\). Build a set from an ascending list of distinct elements. -- /The precondition (input list is strictly ascending) is not checked./ fromDistinctAscList :: [Key] -> IntSet fromDistinctAscList = fromAscList {-# INLINE fromDistinctAscList #-} --- | /O(n)/. Build a set from a monotonic list of elements.+-- | \(O(n)\). Build a set from a monotonic list of elements. -- -- The precise conditions under which this function works are subtle: -- For any branch mask, keys with the same prefix w.r.t. the branch@@ -1244,12 +1232,6 @@ #endif  {---------------------------------------------------------------------  Typeable---------------------------------------------------------------------}--INSTANCE_TYPEABLE0(IntSet)--{--------------------------------------------------------------------   NFData --------------------------------------------------------------------} @@ -1261,14 +1243,14 @@ {--------------------------------------------------------------------   Debugging --------------------------------------------------------------------}--- | /O(n)/. Show the tree that implements the set. The tree is shown+-- | \(O(n)\). Show the tree that implements the set. The tree is shown -- in a compressed, hanging format. showTree :: IntSet -> String showTree s   = showTreeWith True False s  -{- | /O(n)/. The expression (@'showTreeWith' hang wide map@) shows+{- | \(O(n)\). The expression (@'showTreeWith' hang wide map@) shows  the tree that implements the set. If @hang@ is  'True', a /hanging/ tree is shown otherwise a rotated tree is shown. If  @wide@ is 'True', an extra wide version is shown.@@ -1375,11 +1357,7 @@ ----------------------------------------------------------------------}  suffixBitMask :: Int-#if MIN_VERSION_base(4,7,0) suffixBitMask = finiteBitSize (undefined::Word) - 1-#else-suffixBitMask = bitSize (undefined::Word) - 1-#endif {-# INLINE suffixBitMask #-}  prefixBitMask :: Int@@ -1474,7 +1452,7 @@ #if defined(__GLASGOW_HASKELL__) && (WORD_SIZE_IN_BITS==32 || WORD_SIZE_IN_BITS==64) indexOfTheOnlyBit :: Nat -> Int {-# INLINE indexOfTheOnlyBit #-}-#if MIN_VERSION_base(4,8,0) && (WORD_SIZE_IN_BITS==64)+#if WORD_SIZE_IN_BITS==64 indexOfTheOnlyBit bitmask = countTrailingZeros bitmask  lowestBitSet x = countTrailingZeros x@@ -1625,7 +1603,7 @@   Utilities --------------------------------------------------------------------} --- | /O(1)/.  Decompose a set into pieces based on the structure of the underlying+-- | \(O(1)\).  Decompose a set into pieces based on the structure of the underlying -- tree.  This function is useful for consuming a set in parallel. -- -- No guarantee is made as to the sizes of the pieces; an internal, but

@@ -1,17 +1,14 @@ {-# LANGUAGE CPP #-} {-# LANGUAGE BangPatterns #-} {-# LANGUAGE PatternGuards #-}-#if __GLASGOW_HASKELL__-{-# LANGUAGE DeriveDataTypeable, StandaloneDeriving #-}-#endif #if defined(__GLASGOW_HASKELL__)-{-# LANGUAGE Trustworthy #-}-#endif-#if __GLASGOW_HASKELL__ >= 708+{-# LANGUAGE DeriveLift #-} {-# LANGUAGE RoleAnnotations #-}+{-# LANGUAGE StandaloneDeriving #-}+{-# LANGUAGE Trustworthy #-} {-# LANGUAGE TypeFamilies #-}-#define USE_MAGIC_PROXY 1 #endif+#define USE_MAGIC_PROXY 1  #ifdef USE_MAGIC_PROXY {-# LANGUAGE MagicHash #-}@@ -267,7 +264,9 @@     , keys     , assocs     , keysSet+    , argSet     , fromSet+    , fromArgSet      -- ** Lists     , toList@@ -344,7 +343,7 @@     -- Used by the strict version     , AreWeStrict (..)     , atKeyImpl-#if __GLASGOW_HASKELL__ && MIN_VERSION_base(4,8,0)+#ifdef __GLASGOW_HASKELL__     , atKeyPlain #endif     , bin@@ -369,35 +368,21 @@     , mapGentlyWhenMatched     ) where -#if MIN_VERSION_base(4,8,0) import Data.Functor.Identity (Identity (..)) import Control.Applicative (liftA3)-#else-import Control.Applicative (Applicative(..), (<$>), liftA3)-import Data.Monoid (Monoid(..))-import Data.Traversable (Traversable(traverse))-#endif-#if MIN_VERSION_base(4,9,0) import Data.Functor.Classes import Data.Semigroup (stimesIdempotentMonoid)-#endif-#if MIN_VERSION_base(4,9,0)-import Data.Semigroup (Semigroup(stimes))-#endif-#if !(MIN_VERSION_base(4,11,0)) && MIN_VERSION_base(4,9,0)+import Data.Semigroup (Arg(..), Semigroup(stimes))+#if !(MIN_VERSION_base(4,11,0)) import Data.Semigroup (Semigroup((<>))) #endif import Control.Applicative (Const (..)) import Control.DeepSeq (NFData(rnf)) import Data.Bits (shiftL, shiftR) import qualified Data.Foldable as Foldable-#if !MIN_VERSION_base(4,8,0)-import Data.Foldable (Foldable())-#endif #if MIN_VERSION_base(4,10,0) import Data.Bifoldable #endif-import Data.Typeable import Prelude hiding (lookup, map, filter, foldr, foldl, null, splitAt, take, drop)  import qualified Data.Set.Internal as Set@@ -412,20 +397,14 @@  #if __GLASGOW_HASKELL__ import GHC.Exts (build, lazy)-#if !MIN_VERSION_base(4,8,0)-import Data.Functor ((<$))-#endif-#ifdef USE_MAGIC_PROXY+import Language.Haskell.TH.Syntax (Lift)+#  ifdef USE_MAGIC_PROXY import GHC.Exts (Proxy#, proxy# )-#endif-#if __GLASGOW_HASKELL__ >= 708+#  endif import qualified GHC.Exts as GHCExts-#endif import Text.Read hiding (lift) import Data.Data import qualified Control.Category as Category-#endif-#if __GLASGOW_HASKELL__ >= 708 import Data.Coerce #endif @@ -435,7 +414,7 @@ --------------------------------------------------------------------} infixl 9 !,!?,\\ -- --- | /O(log n)/. Find the value at a key.+-- | \(O(\log n)\). Find the value at a key. -- Calls 'error' when the element can not be found. -- -- > fromList [(5,'a'), (3,'b')] ! 1    Error: element not in the map@@ -447,7 +426,7 @@ {-# INLINE (!) #-} #endif --- | /O(log n)/. Find the value at a key.+-- | \(O(\log n)\). Find the value at a key. -- Returns 'Nothing' when the element can not be found. -- -- prop> fromList [(5, 'a'), (3, 'b')] !? 1 == Nothing@@ -484,22 +463,23 @@  type Size     = Int -#if __GLASGOW_HASKELL__ >= 708+#ifdef __GLASGOW_HASKELL__ type role Map nominal representational #endif +#ifdef __GLASGOW_HASKELL__+-- | @since FIXME+deriving instance (Lift k, Lift a) => Lift (Map k a)+#endif+ instance (Ord k) => Monoid (Map k v) where     mempty  = empty     mconcat = unions-#if !(MIN_VERSION_base(4,9,0))-    mappend = union-#else     mappend = (<>)  instance (Ord k) => Semigroup (Map k v) where     (<>)    = union     stimes  = stimesIdempotentMonoid-#endif  #if __GLASGOW_HASKELL__ @@ -530,7 +510,7 @@ {--------------------------------------------------------------------   Query --------------------------------------------------------------------}--- | /O(1)/. Is the map empty?+-- | \(O(1)\). Is the map empty? -- -- > Data.Map.null (empty)           == True -- > Data.Map.null (singleton 1 'a') == False@@ -540,7 +520,7 @@ null (Bin {}) = False {-# INLINE null #-} --- | /O(1)/. The number of elements in the map.+-- | \(O(1)\). The number of elements in the map. -- -- > size empty                                   == 0 -- > size (singleton 1 'a')                       == 1@@ -552,7 +532,7 @@ {-# INLINE size #-}  --- | /O(log n)/. Lookup the value at a key in the map.+-- | \(O(\log n)\). Lookup the value at a key in the map. -- -- The function will return the corresponding value as @('Just' value)@, -- or 'Nothing' if the key isn't in the map.@@ -594,7 +574,7 @@ {-# INLINE lookup #-} #endif --- | /O(log n)/. Is the key a member of the map? See also 'notMember'.+-- | \(O(\log n)\). Is the key a member of the map? See also 'notMember'. -- -- > member 5 (fromList [(5,'a'), (3,'b')]) == True -- > member 1 (fromList [(5,'a'), (3,'b')]) == False@@ -612,7 +592,7 @@ {-# INLINE member #-} #endif --- | /O(log n)/. Is the key not a member of the map? See also 'member'.+-- | \(O(\log n)\). Is the key not a member of the map? See also 'member'. -- -- > notMember 5 (fromList [(5,'a'), (3,'b')]) == False -- > notMember 1 (fromList [(5,'a'), (3,'b')]) == True@@ -625,7 +605,7 @@ {-# INLINE notMember #-} #endif --- | /O(log n)/. Find the value at a key.+-- | \(O(\log n)\). Find the value at a key. -- Calls 'error' when the element can not be found. find :: Ord k => k -> Map k a -> a find = go@@ -641,7 +621,7 @@ {-# INLINE find #-} #endif --- | /O(log n)/. The expression @('findWithDefault' def k map)@ returns+-- | \(O(\log n)\). The expression @('findWithDefault' def k map)@ returns -- the value at key @k@ or returns default value @def@ -- when the key is not in the map. --@@ -661,7 +641,7 @@ {-# INLINE findWithDefault #-} #endif --- | /O(log n)/. Find largest key smaller than the given one and return the+-- | \(O(\log n)\). Find largest key smaller than the given one and return the -- corresponding (key, value) pair. -- -- > lookupLT 3 (fromList [(3,'a'), (5,'b')]) == Nothing@@ -682,7 +662,7 @@ {-# INLINE lookupLT #-} #endif --- | /O(log n)/. Find smallest key greater than the given one and return the+-- | \(O(\log n)\). Find smallest key greater than the given one and return the -- corresponding (key, value) pair. -- -- > lookupGT 4 (fromList [(3,'a'), (5,'b')]) == Just (5, 'b')@@ -703,7 +683,7 @@ {-# INLINE lookupGT #-} #endif --- | /O(log n)/. Find largest key smaller or equal to the given one and return+-- | \(O(\log n)\). Find largest key smaller or equal to the given one and return -- the corresponding (key, value) pair. -- -- > lookupLE 2 (fromList [(3,'a'), (5,'b')]) == Nothing@@ -727,7 +707,7 @@ {-# INLINE lookupLE #-} #endif --- | /O(log n)/. Find smallest key greater or equal to the given one and return+-- | \(O(\log n)\). Find smallest key greater or equal to the given one and return -- the corresponding (key, value) pair. -- -- > lookupGE 3 (fromList [(3,'a'), (5,'b')]) == Just (3, 'a')@@ -754,7 +734,7 @@ {--------------------------------------------------------------------   Construction --------------------------------------------------------------------}--- | /O(1)/. The empty map.+-- | \(O(1)\). The empty map. -- -- > empty      == fromList [] -- > size empty == 0@@ -763,7 +743,7 @@ empty = Tip {-# INLINE empty #-} --- | /O(1)/. A map with a single element.+-- | \(O(1)\). A map with a single element. -- -- > singleton 1 'a'        == fromList [(1, 'a')] -- > size (singleton 1 'a') == 1@@ -775,7 +755,7 @@ {--------------------------------------------------------------------   Insertion --------------------------------------------------------------------}--- | /O(log n)/. Insert a new key and value in the map.+-- | \(O(\log n)\). Insert a new key and value in the map. -- If the key is already present in the map, the associated value is -- replaced with the supplied value. 'insert' is equivalent to -- @'insertWith' 'const'@.@@ -855,7 +835,7 @@ {-# INLINE insertR #-} #endif --- | /O(log n)/. Insert with a function, combining new value and old value.+-- | \(O(\log n)\). Insert with a function, combining new value and old value. -- @'insertWith' f key value mp@ -- will insert the pair (key, value) into @mp@ if key does -- not exist in the map. If the key does exist, the function will@@ -907,7 +887,7 @@ {-# INLINE insertWithR #-} #endif --- | /O(log n)/. Insert with a function, combining key, new value and old value.+-- | \(O(\log n)\). Insert with a function, combining key, new value and old value. -- @'insertWithKey' f key value mp@ -- will insert the pair (key, value) into @mp@ if key does -- not exist in the map. If the key does exist, the function will@@ -956,7 +936,7 @@ {-# INLINE insertWithKeyR #-} #endif --- | /O(log n)/. Combines insert operation with old value retrieval.+-- | \(O(\log n)\). Combines insert operation with old value retrieval. -- The expression (@'insertLookupWithKey' f k x map@) -- is a pair where the first element is equal to (@'lookup' k map@) -- and the second element equal to (@'insertWithKey' f k x map@).@@ -997,7 +977,7 @@ {--------------------------------------------------------------------   Deletion --------------------------------------------------------------------}--- | /O(log n)/. Delete a key and its value from the map. When the key is not+-- | \(O(\log n)\). Delete a key and its value from the map. When the key is not -- a member of the map, the original map is returned. -- -- > delete 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"@@ -1025,7 +1005,7 @@ {-# INLINE delete #-} #endif --- | /O(log n)/. Update a value at a specific key with the result of the provided function.+-- | \(O(\log n)\). Update a value at a specific key with the result of the provided function. -- When the key is not -- a member of the map, the original map is returned. --@@ -1041,7 +1021,7 @@ {-# INLINE adjust #-} #endif --- | /O(log n)/. Adjust a value at a specific key. When the key is not+-- | \(O(\log n)\). Adjust a value at a specific key. When the key is not -- a member of the map, the original map is returned. -- -- > let f key x = (show key) ++ ":new " ++ x@@ -1065,7 +1045,7 @@ {-# INLINE adjustWithKey #-} #endif --- | /O(log n)/. The expression (@'update' f k map@) updates the value @x@+-- | \(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@. --@@ -1082,7 +1062,7 @@ {-# INLINE update #-} #endif --- | /O(log n)/. The expression (@'updateWithKey' f k map@) updates the+-- | \(O(\log n)\). The expression (@'updateWithKey' f k map@) updates the -- value @x@ at @k@ (if it is in the map). If (@f k x@) is 'Nothing', -- the element is deleted. If it is (@'Just' y@), the key @k@ is bound -- to the new value @y@.@@ -1111,7 +1091,7 @@ {-# INLINE updateWithKey #-} #endif --- | /O(log n)/. Lookup and update. See also 'updateWithKey'.+-- | \(O(\log n)\). Lookup and update. See also 'updateWithKey'. -- The function returns changed value, if it is updated. -- Returns the original key value if the map entry is deleted. --@@ -1144,7 +1124,7 @@ {-# INLINE updateLookupWithKey #-} #endif --- | /O(log n)/. The expression (@'alter' f k map@) alters the value @x@ at @k@, or absence thereof.+-- | \(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 : @'lookup' k ('alter' f k m) = f ('lookup' k m)@. --@@ -1182,7 +1162,7 @@ -- Used to choose the appropriate alterF implementation. data AreWeStrict = Strict | Lazy --- | /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 inspect, insert, delete, -- or update a value in a 'Map'.  In short: @'lookup' k \<$\> 'alterF' f k m = f -- ('lookup' k m)@.@@ -1238,14 +1218,12 @@ "alterF/Const" forall k (f :: Maybe a -> Const b (Maybe a)) . alterF f k = \m -> Const . getConst . f $ lookup k m  #-} -#if MIN_VERSION_base(4,8,0) -- base 4.8 and above include Data.Functor.Identity, so we can -- save a pretty decent amount of time by handling it specially. {-# RULES "alterF/Identity" forall k f . alterF f k = atKeyIdentity k f  #-} #endif-#endif  atKeyImpl :: (Functor f, Ord k) =>       AreWeStrict -> k -> (Maybe a -> f (Maybe a)) -> Map k a -> f (Map k a)@@ -1299,10 +1277,7 @@       GT -> (go $! q `snocQB` True) k r       EQ -> TraceResult (Just x) (buildQ q) --- GHC 7.8 doesn't manage to unbox the queue properly--- unless we explicitly inline this function. This stuff--- is a bit touchy, unfortunately.-#if __GLASGOW_HASKELL__ >= 710+#ifdef __GLASGOW_HASKELL__ {-# INLINABLE lookupTrace #-} #else {-# INLINE lookupTrace #-}@@ -1372,7 +1347,7 @@         Just (True,tl) -> Bin sz ky y l (replaceAlong tl x r)         Nothing -> Bin sz ky x l r -#if __GLASGOW_HASKELL__ && MIN_VERSION_base(4,8,0)+#ifdef __GLASGOW_HASKELL__ atKeyIdentity :: Ord k => k -> (Maybe a -> Identity (Maybe a)) -> Map k a -> Identity (Map k a) atKeyIdentity k f t = Identity $ atKeyPlain Lazy k (coerce f) t {-# INLINABLE atKeyIdentity #-}@@ -1447,7 +1422,7 @@ {--------------------------------------------------------------------   Indexing --------------------------------------------------------------------}--- | /O(log n)/. Return the /index/ of a key, which is its zero-based index in+-- | \(O(\log n)\). Return the /index/ of a key, which is its zero-based index in -- the sequence sorted by keys. The index is a number from /0/ up to, but not -- including, the 'size' of the map. Calls 'error' when the key is not -- a 'member' of the map.@@ -1471,7 +1446,7 @@ {-# INLINABLE findIndex #-} #endif --- | /O(log n)/. Lookup the /index/ of a key, which is its zero-based index in+-- | \(O(\log n)\). Lookup the /index/ of a key, which is its zero-based index in -- the sequence sorted by keys. The index is a number from /0/ up to, but not -- including, the 'size' of the map. --@@ -1494,7 +1469,7 @@ {-# INLINABLE lookupIndex #-} #endif --- | /O(log n)/. Retrieve an element by its /index/, i.e. by its zero-based+-- | \(O(\log n)\). Retrieve an element by its /index/, i.e. by its zero-based -- index in the sequence sorted by keys. If the /index/ is out of range (less -- than zero, greater or equal to 'size' of the map), 'error' is called. --@@ -1555,7 +1530,7 @@         EQ -> insertMin kx x r       where sizeL = size l --- | /O(log n)/. Split a map at a particular index.+-- | \(O(\log n)\). Split a map at a particular index. -- -- @ -- splitAt !n !xs = ('take' n xs, 'drop' n xs)@@ -1578,7 +1553,7 @@           EQ -> l :*: insertMin kx x r       where sizeL = size l --- | /O(log n)/. Update the element at /index/, i.e. by its zero-based index in+-- | \(O(\log n)\). Update the element at /index/, i.e. by its zero-based index in -- the sequence sorted by keys. If the /index/ is out of range (less than zero, -- greater or equal to 'size' of the map), 'error' is called. --@@ -1604,7 +1579,7 @@       where         sizeL = size l --- | /O(log n)/. Delete the element at /index/, i.e. by its zero-based index in+-- | \(O(\log n)\). Delete the element at /index/, i.e. by its zero-based index in -- the sequence sorted by keys. If the /index/ is out of range (less than zero, -- greater or equal to 'size' of the map), 'error' is called. --@@ -1633,7 +1608,7 @@ lookupMinSure k a Tip = (k, a) lookupMinSure _ _ (Bin _ k a l _) = lookupMinSure k a l --- | /O(log n)/. The minimal key of the map. Returns 'Nothing' if the map is empty.+-- | \(O(\log n)\). The minimal key of the map. Returns 'Nothing' if the map is empty. -- -- > lookupMin (fromList [(5,"a"), (3,"b")]) == Just (3,"b") -- > lookupMin empty = Nothing@@ -1644,7 +1619,7 @@ lookupMin Tip = Nothing lookupMin (Bin _ k x l _) = Just $! lookupMinSure k x l --- | /O(log n)/. The minimal key of the map. Calls 'error' if the map is empty.+-- | \(O(\log n)\). The minimal key of the map. Calls 'error' if the map is empty. -- -- > findMin (fromList [(5,"a"), (3,"b")]) == (3,"b") -- > findMin empty                            Error: empty map has no minimal element@@ -1654,7 +1629,7 @@   | Just r <- lookupMin t = r   | otherwise = error "Map.findMin: empty map has no minimal element" --- | /O(log n)/. The maximal key of the map. Calls 'error' if the map is empty.+-- | \(O(\log n)\). The maximal key of the map. Calls 'error' if the map is empty. -- -- > findMax (fromList [(5,"a"), (3,"b")]) == (5,"a") -- > findMax empty                            Error: empty map has no maximal element@@ -1663,7 +1638,7 @@ lookupMaxSure k a Tip = (k, a) lookupMaxSure _ _ (Bin _ k a _ r) = lookupMaxSure k a r --- | /O(log n)/. The maximal key of the map. Returns 'Nothing' if the map is empty.+-- | \(O(\log n)\). The maximal key of the map. Returns 'Nothing' if the map is empty. -- -- > lookupMax (fromList [(5,"a"), (3,"b")]) == Just (5,"a") -- > lookupMax empty = Nothing@@ -1679,7 +1654,7 @@   | Just r <- lookupMax t = r   | otherwise = error "Map.findMax: empty map has no maximal element" --- | /O(log n)/. Delete the minimal key. Returns an empty map if the map is empty.+-- | \(O(\log n)\). Delete the minimal key. Returns an empty map if the map is empty. -- -- > deleteMin (fromList [(5,"a"), (3,"b"), (7,"c")]) == fromList [(5,"a"), (7,"c")] -- > deleteMin empty == empty@@ -1689,7 +1664,7 @@ deleteMin (Bin _ kx x l r)    = balanceR kx x (deleteMin l) r deleteMin Tip                 = Tip --- | /O(log n)/. Delete the maximal key. Returns an empty map if the map is empty.+-- | \(O(\log n)\). Delete the maximal key. Returns an empty map if the map is empty. -- -- > deleteMax (fromList [(5,"a"), (3,"b"), (7,"c")]) == fromList [(3,"b"), (5,"a")] -- > deleteMax empty == empty@@ -1699,7 +1674,7 @@ deleteMax (Bin _ kx x l r)    = balanceL kx x l (deleteMax r) deleteMax Tip                 = Tip --- | /O(log n)/. Update the value at the minimal key.+-- | \(O(\log n)\). Update the value at the minimal key. -- -- > updateMin (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "Xb"), (5, "a")] -- > updateMin (\ _ -> Nothing)         (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"@@ -1708,7 +1683,7 @@ updateMin f m   = updateMinWithKey (\_ x -> f x) m --- | /O(log n)/. Update the value at the maximal key.+-- | \(O(\log n)\). Update the value at the maximal key. -- -- > updateMax (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "Xa")] -- > updateMax (\ _ -> Nothing)         (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"@@ -1718,7 +1693,7 @@   = updateMaxWithKey (\_ x -> f x) m  --- | /O(log n)/. Update the value at the minimal key.+-- | \(O(\log n)\). Update the value at the minimal key. -- -- > updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"3:b"), (5,"a")] -- > updateMinWithKey (\ _ _ -> Nothing)                     (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"@@ -1730,7 +1705,7 @@                                            Just x' -> Bin sx kx x' Tip r updateMinWithKey f (Bin _ kx x l r)    = balanceR kx x (updateMinWithKey f l) r --- | /O(log n)/. Update the value at the maximal key.+-- | \(O(\log n)\). Update the value at the maximal key. -- -- > updateMaxWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"b"), (5,"5:a")] -- > updateMaxWithKey (\ _ _ -> Nothing)                     (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"@@ -1742,7 +1717,7 @@                                            Just x' -> Bin sx kx x' l Tip updateMaxWithKey f (Bin _ kx x l r)    = balanceL kx x l (updateMaxWithKey f r) --- | /O(log n)/. Retrieves the minimal (key,value) pair of the map, and+-- | \(O(\log n)\). Retrieves the minimal (key,value) pair of the map, and -- the map stripped of that element, or 'Nothing' if passed an empty map. -- -- > minViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((3,"b"), singleton 5 "a")@@ -1758,7 +1733,7 @@ -- the Just. {-# INLINE minViewWithKey #-} --- | /O(log n)/. Retrieves the maximal (key,value) pair of the map, and+-- | \(O(\log n)\). Retrieves the maximal (key,value) pair of the map, and -- the map stripped of that element, or 'Nothing' if passed an empty map. -- -- > maxViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((5,"a"), singleton 3 "b")@@ -1772,7 +1747,7 @@ -- See note on inlining at minViewWithKey {-# INLINE maxViewWithKey #-} --- | /O(log n)/. Retrieves the value associated with minimal key of the+-- | \(O(\log n)\). Retrieves the value associated with minimal key of the -- map, and the map stripped of that element, or 'Nothing' if passed an -- empty map. --@@ -1784,7 +1759,7 @@               Nothing -> Nothing               Just ~((_, x), t') -> Just (x, t') --- | /O(log n)/. Retrieves the value associated with maximal key of the+-- | \(O(\log n)\). Retrieves the value associated with maximal key of the -- map, and the map stripped of that element, or 'Nothing' if passed an -- empty map. --@@ -1827,7 +1802,7 @@ {-# INLINABLE unionsWith #-} #endif --- | /O(m*log(n\/m + 1)), m <= n/.+-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\). -- The expression (@'union' t1 t2@) takes the left-biased union of @t1@ and @t2@. -- It prefers @t1@ when duplicate keys are encountered, -- i.e. (@'union' == 'unionWith' 'const'@).@@ -1851,7 +1826,7 @@ {--------------------------------------------------------------------   Union with a combining function --------------------------------------------------------------------}--- | /O(m*log(n\/m + 1)), m <= n/. Union with a combining function.+-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\). Union with a combining function. -- -- > unionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")] @@ -1871,7 +1846,7 @@ {-# INLINABLE unionWith #-} #endif --- | /O(m*log(n\/m + 1)), m <= n/.+-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\). -- Union with a combining function. -- -- > let f key left_value right_value = (show key) ++ ":" ++ left_value ++ "|" ++ right_value@@ -1902,7 +1877,7 @@ -- relies on doing it the way we do, and it's not clear whether that -- bound holds the other way. --- | /O(m*log(n\/m + 1)), m <= n/. Difference of two maps.+-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\). Difference of two maps. -- Return elements of the first map not existing in the second map. -- -- > difference (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 3 "b"@@ -1921,7 +1896,7 @@ {-# INLINABLE difference #-} #endif --- | /O(m*log(n\/m + 1)), m <= n/. Remove all keys in a 'Set' from a 'Map'.+-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\). Remove all keys in a 'Set' from a 'Map'. -- -- @ -- m \`withoutKeys\` s = 'filterWithKey' (\k _ -> k ``Set.notMember`` s) m@@ -1944,7 +1919,7 @@ {-# INLINABLE withoutKeys #-} #endif --- | /O(n+m)/. Difference with a combining function.+-- | \(O(n+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@@ -1960,7 +1935,7 @@ {-# INLINABLE differenceWith #-} #endif --- | /O(n+m)/. Difference with a combining function. When two equal keys are+-- | \(O(n+m)\). Difference with a combining function. When two equal keys are -- encountered, the combining function is applied to the key and both values. -- 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@.@@ -1980,7 +1955,7 @@ {--------------------------------------------------------------------   Intersection --------------------------------------------------------------------}--- | /O(m*log(n\/m + 1)), m <= n/. Intersection of two maps.+-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\). Intersection of two maps. -- Return data in the first map for the keys existing in both maps. -- (@'intersection' m1 m2 == 'intersectionWith' 'const' m1 m2@). --@@ -2002,7 +1977,7 @@ {-# INLINABLE intersection #-} #endif --- | /O(m*log(n\/m + 1)), m <= n/. Restrict a 'Map' to only those keys+-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\). Restrict a 'Map' to only those keys -- found in a 'Set'. -- -- @@@ -2027,7 +2002,7 @@ {-# INLINABLE restrictKeys #-} #endif --- | /O(m*log(n\/m + 1)), m <= n/. Intersection with a combining function.+-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\). Intersection with a combining function. -- -- > intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "aA" @@ -2047,7 +2022,7 @@ {-# INLINABLE intersectionWith #-} #endif --- | /O(m*log(n\/m + 1)), m <= n/. Intersection with a combining function.+-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\). Intersection with a combining function. -- -- > let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ ar -- > intersectionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "5:a|A"@@ -2069,7 +2044,7 @@ {--------------------------------------------------------------------   Disjoint --------------------------------------------------------------------}--- | /O(m*log(n\/m + 1)), m <= n/. Check whether the key sets of two+-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\). Check whether the key sets of two -- maps are disjoint (i.e., their 'intersection' is empty). -- -- > disjoint (fromList [(2,'a')]) (fromList [(1,()), (3,())])   == True@@ -2118,24 +2093,6 @@   | null bc = empty   | otherwise = mapMaybe (bc !?) ab -#if !MIN_VERSION_base (4,8,0)--- | The identity type.-newtype Identity a = Identity { runIdentity :: a }-#if __GLASGOW_HASKELL__ == 708-instance Functor Identity where-  fmap = coerce-instance Applicative Identity where-  (<*>) = coerce-  pure = Identity-#else-instance Functor Identity where-  fmap f (Identity a) = Identity (f a)-instance Applicative Identity where-  Identity f <*> Identity x = Identity (f x)-  pure = Identity-#endif-#endif- -- | A tactic for dealing with keys present in one map but not the other in -- 'merge' or 'mergeA'. --@@ -2182,9 +2139,6 @@ -- -- @since 0.5.9 instance (Applicative f, Monad f) => Monad (WhenMissing f k x) where-#if !MIN_VERSION_base(4,8,0)-  return = pure-#endif   m >>= f = traverseMaybeMissing $ \k x -> do          res1 <- missingKey m k x          case res1 of@@ -2320,9 +2274,6 @@ -- -- @since 0.5.9 instance (Monad f, Applicative f) => Monad (WhenMatched f k x y) where-#if !MIN_VERSION_base(4,8,0)-  return = pure-#endif   m >>= f = zipWithMaybeAMatched $ \k x y -> do     res <- runWhenMatched m k x y     case res of@@ -2734,7 +2685,7 @@   MergeWithKey --------------------------------------------------------------------} --- | /O(n+m)/. An unsafe general combining function.+-- | \(O(n+m)\). An unsafe general combining function. -- -- WARNING: This function can produce corrupt maps and its results -- may depend on the internal structures of its inputs. Users should@@ -2794,7 +2745,7 @@ {--------------------------------------------------------------------   Submap --------------------------------------------------------------------}--- | /O(m*log(n\/m + 1)), m <= n/.+-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\). -- This function is defined as (@'isSubmapOf' = 'isSubmapOfBy' (==)@). -- isSubmapOf :: (Ord k,Eq a) => Map k a -> Map k a -> Bool@@ -2803,7 +2754,7 @@ {-# INLINABLE isSubmapOf #-} #endif -{- | /O(m*log(n\/m + 1)), m <= n/.+{- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\).  The expression (@'isSubmapOfBy' f t1 t2@) returns 'True' if  all keys in @t1@ are in tree @t2@, and when @f@ returns 'True' when  applied to their respective values. For example, the following@@ -2852,7 +2803,7 @@ {-# INLINABLE submap' #-} #endif --- | /O(m*log(n\/m + 1)), m <= n/. Is this a proper submap? (ie. a submap but not equal).+-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\). Is this a proper submap? (ie. a submap but not equal). -- Defined as (@'isProperSubmapOf' = 'isProperSubmapOfBy' (==)@). isProperSubmapOf :: (Ord k,Eq a) => Map k a -> Map k a -> Bool isProperSubmapOf m1 m2@@ -2861,7 +2812,7 @@ {-# INLINABLE isProperSubmapOf #-} #endif -{- | /O(m*log(n\/m + 1)), m <= n/. Is this a proper submap? (ie. a submap but not equal).+{- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\). Is this a proper submap? (ie. a submap but not equal).  The expression (@'isProperSubmapOfBy' f m1 m2@) returns 'True' when  @keys m1@ and @keys m2@ are not equal,  all keys in @m1@ are in @m2@, and when @f@ returns 'True' when@@ -2889,7 +2840,7 @@ {--------------------------------------------------------------------   Filter and partition --------------------------------------------------------------------}--- | /O(n)/. Filter all values that satisfy the predicate.+-- | \(O(n)\). Filter all values that satisfy the predicate. -- -- > filter (> "a") (fromList [(5,"a"), (3,"b")]) == singleton 3 "b" -- > filter (> "x") (fromList [(5,"a"), (3,"b")]) == empty@@ -2899,7 +2850,7 @@ filter p m   = filterWithKey (\_ x -> p x) m --- | /O(n)/. Filter all keys\/values that satisfy the predicate.+-- | \(O(n)\). Filter all keys\/values that satisfy the predicate. -- -- > filterWithKey (\k _ -> k > 4) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a" @@ -2913,7 +2864,7 @@   where !pl = filterWithKey p l         !pr = filterWithKey p r --- | /O(n)/. Filter keys and values using an 'Applicative'+-- | \(O(n)\). Filter keys and values using an 'Applicative' -- predicate. filterWithKeyA :: Applicative f => (k -> a -> f Bool) -> Map k a -> f (Map k a) filterWithKeyA _ Tip = pure Tip@@ -2925,7 +2876,7 @@       | otherwise = link kx x pl pr     combine False pl pr = link2 pl pr --- | /O(log n)/. Take while a predicate on the keys holds.+-- | \(O(\log n)\). Take while a predicate on the keys holds. -- The user is responsible for ensuring that for all keys @j@ and @k@ in the map, -- @j \< k ==\> p j \>= p k@. See note at 'spanAntitone'. --@@ -2942,7 +2893,7 @@   | p kx = link kx x l (takeWhileAntitone p r)   | otherwise = takeWhileAntitone p l --- | /O(log n)/. Drop while a predicate on the keys holds.+-- | \(O(\log n)\). Drop while a predicate on the keys holds. -- The user is responsible for ensuring that for all keys @j@ and @k@ in the map, -- @j \< k ==\> p j \>= p k@. See note at 'spanAntitone'. --@@ -2959,7 +2910,7 @@   | p kx = dropWhileAntitone p r   | otherwise = link kx x (dropWhileAntitone p l) r --- | /O(log n)/. Divide a map at the point where a predicate on the keys stops holding.+-- | \(O(\log n)\). Divide a map at the point where a predicate on the keys stops holding. -- The user is responsible for ensuring that for all keys @j@ and @k@ in the map, -- @j \< k ==\> p j \>= p k@. --@@ -2983,7 +2934,7 @@       | p kx = let u :*: v = go p r in link kx x l u :*: v       | otherwise = let u :*: v = go p l in u :*: link kx x v r --- | /O(n)/. Partition the map according to a predicate. The first+-- | \(O(n)\). Partition the map according to a predicate. The first -- map contains all elements that satisfy the predicate, the second all -- elements that fail the predicate. See also 'split'. --@@ -2995,7 +2946,7 @@ partition p m   = partitionWithKey (\_ x -> p x) m --- | /O(n)/. Partition the map according to a predicate. The first+-- | \(O(n)\). Partition the map according to a predicate. The first -- map contains all elements that satisfy the predicate, the second all -- elements that fail the predicate. See also 'split'. --@@ -3019,7 +2970,7 @@         (l1 :*: l2) = go p l         (r1 :*: r2) = go p r --- | /O(n)/. Map values and collect the 'Just' results.+-- | \(O(n)\). Map values and collect the 'Just' results. -- -- > let f x = if x == "a" then Just "new a" else Nothing -- > mapMaybe f (fromList [(5,"a"), (3,"b")]) == singleton 5 "new a"@@ -3027,7 +2978,7 @@ mapMaybe :: (a -> Maybe b) -> Map k a -> Map k b mapMaybe f = mapMaybeWithKey (\_ x -> f x) --- | /O(n)/. Map keys\/values and collect the 'Just' results.+-- | \(O(n)\). Map keys\/values and collect the 'Just' results. -- -- > let f k _ = if k < 5 then Just ("key : " ++ (show k)) else Nothing -- > mapMaybeWithKey f (fromList [(5,"a"), (3,"b")]) == singleton 3 "key : 3"@@ -3038,7 +2989,7 @@   Just y  -> link kx y (mapMaybeWithKey f l) (mapMaybeWithKey f r)   Nothing -> link2 (mapMaybeWithKey f l) (mapMaybeWithKey f r) --- | /O(n)/. Traverse keys\/values and collect the 'Just' results.+-- | \(O(n)\). Traverse keys\/values and collect the 'Just' results. -- -- @since 0.5.8 traverseMaybeWithKey :: Applicative f@@ -3053,7 +3004,7 @@           Nothing -> link2 l' r'           Just x' -> link kx x' l' r' --- | /O(n)/. Map values and separate the 'Left' and 'Right' results.+-- | \(O(n)\). Map values and separate the 'Left' and 'Right' results. -- -- > let f a = if a < "c" then Left a else Right a -- > mapEither f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])@@ -3066,7 +3017,7 @@ mapEither f m   = mapEitherWithKey (\_ x -> f x) m --- | /O(n)/. Map keys\/values and separate the 'Left' and 'Right' results.+-- | \(O(n)\). Map keys\/values and separate the 'Left' and 'Right' results. -- -- > let f k a = if k < 5 then Left (k * 2) else Right (a ++ a) -- > mapEitherWithKey f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])@@ -3089,7 +3040,7 @@ {--------------------------------------------------------------------   Mapping --------------------------------------------------------------------}--- | /O(n)/. Map a function over all values in the map.+-- | \(O(n)\). Map a function over all values in the map. -- -- > map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")] @@ -3105,16 +3056,11 @@ {-# NOINLINE [1] map #-} {-# RULES "map/map" forall f g xs . map f (map g xs) = map (f . g) xs- #-}-#endif-#if __GLASGOW_HASKELL__ >= 709--- Safe coercions were introduced in 7.8, but did not work well with RULES yet.-{-# RULES "map/coerce" map coerce = coerce  #-} #endif --- | /O(n)/. Map a function over all values in the map.+-- | \(O(n)\). Map a function over all values in the map. -- -- > let f key x = (show key) ++ ":" ++ x -- > mapWithKey f (fromList [(5,"a"), (3,"b")]) == fromList [(3, "3:b"), (5, "5:a")]@@ -3135,7 +3081,7 @@  #-} #endif --- | /O(n)/.+-- | \(O(n)\). -- @'traverseWithKey' f m == 'fromList' <$> 'traverse' (\(k, v) -> (,) k <$> f k v) ('toList' m)@ -- That is, behaves exactly like a regular 'traverse' except that the traversing -- function also has access to the key associated with a value.@@ -3150,7 +3096,7 @@     go (Bin s k v l r) = liftA3 (flip (Bin s k)) (go l) (f k v) (go r) {-# INLINE traverseWithKey #-} --- | /O(n)/. The function 'mapAccum' threads an accumulating+-- | \(O(n)\). The function 'mapAccum' threads an accumulating -- argument through the map in ascending order of keys. -- -- > let f a b = (a ++ b, b ++ "X")@@ -3160,7 +3106,7 @@ mapAccum f a m   = mapAccumWithKey (\a' _ x' -> f a' x') a m --- | /O(n)/. The function 'mapAccumWithKey' threads an accumulating+-- | \(O(n)\). The function 'mapAccumWithKey' threads an accumulating -- argument through the map in ascending order of keys. -- -- > let f a k b = (a ++ " " ++ (show k) ++ "-" ++ b, b ++ "X")@@ -3170,7 +3116,7 @@ mapAccumWithKey f a t   = mapAccumL f a t --- | /O(n)/. The function 'mapAccumL' threads an accumulating+-- | \(O(n)\). The function 'mapAccumL' threads an accumulating -- argument through the map in ascending order of keys. mapAccumL :: (a -> k -> b -> (a,c)) -> a -> Map k b -> (a,Map k c) mapAccumL _ a Tip               = (a,Tip)@@ -3180,7 +3126,7 @@       (a3,r') = mapAccumL f a2 r   in (a3,Bin sx kx x' l' r') --- | /O(n)/. The function 'mapAccumRWithKey' threads an accumulating+-- | \(O(n)\). The function 'mapAccumRWithKey' threads an accumulating -- argument through the map in descending order of keys. mapAccumRWithKey :: (a -> k -> b -> (a,c)) -> a -> Map k b -> (a,Map k c) mapAccumRWithKey _ a Tip = (a,Tip)@@ -3190,7 +3136,7 @@       (a3,l') = mapAccumRWithKey f a2 l   in (a3,Bin sx kx x' l' r') --- | /O(n*log n)/.+-- | \(O(n \log 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@@ -3207,7 +3153,7 @@ {-# INLINABLE mapKeys #-} #endif --- | /O(n*log n)/.+-- | \(O(n \log n)\). -- @'mapKeysWith' c 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@@ -3225,7 +3171,7 @@ #endif  --- | /O(n)/.+-- | \(O(n)\). -- @'mapKeysMonotonic' f s == 'mapKeys' f s@, but works only when @f@ -- is strictly monotonic. -- That is, for any values @x@ and @y@, if @x@ < @y@ then @f x@ < @f y@.@@ -3252,7 +3198,7 @@   Folds --------------------------------------------------------------------} --- | /O(n)/. Fold the values in the map using the given right-associative+-- | \(O(n)\). Fold the values in the map using the given right-associative -- binary operator, such that @'foldr' f z == 'Prelude.foldr' f z . 'elems'@. -- -- For example,@@ -3268,7 +3214,7 @@     go z' (Bin _ _ x l r) = go (f x (go z' r)) l {-# INLINE foldr #-} --- | /O(n)/. A strict version of 'foldr'. Each application of the operator is+-- | \(O(n)\). A strict version of 'foldr'. Each application of the operator is -- evaluated before using the result in the next application. This -- function is strict in the starting value. foldr' :: (a -> b -> b) -> b -> Map k a -> b@@ -3278,7 +3224,7 @@     go z' (Bin _ _ x l r) = go (f x $! go z' r) l {-# INLINE foldr' #-} --- | /O(n)/. Fold the values in the map using the given left-associative+-- | \(O(n)\). Fold the values in the map using the given left-associative -- binary operator, such that @'foldl' f z == 'Prelude.foldl' f z . 'elems'@. -- -- For example,@@ -3294,7 +3240,7 @@     go z' (Bin _ _ x l r) = go (f (go z' l) x) r {-# INLINE foldl #-} --- | /O(n)/. A strict version of 'foldl'. Each application of the operator is+-- | \(O(n)\). A strict version of 'foldl'. Each application of the operator is -- evaluated before using the result in the next application. This -- function is strict in the starting value. foldl' :: (a -> b -> a) -> a -> Map k b -> a@@ -3306,7 +3252,7 @@       in go (f z'' x) r {-# INLINE foldl' #-} --- | /O(n)/. Fold the keys and values in the map using the given right-associative+-- | \(O(n)\). Fold the keys and values in the map using the given right-associative -- binary operator, such that -- @'foldrWithKey' f z == 'Prelude.foldr' ('uncurry' f) z . 'toAscList'@. --@@ -3323,7 +3269,7 @@     go z' (Bin _ kx x l r) = go (f kx x (go z' r)) l {-# INLINE foldrWithKey #-} --- | /O(n)/. A strict version of 'foldrWithKey'. Each application of the operator is+-- | \(O(n)\). A strict version of 'foldrWithKey'. Each application of the operator is -- evaluated before using the result in the next application. This -- function is strict in the starting value. foldrWithKey' :: (k -> a -> b -> b) -> b -> Map k a -> b@@ -3333,7 +3279,7 @@     go z' (Bin _ kx x l r) = go (f kx x $! go z' r) l {-# INLINE foldrWithKey' #-} --- | /O(n)/. Fold the keys and values in the map using the given left-associative+-- | \(O(n)\). Fold the keys and values in the map using the given left-associative -- binary operator, such that -- @'foldlWithKey' f z == 'Prelude.foldl' (\\z' (kx, x) -> f z' kx x) z . 'toAscList'@. --@@ -3350,7 +3296,7 @@     go z' (Bin _ kx x l r) = go (f (go z' l) kx x) r {-# INLINE foldlWithKey #-} --- | /O(n)/. A strict version of 'foldlWithKey'. Each application of the operator is+-- | \(O(n)\). A strict version of 'foldlWithKey'. Each application of the operator is -- evaluated before using the result in the next application. This -- function is strict in the starting value. foldlWithKey' :: (a -> k -> b -> a) -> a -> Map k b -> a@@ -3362,7 +3308,7 @@       in go (f z'' kx x) r {-# INLINE foldlWithKey' #-} --- | /O(n)/. Fold the keys and values in the map using the given monoid, such that+-- | \(O(n)\). Fold the keys and values in the map using the given monoid, such that -- -- @'foldMapWithKey' f = 'Prelude.fold' . 'mapWithKey' f@ --@@ -3380,7 +3326,7 @@ {--------------------------------------------------------------------   List variations --------------------------------------------------------------------}--- | /O(n)/.+-- | \(O(n)\). -- Return all elements of the map in the ascending order of their keys. -- Subject to list fusion. --@@ -3390,7 +3336,7 @@ elems :: Map k a -> [a] elems = foldr (:) [] --- | /O(n)/. Return all keys of the map in ascending order. Subject to list+-- | \(O(n)\). Return all keys of the map in ascending order. Subject to list -- fusion. -- -- > keys (fromList [(5,"a"), (3,"b")]) == [3,5]@@ -3399,7 +3345,7 @@ keys  :: Map k a -> [k] keys = foldrWithKey (\k _ ks -> k : ks) [] --- | /O(n)/. An alias for 'toAscList'. Return all key\/value pairs in the map+-- | \(O(n)\). An alias for 'toAscList'. Return all key\/value pairs in the map -- in ascending key order. Subject to list fusion. -- -- > assocs (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]@@ -3409,7 +3355,7 @@ assocs m   = toAscList m --- | /O(n)/. The set of all keys of the map.+-- | \(O(n)\). The set of all keys of the map. -- -- > keysSet (fromList [(5,"a"), (3,"b")]) == Data.Set.fromList [3,5] -- > keysSet empty == Data.Set.empty@@ -3418,7 +3364,16 @@ keysSet Tip = Set.Tip keysSet (Bin sz kx _ l r) = Set.Bin sz kx (keysSet l) (keysSet r) --- | /O(n)/. Build a map from a set of keys and a function which for each key+-- | \(O(n)\). The set of all elements of the map contained in 'Arg's.+--+-- > argSet (fromList [(5,"a"), (3,"b")]) == Data.Set.fromList [Arg 3 "b",Arg 5 "a"]+-- > argSet empty == Data.Set.empty++argSet :: Map k a -> Set.Set (Arg k a)+argSet Tip = Set.Tip+argSet (Bin sz kx x l r) = Set.Bin sz (Arg kx x) (argSet l) (argSet r)++-- | \(O(n)\). Build a map from a set of keys and a function which for each key -- computes its value. -- -- > fromSet (\k -> replicate k 'a') (Data.Set.fromList [3, 5]) == fromList [(5,"aaaaa"), (3,"aaa")]@@ -3428,10 +3383,20 @@ fromSet _ Set.Tip = Tip fromSet f (Set.Bin sz x l r) = Bin sz x (f x) (fromSet f l) (fromSet f r) +-- | /O(n)/. Build a map from a set of elements contained inside 'Arg's.+--+-- > fromArgSet (Data.Set.fromList [Arg 3 "aaa", Arg 5 "aaaaa"]) == fromList [(5,"aaaaa"), (3,"aaa")]+-- > fromArgSet Data.Set.empty == empty++fromArgSet :: Set.Set (Arg k a) -> Map k a+fromArgSet Set.Tip = Tip+fromArgSet (Set.Bin sz (Arg x v) l r) = Bin sz x v (fromArgSet l) (fromArgSet r)+ {--------------------------------------------------------------------   Lists --------------------------------------------------------------------}-#if __GLASGOW_HASKELL__ >= 708++#ifdef __GLASGOW_HASKELL__ -- | @since 0.5.6.2 instance (Ord k) => GHCExts.IsList (Map k v) where   type Item (Map k v) = (k,v)@@ -3439,7 +3404,7 @@   toList   = toList #endif --- | /O(n*log n)/. Build a map from a list of key\/value pairs. See also 'fromAscList'.+-- | \(O(n \log n)\). Build a map from a list of key\/value pairs. See also 'fromAscList'. -- If the list contains more than one value for the same key, the last value -- for the key is retained. --@@ -3491,7 +3456,7 @@ {-# INLINABLE fromList #-} #endif --- | /O(n*log n)/. Build a map from a list of key\/value pairs with a combining function. See also 'fromAscListWith'.+-- | \(O(n \log n)\). Build a map from a list of key\/value pairs with a combining function. See also 'fromAscListWith'. -- -- > fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")] -- > fromListWith (++) [] == empty@@ -3503,7 +3468,7 @@ {-# INLINABLE fromListWith #-} #endif --- | /O(n*log n)/. Build a map from a list of key\/value pairs with a combining function. See also 'fromAscListWithKey'.+-- | \(O(n \log n)\). Build a map from a list of key\/value pairs with a combining function. See also 'fromAscListWithKey'. -- -- > let f k a1 a2 = (show k) ++ a1 ++ a2 -- > fromListWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "3ab"), (5, "5a5ba")]@@ -3518,7 +3483,7 @@ {-# INLINABLE fromListWithKey #-} #endif --- | /O(n)/. Convert the map to a list of key\/value pairs. Subject to list fusion.+-- | \(O(n)\). Convert the map to a list of key\/value pairs. Subject to list fusion. -- -- > toList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")] -- > toList empty == []@@ -3526,7 +3491,7 @@ toList :: Map k a -> [(k,a)] toList = toAscList --- | /O(n)/. Convert the map to a list of key\/value pairs where the keys are+-- | \(O(n)\). Convert the map to a list of key\/value pairs where the keys are -- in ascending order. Subject to list fusion. -- -- > toAscList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]@@ -3534,7 +3499,7 @@ toAscList :: Map k a -> [(k,a)] toAscList = foldrWithKey (\k x xs -> (k,x):xs) [] --- | /O(n)/. Convert the map to a list of key\/value pairs where the keys+-- | \(O(n)\). Convert the map to a list of key\/value pairs where the keys -- are in descending order. Subject to list fusion. -- -- > toDescList (fromList [(5,"a"), (3,"b")]) == [(5,"a"), (3,"b")]@@ -3584,7 +3549,7 @@     fromAscList xs       == fromList xs     fromAscListWith f xs == fromListWith f xs --------------------------------------------------------------------}--- | /O(n)/. Build a map from an ascending list in linear time.+-- | \(O(n)\). Build a map from an ascending list in linear time. -- /The precondition (input list is ascending) is not checked./ -- -- > fromAscList [(3,"b"), (5,"a")]          == fromList [(3, "b"), (5, "a")]@@ -3611,7 +3576,7 @@ {-# INLINABLE fromAscList #-} #endif --- | /O(n)/. Build a map from a descending list in linear time.+-- | \(O(n)\). Build a map from a descending list in linear time. -- /The precondition (input list is descending) is not checked./ -- -- > fromDescList [(5,"a"), (3,"b")]          == fromList [(3, "b"), (5, "a")]@@ -3639,7 +3604,7 @@ {-# INLINABLE fromDescList #-} #endif --- | /O(n)/. Build a map from an ascending list in linear time with a combining function for equal keys.+-- | \(O(n)\). Build a map from an ascending list in linear time with a combining function for equal keys. -- /The precondition (input list is ascending) is not checked./ -- -- > fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")]@@ -3653,7 +3618,7 @@ {-# INLINABLE fromAscListWith #-} #endif --- | /O(n)/. Build a map from a descending list in linear time with a combining function for equal keys.+-- | \(O(n)\). Build a map from a descending list in linear time with a combining function for equal keys. -- /The precondition (input list is descending) is not checked./ -- -- > fromDescListWith (++) [(5,"a"), (5,"b"), (3,"b")] == fromList [(3, "b"), (5, "ba")]@@ -3669,7 +3634,7 @@ {-# INLINABLE fromDescListWith #-} #endif --- | /O(n)/. Build a map from an ascending list in linear time with a+-- | \(O(n)\). Build a map from an ascending list in linear time with a -- combining function for equal keys. -- /The precondition (input list is ascending) is not checked./ --@@ -3697,7 +3662,7 @@ {-# INLINABLE fromAscListWithKey #-} #endif --- | /O(n)/. Build a map from a descending list in linear time with a+-- | \(O(n)\). Build a map from a descending list in linear time with a -- combining function for equal keys. -- /The precondition (input list is descending) is not checked./ --@@ -3725,7 +3690,7 @@ #endif  --- | /O(n)/. Build a map from an ascending list of distinct elements in linear time.+-- | \(O(n)\). Build a map from an ascending list of distinct elements in linear time. -- /The precondition is not checked./ -- -- > fromDistinctAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")]@@ -3751,7 +3716,7 @@                       (l :*: (ky, y):ys) -> case create (s `shiftR` 1) ys of                         (r :*: zs) -> (link ky y l r :*: zs) --- | /O(n)/. Build a map from a descending list of distinct elements in linear time.+-- | \(O(n)\). Build a map from a descending list of distinct elements in linear time. -- /The precondition is not checked./ -- -- > fromDistinctDescList [(5,"a"), (3,"b")] == fromList [(3, "b"), (5, "a")]@@ -3814,7 +3779,7 @@ {--------------------------------------------------------------------   Split --------------------------------------------------------------------}--- | /O(log n)/. The expression (@'split' k map@) is a pair @(map1,map2)@ where+-- | \(O(\log n)\). The expression (@'split' k map@) is a pair @(map1,map2)@ where -- the keys in @map1@ are smaller than @k@ and the keys in @map2@ larger than @k@. -- Any key equal to @k@ is found in neither @map1@ nor @map2@. --@@ -3838,7 +3803,7 @@ {-# INLINABLE split #-} #endif --- | /O(log n)/. The expression (@'splitLookup' k map@) splits a map just+-- | \(O(\log n)\). The expression (@'splitLookup' k map@) splits a map just -- like 'split' but also returns @'lookup' k map@. -- -- > splitLookup 2 (fromList [(5,"a"), (3,"b")]) == (empty, Nothing, fromList [(3,"b"), (5,"a")])@@ -3983,7 +3948,7 @@         MaxView km xm r' -> MaxView km xm (balanceL k x l r') {-# NOINLINE maxViewSure #-} --- | /O(log n)/. Delete and find the minimal element.+-- | \(O(\log n)\). Delete and find the minimal element. -- -- > deleteFindMin (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((3,"b"), fromList[(5,"a"), (10,"c")]) -- > deleteFindMin empty                                      Error: can not return the minimal element of an empty map@@ -3993,7 +3958,7 @@   Nothing -> (error "Map.deleteFindMin: can not return the minimal element of an empty map", Tip)   Just res -> res --- | /O(log n)/. Delete and find the maximal element.+-- | \(O(\log n)\). Delete and find the maximal element. -- -- > deleteFindMax (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((10,"c"), fromList [(3,"b"), (5,"a")]) -- > deleteFindMax empty                                      Error: can not return the maximal element of an empty map@@ -4183,7 +4148,6 @@ instance (Ord k, Ord v) => Ord (Map k v) where     compare m1 m2 = compare (toAscList m1) (toAscList m2) -#if MIN_VERSION_base(4,9,0) {--------------------------------------------------------------------   Lifted instances --------------------------------------------------------------------}@@ -4225,7 +4189,6 @@       where         rp' = liftReadsPrec rp rl         rl' = liftReadList rp rl-#endif  {--------------------------------------------------------------------   Functor@@ -4262,7 +4225,6 @@   {-# INLINE foldl' #-}   foldr' = foldr'   {-# INLINE foldr' #-}-#if MIN_VERSION_base(4,8,0)   length = size   {-# INLINE length #-}   null   = null@@ -4291,7 +4253,6 @@   {-# INLINABLE sum #-}   product = foldl' (*) 1   {-# INLINABLE product #-}-#endif  #if MIN_VERSION_base(4,10,0) -- | @since 0.6.3.1@@ -4346,16 +4307,10 @@     showString "fromList " . shows (toList m)  {---------------------------------------------------------------------  Typeable---------------------------------------------------------------------}--INSTANCE_TYPEABLE2(Map)--{--------------------------------------------------------------------   Utilities --------------------------------------------------------------------} --- | /O(1)/.  Decompose a map into pieces based on the structure of the underlying+-- | \(O(1)\).  Decompose a map into pieces based on the structure of the underlying -- tree.  This function is useful for consuming a map in parallel. -- -- No guarantee is made as to the sizes of the pieces; an internal, but

@@ -6,7 +6,7 @@ import Data.Map.Internal (Map (..), size, delta) import Control.Monad (guard) --- | /O(n)/. Show the tree that implements the map. The tree is shown+-- | \(O(n)\). Show the tree that implements the map. The tree is shown -- in a compressed, hanging format. See 'showTreeWith'. showTree :: (Show k,Show a) => Map k a -> String showTree m@@ -15,7 +15,7 @@     showElem k x  = show k ++ ":=" ++ show x  -{- | /O(n)/. The expression (@'showTreeWith' showelem hang wide map@) shows+{- | \(O(n)\). The expression (@'showTreeWith' showelem hang wide map@) shows  the tree that implements the map. Elements are shown using the @showElem@ function. If @hang@ is  'True', a /hanging/ tree is shown otherwise a rotated tree is shown. If  @wide@ is 'True', an extra wide version is shown.@@ -103,7 +103,7 @@ {--------------------------------------------------------------------   Assertions --------------------------------------------------------------------}--- | /O(n)/. Test if the internal map structure is valid.+-- | \(O(n)\). Test if the internal map structure is valid. -- -- > valid (fromAscList [(3,"b"), (5,"a")]) == True -- > valid (fromAscList [(5,"a"), (3,"b")]) == False

@@ -49,7 +49,7 @@ -- -- == Detailed performance information ----- The amortized running time is given for each operation, with /n/ referring to+-- The amortized running time is given for each operation, with \(n\) referring to -- the number of entries in the map. -- -- Benchmarks comparing "Data.Map.Lazy" with other dictionary implementations@@ -92,6 +92,7 @@     , empty     , singleton     , fromSet+    , fromArgSet      -- ** From Unordered Lists     , fromList@@ -207,6 +208,7 @@     , keys     , assocs     , keysSet+    , argSet      -- ** Lists     , toList

@@ -1,19 +1,6 @@ {-# LANGUAGE CPP #-}-{-# LANGUAGE BangPatterns #-}-#if __GLASGOW_HASKELL__-{-# LANGUAGE DeriveDataTypeable, StandaloneDeriving #-}-#endif-#if !defined(TESTING) && defined(__GLASGOW_HASKELL__)+#if defined(__GLASGOW_HASKELL__) {-# LANGUAGE Safe #-}-#endif-#if __GLASGOW_HASKELL__ >= 708-{-# LANGUAGE RoleAnnotations #-}-{-# LANGUAGE TypeFamilies #-}-#define USE_MAGIC_PROXY 1-#endif--#if USE_MAGIC_PROXY-{-# LANGUAGE MagicHash #-} #endif  #include "containers.h"

@@ -1,19 +1,6 @@ {-# LANGUAGE CPP #-}-{-# LANGUAGE BangPatterns #-}-#if __GLASGOW_HASKELL__-{-# LANGUAGE DeriveDataTypeable, StandaloneDeriving #-}-#endif-#if !defined(TESTING) && defined(__GLASGOW_HASKELL__)+#if defined(__GLASGOW_HASKELL__) {-# LANGUAGE Safe #-}-#endif-#if __GLASGOW_HASKELL__ >= 708-{-# LANGUAGE RoleAnnotations #-}-{-# LANGUAGE TypeFamilies #-}-#define USE_MAGIC_PROXY 1-#endif--#if USE_MAGIC_PROXY-{-# LANGUAGE MagicHash #-} #endif  #include "containers.h"

@@ -55,7 +55,7 @@ -- -- == Detailed performance information ----- The amortized running time is given for each operation, with /n/ referring to+-- The amortized running time is given for each operation, with \(n\) referring to -- the number of entries in the map. -- -- Benchmarks comparing "Data.Map.Strict" with other dictionary implementations@@ -108,6 +108,7 @@     , empty     , singleton     , fromSet+    , fromArgSet      -- ** From Unordered Lists     , fromList@@ -223,6 +224,7 @@     , keys     , assocs     , keysSet+    , argSet      -- ** Lists     , toList

@@ -226,7 +226,9 @@     , keys     , assocs     , keysSet+    , argSet     , fromSet+    , fromArgSet      -- ** Lists     , toList@@ -299,7 +301,7 @@     , maxViewWithKey      -- * Debugging-#if defined(__GLASGOW_HASKELL__)+#ifdef __GLASGOW_HASKELL__     , showTree     , showTreeWith #endif@@ -327,11 +329,10 @@   , (!)   , (!?)   , (\\)+  , argSet   , assocs   , atKeyImpl-#if MIN_VERSION_base(4,8,0)   , atKeyPlain-#endif   , balance   , balanceL   , balanceR@@ -415,26 +416,21 @@ import Data.Map.Internal.Debug (valid)  import Control.Applicative (Const (..), liftA3)-#if !MIN_VERSION_base(4,8,0)-import Control.Applicative (Applicative (..), (<$>))-#endif+import Data.Semigroup (Arg (..)) import qualified Data.Set.Internal as Set import qualified Data.Map.Internal as L import Utils.Containers.Internal.StrictPair  import Data.Bits (shiftL, shiftR)-#if __GLASGOW_HASKELL__ >= 709+#ifdef __GLASGOW_HASKELL__ import Data.Coerce #endif -#if __GLASGOW_HASKELL__ && MIN_VERSION_base(4,8,0)+#ifdef __GLASGOW_HASKELL__ import Data.Functor.Identity (Identity (..)) #endif  import qualified Data.Foldable as Foldable-#if !MIN_VERSION_base(4,8,0)-import Data.Foldable (Foldable())-#endif  -- $strictness --@@ -469,7 +465,7 @@   Query --------------------------------------------------------------------} --- | /O(log n)/. The expression @('findWithDefault' def k map)@ returns+-- | \(O(\log n)\). The expression @('findWithDefault' def k map)@ returns -- the value at key @k@ or returns default value @def@ -- when the key is not in the map. --@@ -495,7 +491,7 @@   Construction --------------------------------------------------------------------} --- | /O(1)/. A map with a single element.+-- | \(O(1)\). A map with a single element. -- -- > singleton 1 'a'        == fromList [(1, 'a')] -- > size (singleton 1 'a') == 1@@ -507,7 +503,7 @@ {--------------------------------------------------------------------   Insertion --------------------------------------------------------------------}--- | /O(log n)/. Insert a new key and value in the map.+-- | \(O(\log n)\). Insert a new key and value in the map. -- If the key is already present in the map, the associated value is -- replaced with the supplied value. 'insert' is equivalent to -- @'insertWith' 'const'@.@@ -533,7 +529,7 @@ {-# INLINE insert #-} #endif --- | /O(log n)/. Insert with a function, combining new value and old value.+-- | \(O(\log n)\). Insert with a function, combining new value and old value. -- @'insertWith' f key value mp@ -- will insert the pair (key, value) into @mp@ if key does -- not exist in the map. If the key does exist, the function will@@ -575,7 +571,7 @@ {-# INLINE insertWithR #-} #endif --- | /O(log n)/. Insert with a function, combining key, new value and old value.+-- | \(O(\log n)\). Insert with a function, combining key, new value and old value. -- @'insertWithKey' f key value mp@ -- will insert the pair (key, value) into @mp@ if key does -- not exist in the map. If the key does exist, the function will@@ -626,7 +622,7 @@ {-# INLINE insertWithKeyR #-} #endif --- | /O(log n)/. Combines insert operation with old value retrieval.+-- | \(O(\log n)\). Combines insert operation with old value retrieval. -- The expression (@'insertLookupWithKey' f k x map@) -- is a pair where the first element is equal to (@'lookup' k map@) -- and the second element equal to (@'insertWithKey' f k x map@).@@ -667,7 +663,7 @@   Deletion --------------------------------------------------------------------} --- | /O(log n)/. Update a value at a specific key with the result of the provided function.+-- | \(O(\log n)\). Update a value at a specific key with the result of the provided function. -- When the key is not -- a member of the map, the original map is returned. --@@ -683,7 +679,7 @@ {-# INLINE adjust #-} #endif --- | /O(log n)/. Adjust a value at a specific key. When the key is not+-- | \(O(\log n)\). Adjust a value at a specific key. When the key is not -- a member of the map, the original map is returned. -- -- > let f key x = (show key) ++ ":new " ++ x@@ -708,7 +704,7 @@ {-# INLINE adjustWithKey #-} #endif --- | /O(log n)/. The expression (@'update' f k map@) updates the value @x@+-- | \(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@. --@@ -725,7 +721,7 @@ {-# INLINE update #-} #endif --- | /O(log n)/. The expression (@'updateWithKey' f k map@) updates the+-- | \(O(\log n)\). The expression (@'updateWithKey' f k map@) updates the -- value @x@ at @k@ (if it is in the map). If (@f k x@) is 'Nothing', -- the element is deleted. If it is (@'Just' y@), the key @k@ is bound -- to the new value @y@.@@ -754,7 +750,7 @@ {-# INLINE updateWithKey #-} #endif --- | /O(log n)/. Lookup and update. See also 'updateWithKey'.+-- | \(O(\log n)\). Lookup and update. See also 'updateWithKey'. -- The function returns changed value, if it is updated. -- Returns the original key value if the map entry is deleted. --@@ -784,7 +780,7 @@ {-# INLINE updateLookupWithKey #-} #endif --- | /O(log n)/. The expression (@'alter' f k map@) alters the value @x@ at @k@, or absence thereof.+-- | \(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 : @'lookup' k ('alter' f k m) = f ('lookup' k m)@. --@@ -819,7 +815,7 @@ {-# INLINE alter #-} #endif --- | /O(log n)/. The expression (@'alterF' f k map@) alters the value @x@ at @k@, or absence thereof.+-- | \(O(\log n)\). The expression (@'alterF' f k map@) alters the value @x@ at @k@, or absence thereof. -- 'alterF' can be used to inspect, insert, delete, or update a value in a 'Map'. -- In short: @'lookup' k \<$\> 'alterF' f k m = f ('lookup' k m)@. --@@ -872,11 +868,6 @@ -- `Control.Applicative.Const` and just doing a lookup. {-# RULES "alterF/Const" forall k (f :: Maybe a -> Const b (Maybe a)) . alterF f k = \m -> Const . getConst . f $ lookup k m- #-}-#if MIN_VERSION_base(4,8,0)--- base 4.8 and above include Data.Functor.Identity, so we can--- save a pretty decent amount of time by handling it specially.-{-# RULES "alterF/Identity" forall k f . alterF f k = atKeyIdentity k f  #-} @@ -884,13 +875,12 @@ atKeyIdentity k f t = Identity $ atKeyPlain Strict k (coerce f) t {-# INLINABLE atKeyIdentity #-} #endif-#endif  {--------------------------------------------------------------------   Indexing --------------------------------------------------------------------} --- | /O(log n)/. Update the element at /index/. Calls 'error' when an+-- | \(O(\log n)\). Update the element at /index/. Calls 'error' when an -- invalid index is used. -- -- > updateAt (\ _ _ -> Just "x") 0    (fromList [(5,"a"), (3,"b")]) == fromList [(3, "x"), (5, "a")]@@ -919,7 +909,7 @@   Minimal, Maximal --------------------------------------------------------------------} --- | /O(log n)/. Update the value at the minimal key.+-- | \(O(\log n)\). Update the value at the minimal key. -- -- > updateMin (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "Xb"), (5, "a")] -- > updateMin (\ _ -> Nothing)         (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"@@ -928,7 +918,7 @@ updateMin f m   = updateMinWithKey (\_ x -> f x) m --- | /O(log n)/. Update the value at the maximal key.+-- | \(O(\log n)\). Update the value at the maximal key. -- -- > updateMax (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "Xa")] -- > updateMax (\ _ -> Nothing)         (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"@@ -938,7 +928,7 @@   = updateMaxWithKey (\_ x -> f x) m  --- | /O(log n)/. Update the value at the minimal key.+-- | \(O(\log n)\). Update the value at the minimal key. -- -- > updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"3:b"), (5,"a")] -- > updateMinWithKey (\ _ _ -> Nothing)                     (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"@@ -950,7 +940,7 @@                                            Just x' -> x' `seq` Bin sx kx x' Tip r updateMinWithKey f (Bin _ kx x l r)    = balanceR kx x (updateMinWithKey f l) r --- | /O(log n)/. Update the value at the maximal key.+-- | \(O(\log n)\). Update the value at the maximal key. -- -- > updateMaxWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"b"), (5,"5:a")] -- > updateMaxWithKey (\ _ _ -> Nothing)                     (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"@@ -982,7 +972,7 @@ {--------------------------------------------------------------------   Union with a combining function --------------------------------------------------------------------}--- | /O(m*log(n\/m + 1)), m <= n/. Union with a combining function.+-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\). Union with a combining function. -- -- > unionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")] @@ -998,7 +988,7 @@ {-# INLINABLE unionWith #-} #endif --- | /O(m*log(n\/m + 1)), m <= n/.+-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\). -- Union with a combining function. -- -- > let f key left_value right_value = (show key) ++ ":" ++ left_value ++ "|" ++ right_value@@ -1020,7 +1010,7 @@   Difference --------------------------------------------------------------------} --- | /O(n+m)/. Difference with a combining function.+-- | \(O(n+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@@ -1036,7 +1026,7 @@ {-# INLINABLE differenceWith #-} #endif --- | /O(n+m)/. Difference with a combining function. When two equal keys are+-- | \(O(n+m)\). Difference with a combining function. When two equal keys are -- encountered, the combining function is applied to the key and both values. -- 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@.@@ -1056,7 +1046,7 @@   Intersection --------------------------------------------------------------------} --- | /O(m*log(n\/m + 1)), m <= n/. Intersection with a combining function.+-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\). Intersection with a combining function. -- -- > intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "aA" @@ -1074,7 +1064,7 @@ {-# INLINABLE intersectionWith #-} #endif --- | /O(m*log(n\/m + 1)), m <= n/. Intersection with a combining function.+-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\). Intersection with a combining function. -- -- > let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ ar -- > intersectionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "5:a|A"@@ -1212,7 +1202,7 @@   MergeWithKey --------------------------------------------------------------------} --- | /O(n+m)/. An unsafe universal combining function.+-- | \(O(n+m)\). An unsafe universal combining function. -- -- WARNING: This function can produce corrupt maps and its results -- may depend on the internal structures of its inputs. Users should@@ -1274,7 +1264,7 @@   Filter and partition --------------------------------------------------------------------} --- | /O(n)/. Map values and collect the 'Just' results.+-- | \(O(n)\). Map values and collect the 'Just' results. -- -- > let f x = if x == "a" then Just "new a" else Nothing -- > mapMaybe f (fromList [(5,"a"), (3,"b")]) == singleton 5 "new a"@@ -1282,7 +1272,7 @@ mapMaybe :: (a -> Maybe b) -> Map k a -> Map k b mapMaybe f = mapMaybeWithKey (\_ x -> f x) --- | /O(n)/. Map keys\/values and collect the 'Just' results.+-- | \(O(n)\). Map keys\/values and collect the 'Just' results. -- -- > let f k _ = if k < 5 then Just ("key : " ++ (show k)) else Nothing -- > mapMaybeWithKey f (fromList [(5,"a"), (3,"b")]) == singleton 3 "key : 3"@@ -1293,7 +1283,7 @@   Just y  -> y `seq` link kx y (mapMaybeWithKey f l) (mapMaybeWithKey f r)   Nothing -> link2 (mapMaybeWithKey f l) (mapMaybeWithKey f r) --- | /O(n)/. Traverse keys\/values and collect the 'Just' results.+-- | \(O(n)\). Traverse keys\/values and collect the 'Just' results. -- -- @since 0.5.8 @@ -1309,7 +1299,7 @@           Nothing -> link2 l' r'           Just !x' -> link kx x' l' r' --- | /O(n)/. Map values and separate the 'Left' and 'Right' results.+-- | \(O(n)\). Map values and separate the 'Left' and 'Right' results. -- -- > let f a = if a < "c" then Left a else Right a -- > mapEither f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])@@ -1322,7 +1312,7 @@ mapEither f m   = mapEitherWithKey (\_ x -> f x) m --- | /O(n)/. Map keys\/values and separate the 'Left' and 'Right' results.+-- | \(O(n)\). Map keys\/values and separate the 'Left' and 'Right' results. -- -- > let f k a = if k < 5 then Left (k * 2) else Right (a ++ a) -- > mapEitherWithKey f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])@@ -1345,7 +1335,7 @@ {--------------------------------------------------------------------   Mapping --------------------------------------------------------------------}--- | /O(n)/. Map a function over all values in the map.+-- | \(O(n)\). Map a function over all values in the map. -- -- > map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")] @@ -1365,7 +1355,7 @@  #-} #endif --- | /O(n)/. Map a function over all values in the map.+-- | \(O(n)\). Map a function over all values in the map. -- -- > let f key x = (show key) ++ ":" ++ x -- > mapWithKey f (fromList [(5,"a"), (3,"b")]) == fromList [(3, "3:b"), (5, "5:a")]@@ -1394,7 +1384,7 @@  #-} #endif --- | /O(n)/.+-- | \(O(n)\). -- @'traverseWithKey' f m == 'fromList' <$> 'traverse' (\(k, v) -> (\v' -> v' \`seq\` (k,v')) <$> f k v) ('toList' m)@ -- That is, it behaves much like a regular 'traverse' except that the traversing -- function also has access to the key associated with a value and the values are@@ -1410,7 +1400,7 @@     go (Bin s k v l r) = liftA3 (\ l' !v' r' -> Bin s k v' l' r') (go l) (f k v) (go r) {-# INLINE traverseWithKey #-} --- | /O(n)/. The function 'mapAccum' threads an accumulating+-- | \(O(n)\). The function 'mapAccum' threads an accumulating -- argument through the map in ascending order of keys. -- -- > let f a b = (a ++ b, b ++ "X")@@ -1420,7 +1410,7 @@ mapAccum f a m   = mapAccumWithKey (\a' _ x' -> f a' x') a m --- | /O(n)/. The function 'mapAccumWithKey' threads an accumulating+-- | \(O(n)\). The function 'mapAccumWithKey' threads an accumulating -- argument through the map in ascending order of keys. -- -- > let f a k b = (a ++ " " ++ (show k) ++ "-" ++ b, b ++ "X")@@ -1430,7 +1420,7 @@ mapAccumWithKey f a t   = mapAccumL f a t --- | /O(n)/. The function 'mapAccumL' threads an accumulating+-- | \(O(n)\). The function 'mapAccumL' threads an accumulating -- argument through the map in ascending order of keys. mapAccumL :: (a -> k -> b -> (a,c)) -> a -> Map k b -> (a,Map k c) mapAccumL _ a Tip               = (a,Tip)@@ -1440,7 +1430,7 @@       (a3,r') = mapAccumL f a2 r   in x' `seq` (a3,Bin sx kx x' l' r') --- | /O(n)/. The function 'mapAccumRWithKey' threads an accumulating+-- | \(O(n)\). The function 'mapAccumRWithKey' threads an accumulating -- argument through the map in descending order of keys. mapAccumRWithKey :: (a -> k -> b -> (a,c)) -> a -> Map k b -> (a,Map k c) mapAccumRWithKey _ a Tip = (a,Tip)@@ -1450,7 +1440,7 @@       (a3,l') = mapAccumRWithKey f a2 l   in x' `seq` (a3,Bin sx kx x' l' r') --- | /O(n*log n)/.+-- | \(O(n \log n)\). -- @'mapKeysWith' c 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@@ -1471,7 +1461,7 @@   Conversions --------------------------------------------------------------------} --- | /O(n)/. Build a map from a set of keys and a function which for each key+-- | \(O(n)\). Build a map from a set of keys and a function which for each key -- computes its value. -- -- > fromSet (\k -> replicate k 'a') (Data.Set.fromList [3, 5]) == fromList [(5,"aaaaa"), (3,"aaa")]@@ -1481,10 +1471,19 @@ fromSet _ Set.Tip = Tip fromSet f (Set.Bin sz x l r) = case f x of v -> v `seq` Bin sz x v (fromSet f l) (fromSet f r) +-- | /O(n)/. Build a map from a set of elements contained inside 'Arg's.+--+-- > fromArgSet (Data.Set.fromList [Arg 3 "aaa", Arg 5 "aaaaa"]) == fromList [(5,"aaaaa"), (3,"aaa")]+-- > fromArgSet Data.Set.empty == empty++fromArgSet :: Set.Set (Arg k a) -> Map k a+fromArgSet Set.Tip = Tip+fromArgSet (Set.Bin sz (Arg x v) l r) = v `seq` Bin sz x v (fromArgSet l) (fromArgSet r)+ {--------------------------------------------------------------------   Lists --------------------------------------------------------------------}--- | /O(n*log n)/. Build a map from a list of key\/value pairs. See also 'fromAscList'.+-- | \(O(n \log n)\). Build a map from a list of key\/value pairs. See also 'fromAscList'. -- If the list contains more than one value for the same key, the last value -- for the key is retained. --@@ -1536,7 +1535,7 @@ {-# INLINABLE fromList #-} #endif --- | /O(n*log n)/. Build a map from a list of key\/value pairs with a combining function. See also 'fromAscListWith'.+-- | \(O(n \log n)\). Build a map from a list of key\/value pairs with a combining function. See also 'fromAscListWith'. -- -- > fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")] -- > fromListWith (++) [] == empty@@ -1548,7 +1547,7 @@ {-# INLINABLE fromListWith #-} #endif --- | /O(n*log n)/. Build a map from a list of key\/value pairs with a combining function. See also 'fromAscListWithKey'.+-- | \(O(n \log n)\). Build a map from a list of key\/value pairs with a combining function. See also 'fromAscListWithKey'. -- -- > let f k a1 a2 = (show k) ++ a1 ++ a2 -- > fromListWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "3ab"), (5, "5a5ba")]@@ -1575,7 +1574,7 @@     fromDescListWith f xs == fromListWith f xs --------------------------------------------------------------------} --- | /O(n)/. Build a map from an ascending list in linear time.+-- | \(O(n)\). Build a map from an ascending list in linear time. -- /The precondition (input list is ascending) is not checked./ -- -- > fromAscList [(3,"b"), (5,"a")]          == fromList [(3, "b"), (5, "a")]@@ -1589,7 +1588,7 @@ {-# INLINABLE fromAscList #-} #endif --- | /O(n)/. Build a map from a descending list in linear time.+-- | \(O(n)\). Build a map from a descending list in linear time. -- /The precondition (input list is descending) is not checked./ -- -- > fromDescList [(5,"a"), (3,"b")]          == fromList [(3, "b"), (5, "a")]@@ -1603,7 +1602,7 @@ {-# INLINABLE fromDescList #-} #endif --- | /O(n)/. Build a map from an ascending list in linear time with a combining function for equal keys.+-- | \(O(n)\). Build a map from an ascending list in linear time with a combining function for equal keys. -- /The precondition (input list is ascending) is not checked./ -- -- > fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")]@@ -1617,7 +1616,7 @@ {-# INLINABLE fromAscListWith #-} #endif --- | /O(n)/. Build a map from a descending list in linear time with a combining function for equal keys.+-- | \(O(n)\). Build a map from a descending list in linear time with a combining function for equal keys. -- /The precondition (input list is descending) is not checked./ -- -- > fromDescListWith (++) [(5,"a"), (5,"b"), (3,"b")] == fromList [(3, "b"), (5, "ba")]@@ -1631,7 +1630,7 @@ {-# INLINABLE fromDescListWith #-} #endif --- | /O(n)/. Build a map from an ascending list in linear time with a+-- | \(O(n)\). Build a map from an ascending list in linear time with a -- combining function for equal keys. -- /The precondition (input list is ascending) is not checked./ --@@ -1659,7 +1658,7 @@ {-# INLINABLE fromAscListWithKey #-} #endif --- | /O(n)/. Build a map from a descending list in linear time with a+-- | \(O(n)\). Build a map from a descending list in linear time with a -- combining function for equal keys. -- /The precondition (input list is descending) is not checked./ --@@ -1687,7 +1686,7 @@ {-# INLINABLE fromDescListWithKey #-} #endif --- | /O(n)/. Build a map from an ascending list of distinct elements in linear time.+-- | \(O(n)\). Build a map from an ascending list of distinct elements in linear time. -- /The precondition is not checked./ -- -- > fromDistinctAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")]@@ -1714,7 +1713,7 @@                       (l :*: (ky, y):ys) -> case create (s `shiftR` 1) ys of                         (r :*: zs) -> y `seq` (link ky y l r :*: zs) --- | /O(n)/. Build a map from a descending list of distinct elements in linear time.+-- | \(O(n)\). Build a map from a descending list of distinct elements in linear time. -- /The precondition is not checked./ -- -- > fromDistinctDescList [(5,"a"), (3,"b")] == fromList [(3, "b"), (5, "a")]

@@ -78,7 +78,7 @@ -- -- == Detailed performance information ----- An amortized running time is given for each operation, with /n/ referring+-- An amortized running time is given for each operation, with \(n\) referring -- to the length of the sequence and /i/ being the integral index used by -- some operations. These bounds hold even in a persistent (shared) setting. --

@@ -4,11 +4,14 @@ #if __GLASGOW_HASKELL__ {-# LANGUAGE DeriveDataTypeable #-} {-# LANGUAGE DeriveGeneric #-}+{-# LANGUAGE DeriveLift #-} {-# LANGUAGE StandaloneDeriving #-} {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE ScopedTypeVariables #-}-{-# LANGUAGE TypeFamilies #-}+{-# LANGUAGE TemplateHaskellQuotes #-} {-# LANGUAGE Trustworthy #-}+{-# LANGUAGE TypeFamilies #-}+{-# LANGUAGE TypeOperators #-} #endif #ifdef DEFINE_PATTERN_SYNONYMS {-# LANGUAGE PatternSynonyms #-}@@ -196,9 +199,7 @@ #if MIN_VERSION_base(4,11,0)     (<>), #endif-#if MIN_VERSION_base(4,8,0)     Applicative, (<$>), foldMap, Monoid,-#endif     null, length, lookup, take, drop, splitAt, foldl, foldl1, foldr, foldr1,     scanl, scanl1, scanr, scanr1, replicate, zip, zipWith, zip3, zipWith3,     unzip, takeWhile, dropWhile, iterate, reverse, filter, mapM, sum, all)@@ -213,16 +214,9 @@ import Data.Foldable (Foldable(foldl, foldl1, foldr, foldr1, foldMap, foldl', foldr'), toList) import qualified Data.Foldable as F -#if !(__GLASGOW_HASKELL__ >= 708)-import qualified Data.List-#endif--#if MIN_VERSION_base(4,9,0) import qualified Data.Semigroup as Semigroup import Data.Functor.Classes-#endif import Data.Traversable-import Data.Typeable  -- GHC specific stuff #ifdef __GLASGOW_HASKELL__@@ -231,8 +225,7 @@     readPrec, readListPrec, readListPrecDefault) import Data.Data import Data.String (IsString(..))-#endif-#if __GLASGOW_HASKELL__+import qualified Language.Haskell.TH.Syntax as TH import GHC.Generics (Generic, Generic1) #endif @@ -244,22 +237,11 @@ #endif  import Utils.Containers.Internal.Coercions ((.#), (.^#))--- Coercion on GHC 7.8+-#if __GLASGOW_HASKELL__ >= 708 import Data.Coerce import qualified GHC.Exts-#else-#endif --- Identity functor on base 4.8 (GHC 7.10+)-#if MIN_VERSION_base(4,8,0) import Data.Functor.Identity (Identity(..))-#endif -#if !MIN_VERSION_base(4,8,0)-import Data.Word (Word)-#endif- import Utils.Containers.Internal.StrictPair (StrictPair (..), toPair) import Control.Monad.Zip (MonadZip (..)) import Control.Monad.Fix (MonadFix (..), fix)@@ -358,6 +340,41 @@ -- | General-purpose finite sequences. newtype Seq a = Seq (FingerTree (Elem a)) +#ifdef __GLASGOW_HASKELL__+-- | @since FIXME+instance TH.Lift a => TH.Lift (Seq a) where+#  if MIN_VERSION_template_haskell(2,16,0)+  liftTyped t = [|| coerceFT z ||]+#  else+  lift t = [| coerceFT z |]+#  endif+    where+      -- We rebalance the sequence to use only 3-nodes before lifting its+      -- underlying finger tree. This should minimize the size and depth of the+      -- tree generated at run-time. It also reduces the size of the splice,+      -- but I don't know how that affects the size of the resulting Core once+      -- all the types are added.+      Seq ft = zipWith (flip const) (replicate (length t) ()) t++      -- We remove the 'Elem' constructors to reduce the size of the splice+      -- and the number of types and coercions in the generated Core. Instead+      -- of, say,+      --+      --   Seq (Deep 3 (Two (Elem 1) (Elem 2)) EmptyT (One (Elem 3)))+      --+      -- we generate+      --+      --   coerceFT (Deep 3 (Two 1 2)) EmptyT (One 3)+      z :: FingerTree a+      z = coerce ft++-- | We use this to help the types work out for splices in the+-- Lift instance. Things get a bit yucky otherwise.+coerceFT :: FingerTree a -> Seq a+coerceFT = coerce++#endif+ instance Functor Seq where     fmap = fmapSeq #ifdef __GLASGOW_HASKELL__@@ -370,11 +387,6 @@ {-# NOINLINE [1] fmapSeq #-} {-# RULES "fmapSeq/fmapSeq" forall f g xs . fmapSeq f (fmapSeq g xs) = fmapSeq (f . g) xs- #-}-#endif-#if __GLASGOW_HASKELL__ >= 709--- Safe coercions were introduced in 7.8, but did not work well with RULES yet.-{-# RULES "fmapSeq/coerce" fmapSeq coerce = coerce  #-} #endif@@ -407,12 +419,10 @@     foldl1 f (Seq xs) = getElem (foldl1 f' xs)       where f' (Elem x) (Elem y) = Elem (f x y) -#if MIN_VERSION_base(4,8,0)     length = length     {-# INLINE length #-}     null   = null     {-# INLINE null #-}-#endif  instance Traversable Seq where #if __GLASGOW_HASKELL__@@ -464,7 +474,7 @@                 (\a' b' c' d' -> Four (Elem a') (Elem b') (Elem c') (Elem d'))                 (f a)                 (f b)-                (f c) <*> +                (f c) <*>                 (f d)         traverseDigitN             :: Applicative f@@ -600,7 +610,7 @@              (fmap (fmap (f lastx)) (nodeToDigit sf))   where     lift_elem :: (a -> b -> c) -> a -> Elem b -> Elem c-#if __GLASGOW_HASKELL__ >= 708+#ifdef __GLASGOW_HASKELL__     lift_elem = coerce #else     lift_elem f x (Elem y) = Elem (f x y)@@ -782,8 +792,8 @@ squashR (Two12 n1 n2) m = node3 n1 n2 m  --- | /O(m*n)/ (incremental) Takes an /O(m)/ function and a finger tree of size--- /n/ and maps the function over the tree leaves. Unlike the usual 'fmap', the+-- | \(O(mn)\) (incremental) Takes an \(O(m)\) function and a finger tree of size+-- \(n\) and maps the function over the tree leaves. Unlike the usual 'fmap', the -- function is applied to the "leaves" of the 'FingerTree' (i.e., given a -- @FingerTree (Elem a)@, it applies the function to elements of type @Elem -- a@), replacing the leaves with subtrees of at least the same height, e.g.,@@ -798,7 +808,7 @@ mapMulNode mul f (Node2 s a b)   = Node2 (mul * s) (f a) (f b) mapMulNode mul f (Node3 s a b c) = Node3 (mul * s) (f a) (f b) (f c) --- | /O(log n)/ (incremental) Takes the extra flexibility out of a 'FingerTree'+-- | \(O(\log n)\) (incremental) Takes the extra flexibility out of a 'FingerTree' -- to make it a genuine 2-3 finger tree. The result of 'rigidify' will have -- only two and three digits at the top level and only one and two -- digits elsewhere. If the tree has fewer than four elements, 'rigidify'@@ -828,7 +838,7 @@      Three b c d -> RigidFull $ Rigid s (node2 a b) EmptyTh (node2 c d)      Four b c d e -> RigidFull $ Rigid s (node3 a b c) EmptyTh (node2 d e) --- | /O(log n)/ (incremental) Takes a tree whose left side has been rigidified+-- | \(O(\log n)\) (incremental) Takes a tree whose left side has been rigidified -- and finishes the job. rigidifyRight :: Int -> Digit23 (Elem a) -> FingerTree (Node (Elem a)) -> Digit (Elem a) -> Rigidified (Elem a) @@ -845,7 +855,7 @@       Node2 _ a b -> RigidThree a b e       Node3 _ a b c -> RigidFull $ Rigid s (node2 a b) EmptyTh (node2 c e) --- | /O(log n)/ (incremental) Rejigger a finger tree so the digits are all ones+-- | \(O(\log n)\) (incremental) Rejigger a finger tree so the digits are all ones -- and twos. thin :: Sized a => FingerTree a -> Thin a -- Note that 'thin12' will produce a 'DeepTh' constructor immediately before@@ -913,7 +923,6 @@         showString "fromList " . shows (toList xs) #endif -#if MIN_VERSION_base(4,9,0) -- | @since 0.5.9 instance Show1 Seq where   liftShowsPrec _shwsPrc shwList p xs = showParen (p > 10) $@@ -926,7 +935,6 @@ -- | @since 0.5.9 instance Ord1 Seq where     liftCompare cmp xs ys = liftCompare cmp (toList xs) (toList ys)-#endif  instance Read a => Read (Seq a) where #ifdef __GLASGOW_HASKELL__@@ -943,32 +951,22 @@         return (fromList xs,t) #endif -#if MIN_VERSION_base(4,9,0) -- | @since 0.5.9 instance Read1 Seq where   liftReadsPrec _rp readLst p = readParen (p > 10) $ \r -> do     ("fromList",s) <- lex r     (xs,t) <- readLst s     pure (fromList xs, t)-#endif  instance Monoid (Seq a) where     mempty = empty-#if MIN_VERSION_base(4,9,0)     mappend = (Semigroup.<>)-#else-    mappend = (><)-#endif -#if MIN_VERSION_base(4,9,0) -- | @since 0.5.7 instance Semigroup.Semigroup (Seq a) where     (<>)    = (><)     stimes = cycleNTimes . fromIntegral-#endif -INSTANCE_TYPEABLE1(Seq)- #if __GLASGOW_HASKELL__ instance Data a => Data (Seq a) where     gfoldl f z s    = case viewl s of@@ -1012,6 +1010,8 @@  -- | @since 0.6.1 deriving instance Generic (FingerTree a)++deriving instance TH.Lift a => TH.Lift (FingerTree a) #endif  instance Sized a => Sized (FingerTree a) where@@ -1024,7 +1024,7 @@ instance Foldable FingerTree where     foldMap _ EmptyT = mempty     foldMap f' (Single x') = f' x'-    foldMap f' (Deep _ pr' m' sf') = +    foldMap f' (Deep _ pr' m' sf') =         foldMapDigit f' pr' <>         foldMapTree (foldMapNode f') m' <>         foldMapDigit f' sf'@@ -1032,7 +1032,7 @@         foldMapTree :: Monoid m => (Node a -> m) -> FingerTree (Node a) -> m         foldMapTree _ EmptyT = mempty         foldMapTree f (Single x) = f x-        foldMapTree f (Deep _ pr m sf) = +        foldMapTree f (Deep _ pr m sf) =             foldMapDigitN f pr <>             foldMapTree (foldMapNodeN f) m <>             foldMapDigitN f sf@@ -1203,6 +1203,8 @@  -- | @since 0.6.1 deriving instance Generic (Digit a)++deriving instance TH.Lift a => TH.Lift (Digit a) #endif  foldDigit :: (b -> b -> b) -> (a -> b) -> Digit a -> b@@ -1304,6 +1306,8 @@  -- | @since 0.6.1 deriving instance Generic (Node a)++deriving instance TH.Lift a => TH.Lift (Node a) #endif  foldNode :: (b -> b -> b) -> (a -> b) -> Node a -> b@@ -1379,7 +1383,7 @@     size _ = 1  instance Functor Elem where-#if __GLASGOW_HASKELL__ >= 708+#ifdef __GLASGOW_HASKELL__ -- This cuts the time for <*> by around a fifth.     fmap = coerce #else@@ -1388,7 +1392,7 @@  instance Foldable Elem where     foldr f z (Elem x) = f x z-#if __GLASGOW_HASKELL__ >= 708+#ifdef __GLASGOW_HASKELL__     foldMap = coerce     foldl = coerce     foldl' = coerce@@ -1407,17 +1411,7 @@ ------------------------------------------------------- -- Applicative construction --------------------------------------------------------#if !MIN_VERSION_base(4,8,0)-newtype Identity a = Identity {runIdentity :: a} -instance Functor Identity where-    fmap f (Identity x) = Identity (f x)--instance Applicative Identity where-    pure = Identity-    Identity f <*> Identity x = Identity (f x)-#endif- -- | 'applicativeTree' takes an Applicative-wrapped construction of a -- piece of a FingerTree, assumed to always have the same size (which -- is put in the second argument), and replicates it as many times as@@ -1426,7 +1420,7 @@ {-# SPECIALIZE applicativeTree :: Int -> Int -> State s a -> State s (FingerTree a) #-} {-# SPECIALIZE applicativeTree :: Int -> Int -> Identity a -> Identity (FingerTree a) #-} -- Special note: the Identity specialization automatically does node sharing,--- reducing memory usage of the resulting tree to /O(log n)/.+-- reducing memory usage of the resulting tree to \(O(\log n)\). applicativeTree :: Applicative f => Int -> Int -> f a -> f (FingerTree a) applicativeTree n !mSize m = case n of     0 -> pure EmptyT@@ -1717,17 +1711,10 @@ -- -- For @base >= 4.8.0@ and @containers >= 0.5.11@, 'replicateM' -- is a synonym for 'replicateA'.-#if MIN_VERSION_base(4,8,0) replicateM :: Applicative m => Int -> m a -> m (Seq a) replicateM = replicateA-#else-replicateM :: Monad m => Int -> m a -> m (Seq a)-replicateM n x-  | n >= 0      = Applicative.unwrapMonad (replicateA n (Applicative.WrapMonad x))-  | otherwise   = error "replicateM takes a nonnegative integer argument"-#endif --- | /O(/log/ k)/. @'cycleTaking' k xs@ forms a sequence of length @k@ by+-- | \(O(\log k)\). @'cycleTaking' k xs@ forms a sequence of length @k@ by -- repeatedly concatenating @xs@ with itself. @xs@ may only be empty if -- @k@ is 0. --@@ -2186,9 +2173,10 @@  -- | @since 0.5.8 deriving instance Generic (ViewL a)-#endif -INSTANCE_TYPEABLE1(ViewL)+-- | @since FIXME+deriving instance TH.Lift a => TH.Lift (ViewL a)+#endif  instance Functor ViewL where     {-# INLINE fmap #-}@@ -2208,13 +2196,11 @@     foldl1 _ EmptyL = error "foldl1: empty view"     foldl1 f (x :< xs) = foldl f x xs -#if MIN_VERSION_base(4,8,0)     null EmptyL = True     null (_ :< _) = False      length EmptyL = 0     length (_ :< xs) = 1 + length xs-#endif  instance Traversable ViewL where     traverse _ EmptyL       = pure EmptyL@@ -2254,9 +2240,10 @@  -- | @since 0.5.8 deriving instance Generic (ViewR a)-#endif -INSTANCE_TYPEABLE1(ViewR)+-- | @since FIXME+deriving instance TH.Lift a => TH.Lift (ViewR a)+#endif  instance Functor ViewR where     {-# INLINE fmap #-}@@ -2275,13 +2262,12 @@      foldr1 _ EmptyR = error "foldr1: empty view"     foldr1 f (xs :> x) = foldr f x xs-#if MIN_VERSION_base(4,8,0)+     null EmptyR = True     null (_ :> _) = False      length EmptyR = 0     length (xs :> _) = length xs + 1-#endif  instance Traversable ViewR where     traverse _ EmptyR       = pure EmptyR@@ -2362,7 +2348,7 @@   -- See note on unsigned arithmetic in splitAt   | fromIntegral i < (fromIntegral (size xs) :: Word) = case lookupTree i xs of                 Place _ (Elem x) -> x-  | otherwise   = +  | otherwise   =       error $ "index out of bounds in call to: Data.Sequence.index " ++ show i  -- | \( O(\log(\min(i,n-i))) \). The element at the specified position,@@ -2552,7 +2538,7 @@ -- -- @since 0.5.8 adjust'          :: forall a . (a -> a) -> Int -> Seq a -> Seq a-#if __GLASGOW_HASKELL__ >= 708+#ifdef __GLASGOW_HASKELL__ adjust' f i xs   -- See note on unsigned arithmetic in splitAt   | fromIntegral i < (fromIntegral (length xs) :: Word) =@@ -3160,7 +3146,7 @@ foldMapWithIndex f' (Seq xs') = foldMapWithIndexTreeE (lift_elem f') 0 xs'  where   lift_elem :: (Int -> a -> m) -> (Int -> Elem a -> m)-#if __GLASGOW_HASKELL__ >= 708+#ifdef __GLASGOW_HASKELL__   lift_elem g = coerce g #else   lift_elem g = \s (Elem a) -> g s a@@ -3357,7 +3343,7 @@         {-# INLINE mb #-}      lift_elem :: (Int -> a) -> (Int -> Elem a)-#if __GLASGOW_HASKELL__ >= 708+#ifdef __GLASGOW_HASKELL__     lift_elem g = coerce g #else     lift_elem g = Elem . g@@ -3374,8 +3360,8 @@ #ifdef __GLASGOW_HASKELL__ fromArray a = fromFunction (GHC.Arr.numElements a) (GHC.Arr.unsafeAt a)  where-  -- The following definition uses (Ix i) constraing, which is needed for the-  -- other fromArray definition.+  -- The following definition uses an (Ix i) constraint, which is needed for+  -- the other fromArray definition.   _ = Data.Array.rangeSize (Data.Array.bounds a) #else fromArray a = fromList2 (Data.Array.rangeSize (Data.Array.bounds a)) (Data.Array.elems a)@@ -4392,7 +4378,7 @@             !n10 = Node3 (3*s) n1 n2 n3      map_elem :: [a] -> [Elem a]-#if __GLASGOW_HASKELL__ >= 708+#ifdef __GLASGOW_HASKELL__     map_elem xs = coerce xs #else     map_elem xs = Data.List.map Elem xs@@ -4402,7 +4388,7 @@ -- essentially: Free ((,) a) b. data ListFinal a cont = LFinal !cont | LCons !a (ListFinal a cont) -#if __GLASGOW_HASKELL__ >= 708+#ifdef __GLASGOW_HASKELL__ instance GHC.Exts.IsList (Seq a) where     type Item (Seq a) = a     fromList = fromList@@ -4433,7 +4419,7 @@ fmapReverse f (Seq xs) = Seq (fmapReverseTree (lift_elem f) xs)   where     lift_elem :: (a -> b) -> (Elem a -> Elem b)-#if __GLASGOW_HASKELL__ >= 708+#ifdef __GLASGOW_HASKELL__     lift_elem = coerce #else     lift_elem g (Elem a) = Elem (g a)@@ -4761,7 +4747,7 @@ -- This instance is only used at the very top of the tree; -- the rest of the elements are handled by unzipWithNodeElem instance UnzipWith Elem where-#if __GLASGOW_HASKELL__ >= 708+#ifdef __GLASGOW_HASKELL__   unzipWith' = coerce #else   unzipWith' f (Elem a) = case f a of (x, y) -> (Elem x, Elem y)

@@ -67,7 +67,7 @@ module Data.Set (             -- * Set type #if !defined(TESTING)-              Set          -- instance Eq,Ord,Show,Read,Data,Typeable+              Set          -- instance Eq,Ord,Show,Read,Data #else               Set(..) #endif

@@ -1,14 +1,13 @@ {-# LANGUAGE CPP #-} {-# LANGUAGE BangPatterns #-} {-# LANGUAGE PatternGuards #-}-#if __GLASGOW_HASKELL__-{-# LANGUAGE DeriveDataTypeable, StandaloneDeriving #-}-#endif #if !defined(TESTING) && defined(__GLASGOW_HASKELL__) {-# LANGUAGE Trustworthy #-} #endif-#if __GLASGOW_HASKELL__ >= 708+#ifdef __GLASGOW_HASKELL__+{-# LANGUAGE DeriveLift #-} {-# LANGUAGE RoleAnnotations #-}+{-# LANGUAGE StandaloneDeriving #-} {-# LANGUAGE TypeFamilies #-} #endif @@ -124,7 +123,7 @@  module Data.Set.Internal (             -- * Set type-              Set(..)       -- instance Eq,Ord,Show,Read,Data,Typeable+              Set(..)       -- instance Eq,Ord,Show,Read,Data             , Size              -- * Operators@@ -156,9 +155,16 @@             , unions             , difference             , intersection+#if (MIN_VERSION_base(4,9,0))+            , intersections+#endif             , cartesianProduct             , disjointUnion+#if (MIN_VERSION_base(4,9,0))+            , Intersection(..)+#endif +             -- * Filter             , filter             , takeWhileAntitone@@ -234,27 +240,15 @@ import Control.Applicative (Const(..)) import qualified Data.List as List import Data.Bits (shiftL, shiftR)-#if !MIN_VERSION_base(4,8,0)-import Data.Monoid (Monoid(..))-#endif-#if MIN_VERSION_base(4,9,0) import Data.Semigroup (Semigroup(stimes))-#endif-#if !(MIN_VERSION_base(4,11,0)) && MIN_VERSION_base(4,9,0)+import Data.List.NonEmpty (NonEmpty(..))+#if !(MIN_VERSION_base(4,11,0)) import Data.Semigroup (Semigroup((<>))) #endif-#if MIN_VERSION_base(4,9,0)-import Data.Semigroup (stimesIdempotentMonoid)+import Data.Semigroup (stimesIdempotentMonoid, stimesIdempotent) import Data.Functor.Classes-#endif-#if MIN_VERSION_base(4,8,0) import Data.Functor.Identity (Identity)-#endif import qualified Data.Foldable as Foldable-#if !MIN_VERSION_base(4,8,0)-import Data.Foldable (Foldable (foldMap))-#endif-import Data.Typeable import Control.DeepSeq (NFData(rnf))  import Utils.Containers.Internal.StrictPair@@ -262,12 +256,11 @@  #if __GLASGOW_HASKELL__ import GHC.Exts ( build, lazy )-#if __GLASGOW_HASKELL__ >= 708 import qualified GHC.Exts as GHCExts-#endif import Text.Read ( readPrec, Read (..), Lexeme (..), parens, prec                  , lexP, readListPrecDefault ) import Data.Data+import Language.Haskell.TH.Syntax (Lift) #endif  @@ -276,7 +269,7 @@ --------------------------------------------------------------------} infixl 9 \\ -- --- | /O(m*log(n\/m+1)), m <= n/. See 'difference'.+-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\). See 'difference'. (\\) :: Ord a => Set a -> Set a -> Set a m1 \\ m2 = difference m1 m2 #if __GLASGOW_HASKELL__@@ -294,25 +287,23 @@  type Size     = Int -#if __GLASGOW_HASKELL__ >= 708+#ifdef __GLASGOW_HASKELL__ type role Set nominal #endif +-- | @since FIXME+deriving instance Lift a => Lift (Set a)+ instance Ord a => Monoid (Set a) where     mempty  = empty     mconcat = unions-#if !(MIN_VERSION_base(4,9,0))-    mappend = union-#else     mappend = (<>)  -- | @since 0.5.7 instance Ord a => Semigroup (Set a) where     (<>)    = union     stimes  = stimesIdempotentMonoid-#endif - -- | Folds in order of increasing key. instance Foldable.Foldable Set where     fold = go@@ -333,7 +324,6 @@     {-# INLINE foldl' #-}     foldr' = foldr'     {-# INLINE foldr' #-}-#if MIN_VERSION_base(4,8,0)     length = size     {-# INLINE length #-}     null   = null@@ -352,9 +342,7 @@     {-# INLINABLE sum #-}     product = foldl' (*) 1     {-# INLINABLE product #-}-#endif - #if __GLASGOW_HASKELL__  {--------------------------------------------------------------------@@ -384,19 +372,19 @@ {--------------------------------------------------------------------   Query --------------------------------------------------------------------}--- | /O(1)/. Is this the empty set?+-- | \(O(1)\). Is this the empty set? null :: Set a -> Bool null Tip      = True null (Bin {}) = False {-# INLINE null #-} --- | /O(1)/. The number of elements in the set.+-- | \(O(1)\). The number of elements in the set. size :: Set a -> Int size Tip = 0 size (Bin sz _ _ _) = sz {-# INLINE size #-} --- | /O(log n)/. Is the element in the set?+-- | \(O(\log n)\). Is the element in the set? member :: Ord a => a -> Set a -> Bool member = go   where@@ -411,7 +399,7 @@ {-# INLINE member #-} #endif --- | /O(log n)/. Is the element not in the set?+-- | \(O(\log n)\). Is the element not in the set? notMember :: Ord a => a -> Set a -> Bool notMember a t = not $ member a t #if __GLASGOW_HASKELL__@@ -420,7 +408,7 @@ {-# INLINE notMember #-} #endif --- | /O(log n)/. Find largest element smaller than the given one.+-- | \(O(\log n)\). Find largest element smaller than the given one. -- -- > lookupLT 3 (fromList [3, 5]) == Nothing -- > lookupLT 5 (fromList [3, 5]) == Just 3@@ -440,7 +428,7 @@ {-# INLINE lookupLT #-} #endif --- | /O(log n)/. Find smallest element greater than the given one.+-- | \(O(\log n)\). Find smallest element greater than the given one. -- -- > lookupGT 4 (fromList [3, 5]) == Just 5 -- > lookupGT 5 (fromList [3, 5]) == Nothing@@ -460,7 +448,7 @@ {-# INLINE lookupGT #-} #endif --- | /O(log n)/. Find largest element smaller or equal to the given one.+-- | \(O(\log n)\). Find largest element smaller or equal to the given one. -- -- > lookupLE 2 (fromList [3, 5]) == Nothing -- > lookupLE 4 (fromList [3, 5]) == Just 3@@ -483,7 +471,7 @@ {-# INLINE lookupLE #-} #endif --- | /O(log n)/. Find smallest element greater or equal to the given one.+-- | \(O(\log n)\). Find smallest element greater or equal to the given one. -- -- > lookupGE 3 (fromList [3, 5]) == Just 3 -- > lookupGE 4 (fromList [3, 5]) == Just 5@@ -509,12 +497,12 @@ {--------------------------------------------------------------------   Construction --------------------------------------------------------------------}--- | /O(1)/. The empty set.+-- | \(O(1)\). The empty set. empty  :: Set a empty = Tip {-# INLINE empty #-} --- | /O(1)/. Create a singleton set.+-- | \(O(1)\). Create a singleton set. singleton :: a -> Set a singleton x = Bin 1 x Tip Tip {-# INLINE singleton #-}@@ -522,7 +510,7 @@ {--------------------------------------------------------------------   Insertion, Deletion --------------------------------------------------------------------}--- | /O(log n)/. Insert an element in a set.+-- | \(O(\log n)\). Insert an element in a set. -- If the set already contains an element equal to the given value, -- it is replaced with the new value. @@ -577,7 +565,7 @@ {-# INLINE insertR #-} #endif --- | /O(log n)/. Delete an element from a set.+-- | \(O(\log n)\). Delete an element from a set.  -- See Note: Type of local 'go' function delete :: Ord a => a -> Set a -> Set a@@ -599,7 +587,7 @@ {-# INLINE delete #-} #endif --- | /O(log n)/ @('alterF' f x s)@ can delete or insert @x@ in @s@ depending on+-- | \(O(\log n)\) @('alterF' f x s)@ can delete or insert @x@ in @s@ depending on -- whether an equal element is found in @s@. -- -- In short:@@ -633,9 +621,7 @@  #-} #endif -#if MIN_VERSION_base(4,8,0) {-# SPECIALIZE alterF :: Ord a => (Bool -> Identity Bool) -> a -> Set a -> Identity (Set a) #-}-#endif  data AlteredSet a       -- | The needle is present in the original set.@@ -668,7 +654,7 @@ {--------------------------------------------------------------------   Subset --------------------------------------------------------------------}--- | /O(m*log(n\/m + 1)), m <= n/.+-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\). -- @(s1 \`isProperSubsetOf\` s2)@ indicates whether @s1@ is a -- proper subset of @s2@. --@@ -683,7 +669,7 @@ #endif  --- | /O(m*log(n\/m + 1)), m <= n/.+-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\). -- @(s1 \`isSubsetOf\` s2)@ indicates whether @s1@ is a subset of @s2@. -- -- @@@ -704,7 +690,7 @@ -- -- This function is structured very much like `difference`, `union`, -- and `intersection`. Whereas the bounds proofs for those in Blelloch--- et al needed to accound for both "split work" and "merge work", we+-- et al needed to account for both "split work" and "merge work", we -- only have to worry about split work here, which is the same as in -- those functions. isSubsetOfX :: Ord a => Set a -> Set a -> Bool@@ -738,7 +724,7 @@ {--------------------------------------------------------------------   Disjoint --------------------------------------------------------------------}--- | /O(m*log(n\/m + 1)), m <= n/. Check whether two sets are disjoint+-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\). Check whether two sets are disjoint -- (i.e., their intersection is empty). -- -- > disjoint (fromList [2,4,6])   (fromList [1,3])     == True@@ -775,7 +761,7 @@ lookupMinSure x Tip = x lookupMinSure _ (Bin _ x l _) = lookupMinSure x l --- | /O(log n)/. The minimal element of a set.+-- | \(O(\log n)\). The minimal element of a set. -- -- @since 0.5.9 @@ -783,7 +769,7 @@ lookupMin Tip = Nothing lookupMin (Bin _ x l _) = Just $! lookupMinSure x l --- | /O(log n)/. The minimal element of a set.+-- | \(O(\log n)\). The minimal element of a set. findMin :: Set a -> a findMin t   | Just r <- lookupMin t = r@@ -793,7 +779,7 @@ lookupMaxSure x Tip = x lookupMaxSure _ (Bin _ x _ r) = lookupMaxSure x r --- | /O(log n)/. The maximal element of a set.+-- | \(O(\log n)\). The maximal element of a set. -- -- @since 0.5.9 @@ -801,19 +787,19 @@ lookupMax Tip = Nothing lookupMax (Bin _ x _ r) = Just $! lookupMaxSure x r --- | /O(log n)/. The maximal element of a set.+-- | \(O(\log n)\). The maximal element of a set. findMax :: Set a -> a findMax t   | Just r <- lookupMax t = r   | otherwise = error "Set.findMax: empty set has no maximal element" --- | /O(log n)/. Delete the minimal element. Returns an empty set if the set is empty.+-- | \(O(\log n)\). Delete the minimal element. Returns an empty set if the set is empty. deleteMin :: Set a -> Set a deleteMin (Bin _ _ Tip r) = r deleteMin (Bin _ x l r)   = balanceR x (deleteMin l) r deleteMin Tip             = Tip --- | /O(log n)/. Delete the maximal element. Returns an empty set if the set is empty.+-- | \(O(\log n)\). Delete the maximal element. Returns an empty set if the set is empty. deleteMax :: Set a -> Set a deleteMax (Bin _ _ l Tip) = l deleteMax (Bin _ x l r)   = balanceL x l (deleteMax r)@@ -829,7 +815,7 @@ {-# INLINABLE unions #-} #endif --- | /O(m*log(n\/m + 1)), m <= n/. The union of two sets, preferring the first set when+-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\). The union of two sets, preferring the first set when -- equal elements are encountered. union :: Ord a => Set a -> Set a -> Set a union t1 Tip  = t1@@ -849,7 +835,7 @@ {--------------------------------------------------------------------   Difference --------------------------------------------------------------------}--- | /O(m*log(n\/m + 1)), m <= n/. Difference of two sets.+-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\). Difference of two sets. -- -- Return elements of the first set not existing in the second set. --@@ -870,7 +856,7 @@ {--------------------------------------------------------------------   Intersection --------------------------------------------------------------------}--- | /O(m*log(n\/m + 1)), m <= n/. The intersection of two sets.+-- | \(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\). The intersection of two sets. -- Elements of the result come from the first set, so for example -- -- > import qualified Data.Set as S@@ -897,10 +883,28 @@ {-# INLINABLE intersection #-} #endif +#if (MIN_VERSION_base(4,9,0))+-- | The intersection of a series of sets. Intersections are performed left-to-right.+intersections :: Ord a => NonEmpty (Set a) -> Set a+intersections (s0 :| ss) = List.foldr go id ss s0+    where+      go s r acc+          | null acc = empty+          | otherwise = r (intersection acc s)++-- | Sets form a 'Semigroup' under 'intersection'.+newtype Intersection a = Intersection { getIntersection :: Set a }+    deriving (Show, Eq, Ord)++instance (Ord a) => Semigroup (Intersection a) where+    (Intersection a) <> (Intersection b) = Intersection $ intersection a b+    stimes = stimesIdempotent+#endif+ {--------------------------------------------------------------------   Filter and partition --------------------------------------------------------------------}--- | /O(n)/. Filter all elements that satisfy the predicate.+-- | \(O(n)\). Filter all elements that satisfy the predicate. filter :: (a -> Bool) -> Set a -> Set a filter _ Tip = Tip filter p t@(Bin _ x l r)@@ -912,7 +916,7 @@       !l' = filter p l       !r' = filter p r --- | /O(n)/. Partition the set into two sets, one with all elements that satisfy+-- | \(O(n)\). Partition the set into two sets, one with all elements that satisfy -- the predicate and one with all elements that don't satisfy the predicate. -- See also 'split'. partition :: (a -> Bool) -> Set a -> (Set a,Set a)@@ -933,7 +937,7 @@   Map ----------------------------------------------------------------------} --- | /O(n*log n)/.+-- | \(O(n \log n)\). -- @'map' f s@ is the set obtained by applying @f@ to each element of @s@. -- -- It's worth noting that the size of the result may be smaller if,@@ -945,7 +949,7 @@ {-# INLINABLE map #-} #endif --- | /O(n)/. The+-- | \(O(n)\). The -- -- @'mapMonotonic' f s == 'map' f s@, but works only when @f@ is strictly increasing. -- /The precondition is not checked./@@ -962,7 +966,7 @@ {--------------------------------------------------------------------   Fold --------------------------------------------------------------------}--- | /O(n)/. Fold the elements in the set using the given right-associative+-- | \(O(n)\). Fold the elements in the set using the given right-associative -- binary operator. This function is an equivalent of 'foldr' and is present -- for compatibility only. --@@ -971,7 +975,7 @@ fold = foldr {-# INLINE fold #-} --- | /O(n)/. Fold the elements in the set using the given right-associative+-- | \(O(n)\). Fold the elements in the set using the given right-associative -- binary operator, such that @'foldr' f z == 'Prelude.foldr' f z . 'toAscList'@. -- -- For example,@@ -984,7 +988,7 @@     go z' (Bin _ x l r) = go (f x (go z' r)) l {-# INLINE foldr #-} --- | /O(n)/. A strict version of 'foldr'. Each application of the operator is+-- | \(O(n)\). A strict version of 'foldr'. Each application of the operator is -- evaluated before using the result in the next application. This -- function is strict in the starting value. foldr' :: (a -> b -> b) -> b -> Set a -> b@@ -994,7 +998,7 @@     go z' (Bin _ x l r) = go (f x $! go z' r) l {-# INLINE foldr' #-} --- | /O(n)/. Fold the elements in the set using the given left-associative+-- | \(O(n)\). Fold the elements in the set using the given left-associative -- binary operator, such that @'foldl' f z == 'Prelude.foldl' f z . 'toAscList'@. -- -- For example,@@ -1007,7 +1011,7 @@     go z' (Bin _ x l r) = go (f (go z' l) x) r {-# INLINE foldl #-} --- | /O(n)/. A strict version of 'foldl'. Each application of the operator is+-- | \(O(n)\). A strict version of 'foldl'. Each application of the operator is -- evaluated before using the result in the next application. This -- function is strict in the starting value. foldl' :: (a -> b -> a) -> a -> Set b -> a@@ -1022,7 +1026,7 @@ {--------------------------------------------------------------------   List variations --------------------------------------------------------------------}--- | /O(n)/. An alias of 'toAscList'. The elements of a set in ascending order.+-- | \(O(n)\). An alias of 'toAscList'. The elements of a set in ascending order. -- Subject to list fusion. elems :: Set a -> [a] elems = toAscList@@ -1030,7 +1034,8 @@ {--------------------------------------------------------------------   Lists --------------------------------------------------------------------}-#if __GLASGOW_HASKELL__ >= 708++#ifdef __GLASGOW_HASKELL__ -- | @since 0.5.6.2 instance (Ord a) => GHCExts.IsList (Set a) where   type Item (Set a) = a@@ -1038,15 +1043,15 @@   toList   = toList #endif --- | /O(n)/. Convert the set to a list of elements. Subject to list fusion.+-- | \(O(n)\). Convert the set to a list of elements. Subject to list fusion. toList :: Set a -> [a] toList = toAscList --- | /O(n)/. Convert the set to an ascending list of elements. Subject to list fusion.+-- | \(O(n)\). Convert the set to an ascending list of elements. Subject to list fusion. toAscList :: Set a -> [a] toAscList = foldr (:) [] --- | /O(n)/. Convert the set to a descending list of elements. Subject to list+-- | \(O(n)\). Convert the set to a descending list of elements. Subject to list -- fusion. toDescList :: Set a -> [a] toDescList = foldl (flip (:)) []@@ -1080,7 +1085,7 @@ {-# RULES "Set.toDescListBack" [1] foldlFB (\xs x -> x : xs) [] = toDescList #-} #endif --- | /O(n*log n)/. Create a set from a list of elements.+-- | \(O(n \log n)\). Create a set from a list of elements. -- -- If the elements are ordered, a linear-time implementation is used, -- with the performance equal to 'fromDistinctAscList'.@@ -1132,7 +1137,7 @@   Note that if [xs] is ascending that:     fromAscList xs == fromList xs --------------------------------------------------------------------}--- | /O(n)/. Build a set from an ascending list in linear time.+-- | \(O(n)\). Build a set from an ascending list in linear time. -- /The precondition (input list is ascending) is not checked./ fromAscList :: Eq a => [a] -> Set a fromAscList xs = fromDistinctAscList (combineEq xs)@@ -1140,7 +1145,7 @@ {-# INLINABLE fromAscList #-} #endif --- | /O(n)/. Build a set from a descending list in linear time.+-- | \(O(n)\). Build a set from a descending list in linear time. -- /The precondition (input list is descending) is not checked./ -- -- @since 0.5.8@@ -1164,7 +1169,7 @@       | z == y = combineEq' z ys       | otherwise = z : combineEq' y ys --- | /O(n)/. Build a set from an ascending list of distinct elements in linear time.+-- | \(O(n)\). Build a set from an ascending list of distinct elements in linear time. -- /The precondition (input list is strictly ascending) is not checked./  -- For some reason, when 'singleton' is used in fromDistinctAscList or in@@ -1186,7 +1191,7 @@                       (l :*: (y:ys)) -> case create (s `shiftR` 1) ys of                         (r :*: zs) -> (link y l r :*: zs) --- | /O(n)/. Build a set from a descending list of distinct elements in linear time.+-- | \(O(n)\). Build a set from a descending list of distinct elements in linear time. -- /The precondition (input list is strictly descending) is not checked./  -- For some reason, when 'singleton' is used in fromDistinctDescList or in@@ -1232,7 +1237,6 @@   showsPrec p xs = showParen (p > 10) $     showString "fromList " . shows (toList xs) -#if MIN_VERSION_base(4,9,0) -- | @since 0.5.9 instance Eq1 Set where     liftEq eq m n =@@ -1247,7 +1251,6 @@ instance Show1 Set where     liftShowsPrec sp sl d m =         showsUnaryWith (liftShowsPrec sp sl) "fromList" d (toList m)-#endif  {--------------------------------------------------------------------   Read@@ -1268,12 +1271,6 @@ #endif  {---------------------------------------------------------------------  Typeable/Data---------------------------------------------------------------------}--INSTANCE_TYPEABLE1(Set)--{--------------------------------------------------------------------   NFData --------------------------------------------------------------------} @@ -1284,7 +1281,7 @@ {--------------------------------------------------------------------   Split --------------------------------------------------------------------}--- | /O(log n)/. The expression (@'split' x set@) is a pair @(set1,set2)@+-- | \(O(\log n)\). The expression (@'split' x set@) is a pair @(set1,set2)@ -- where @set1@ comprises the elements of @set@ less than @x@ and @set2@ -- comprises the elements of @set@ greater than @x@. split :: Ord a => a -> Set a -> (Set a,Set a)@@ -1300,7 +1297,7 @@           EQ -> (l :*: r) {-# INLINABLE splitS #-} --- | /O(log n)/. Performs a 'split' but also returns whether the pivot+-- | \(O(\log n)\). Performs a 'split' but also returns whether the pivot -- element was found in the original set. splitMember :: Ord a => a -> Set a -> (Set a,Bool,Set a) splitMember _ Tip = (Tip, False, Tip)@@ -1321,7 +1318,7 @@   Indexing --------------------------------------------------------------------} --- | /O(log n)/. Return the /index/ of an element, which is its zero-based+-- | \(O(\log n)\). Return the /index/ of an element, which is its zero-based -- index in the sorted sequence of elements. The index is a number from /0/ up -- to, but not including, the 'size' of the set. Calls 'error' when the element -- is not a 'member' of the set.@@ -1347,7 +1344,7 @@ {-# INLINABLE findIndex #-} #endif --- | /O(log n)/. Lookup the /index/ of an element, which is its zero-based index in+-- | \(O(\log n)\). Lookup the /index/ of an element, which is its zero-based index in -- the sorted sequence of elements. The index is a number from /0/ up to, but not -- including, the 'size' of the set. --@@ -1372,7 +1369,7 @@ {-# INLINABLE lookupIndex #-} #endif --- | /O(log n)/. Retrieve an element by its /index/, i.e. by its zero-based+-- | \(O(\log n)\). Retrieve an element by its /index/, i.e. by its zero-based -- index in the sorted sequence of elements. If the /index/ is out of range (less -- than zero, greater or equal to 'size' of the set), 'error' is called. --@@ -1392,7 +1389,7 @@   where     sizeL = size l --- | /O(log n)/. Delete the element at /index/, i.e. by its zero-based index in+-- | \(O(\log n)\). Delete the element at /index/, i.e. by its zero-based index in -- the sorted sequence of elements. If the /index/ is out of range (less than zero, -- greater or equal to 'size' of the set), 'error' is called. --@@ -1456,7 +1453,7 @@         EQ -> insertMin x r       where sizeL = size l --- | /O(log n)/. Split a set at a particular index.+-- | \(O(\log n)\). Split a set at a particular index. -- -- @ -- splitAt !n !xs = ('take' n xs, 'drop' n xs)@@ -1477,7 +1474,7 @@           EQ -> l :*: insertMin x r       where sizeL = size l --- | /O(log n)/. Take while a predicate on the elements holds.+-- | \(O(\log n)\). Take while a predicate on the elements holds. -- The user is responsible for ensuring that for all elements @j@ and @k@ in the set, -- @j \< k ==\> p j \>= p k@. See note at 'spanAntitone'. --@@ -1494,7 +1491,7 @@   | p x = link x l (takeWhileAntitone p r)   | otherwise = takeWhileAntitone p l --- | /O(log n)/. Drop while a predicate on the elements holds.+-- | \(O(\log n)\). Drop while a predicate on the elements holds. -- The user is responsible for ensuring that for all elements @j@ and @k@ in the set, -- @j \< k ==\> p j \>= p k@. See note at 'spanAntitone'. --@@ -1511,7 +1508,7 @@   | p x = dropWhileAntitone p r   | otherwise = link x (dropWhileAntitone p l) r --- | /O(log n)/. Divide a set at the point where a predicate on the elements stops holding.+-- | \(O(\log n)\). Divide a set at the point where a predicate on the elements stops holding. -- The user is responsible for ensuring that for all elements @j@ and @k@ in the set, -- @j \< k ==\> p j \>= p k@. --@@ -1606,7 +1603,7 @@   | sl > sr = let !(m :*: l') = maxViewSure xl ll lr in balanceR m l' r   | otherwise = let !(m :*: r') = minViewSure xr rl rr in balanceL m l r' --- | /O(log n)/. Delete and find the minimal element.+-- | \(O(\log n)\). Delete and find the minimal element. -- -- > deleteFindMin set = (findMin set, deleteMin set) @@ -1615,7 +1612,7 @@   | Just r <- minView t = r   | otherwise = (error "Set.deleteFindMin: can not return the minimal element of an empty set", Tip) --- | /O(log n)/. Delete and find the maximal element.+-- | \(O(\log n)\). Delete and find the maximal element. -- -- > deleteFindMax set = (findMax set, deleteMax set) deleteFindMax :: Set a -> (a,Set a)@@ -1631,7 +1628,7 @@       case go xl ll lr of         xm :*: l' -> xm :*: balanceR x l' r --- | /O(log n)/. Retrieves the minimal key of the set, and the set+-- | \(O(\log n)\). Retrieves the minimal key of the set, and the set -- stripped of that element, or 'Nothing' if passed an empty set. minView :: Set a -> Maybe (a, Set a) minView Tip = Nothing@@ -1645,7 +1642,7 @@       case go xr rl rr of         xm :*: r' -> xm :*: balanceL x l r' --- | /O(log n)/. Retrieves the maximal key of the set, and the set+-- | \(O(\log n)\). Retrieves the maximal key of the set, and the set -- stripped of that element, or 'Nothing' if passed an empty set. maxView :: Set a -> Maybe (a, Set a) maxView Tip = Nothing@@ -1661,14 +1658,14 @@   [ratio] is the ratio between an outer and inner sibling of the           heavier subtree in an unbalanced setting. It determines           whether a double or single rotation should be performed-          to restore balance. It is correspondes with the inverse+          to restore balance. It is corresponds with the inverse           of $\alpha$ in Adam's article.    Note that according to the Adam's paper:   - [delta] should be larger than 4.646 with a [ratio] of 2.   - [delta] should be larger than 3.745 with a [ratio] of 1.534. -  But the Adam's paper is errorneous:+  But the Adam's paper is erroneous:   - it can be proved that for delta=2 and delta>=5 there does     not exist any ratio that would work   - delta=4.5 and ratio=2 does not work@@ -1788,7 +1785,7 @@   Utilities --------------------------------------------------------------------} --- | /O(1)/.  Decompose a set into pieces based on the structure of the underlying+-- | \(O(1)\).  Decompose a set into pieces based on the structure of the underlying -- tree.  This function is useful for consuming a set in parallel. -- -- No guarantee is made as to the sizes of the pieces; an internal, but@@ -1834,7 +1831,7 @@ powerSet xs0 = insertMin empty (foldr' step Tip xs0) where   step x pxs = insertMin (singleton x) (insertMin x `mapMonotonic` pxs) `glue` pxs --- | /O(m*n)/ (conjectured). Calculate the Cartesian product of two sets.+-- | \(O(mn)\) (conjectured). Calculate the Cartesian product of two sets. -- -- @ -- cartesianProduct xs ys = fromList $ liftA2 (,) (toList xs) (toList ys)@@ -1878,19 +1875,13 @@ -- This is used to define cartesianProduct. newtype MergeSet a = MergeSet { getMergeSet :: Set a } -#if (MIN_VERSION_base(4,9,0)) instance Semigroup (MergeSet a) where   MergeSet xs <> MergeSet ys = MergeSet (merge xs ys)-#endif  instance Monoid (MergeSet a) where   mempty = MergeSet empty -#if (MIN_VERSION_base(4,9,0))   mappend = (<>)-#else-  mappend (MergeSet xs) (MergeSet ys) = MergeSet (merge xs ys)-#endif  -- | Calculate the disjoint union of two sets. --@@ -1910,14 +1901,14 @@ {--------------------------------------------------------------------   Debugging --------------------------------------------------------------------}--- | /O(n)/. Show the tree that implements the set. The tree is shown+-- | \(O(n)\). Show the tree that implements the set. The tree is shown -- in a compressed, hanging format. showTree :: Show a => Set a -> String showTree s   = showTreeWith True False s  -{- | /O(n)/. The expression (@showTreeWith hang wide map@) shows+{- | \(O(n)\). The expression (@showTreeWith hang wide map@) shows  the tree that implements the set. If @hang@ is  @True@, a /hanging/ tree is shown otherwise a rotated tree is shown. If  @wide@ is 'True', an extra wide version is shown.@@ -2004,7 +1995,7 @@ {--------------------------------------------------------------------   Assertions --------------------------------------------------------------------}--- | /O(n)/. Test if the internal set structure is valid.+-- | \(O(n)\). Test if the internal set structure is valid. valid :: Ord a => Set a -> Bool valid t   = balanced t && ordered t && validsize t

@@ -1,8 +1,9 @@ {-# LANGUAGE PatternGuards #-} {-# LANGUAGE CPP #-} #if __GLASGOW_HASKELL__-{-# LANGUAGE DeriveDataTypeable, StandaloneDeriving #-}+{-# LANGUAGE DeriveDataTypeable #-} {-# LANGUAGE DeriveGeneric #-}+{-# LANGUAGE DeriveLift #-} {-# LANGUAGE Trustworthy #-} #endif @@ -51,44 +52,30 @@      ) where -#if MIN_VERSION_base(4,8,0) import Data.Foldable (toList) import Control.Applicative (Applicative(..), liftA2)-#else-import Control.Applicative (Applicative(..), liftA2, (<$>))-import Data.Foldable (Foldable(foldMap), toList)-import Data.Monoid (Monoid(..))-import Data.Traversable (Traversable(traverse))-#endif- import Control.Monad (liftM) import Control.Monad.Fix (MonadFix (..), fix) import Data.Sequence (Seq, empty, singleton, (<|), (|>), fromList,             ViewL(..), ViewR(..), viewl, viewr)-import Data.Typeable import Control.DeepSeq (NFData(rnf))  #ifdef __GLASGOW_HASKELL__ import Data.Data (Data) import GHC.Generics (Generic, Generic1)+import Language.Haskell.TH.Syntax (Lift) #endif  import Control.Monad.Zip (MonadZip (..)) -#if MIN_VERSION_base(4,8,0) import Data.Coerce-#endif -#if MIN_VERSION_base(4,9,0) import Data.Functor.Classes-#endif-#if (!MIN_VERSION_base(4,11,0)) && MIN_VERSION_base(4,9,0)++#if !MIN_VERSION_base(4,11,0) import Data.Semigroup (Semigroup (..)) #endif -#if !MIN_VERSION_base(4,8,0)-import Data.Functor ((<$))-#endif  -- | Non-empty, possibly infinite, multi-way trees; also known as /rose trees/. data Tree a = Node {@@ -103,6 +90,7 @@            , Data            , Generic  -- ^ @since 0.5.8            , Generic1 -- ^ @since 0.5.8+           , Lift -- ^ @since FIXME            ) #else   deriving (Eq, Ord, Read, Show)@@ -112,7 +100,6 @@ -- reasons. type Forest a = [Tree a] -#if MIN_VERSION_base(4,9,0) -- | @since 0.5.9 instance Eq1 Tree where   liftEq eq = leq@@ -147,19 +134,15 @@       (fr, s9) <- liftReadList rd rdl s8       ("}", s10) <- lex s9       pure (Node a fr, s10)-#endif -INSTANCE_TYPEABLE1(Tree)- instance Functor Tree where     fmap = fmapTree     x <$ Node _ ts = Node x (map (x <$) ts)  fmapTree :: (a -> b) -> Tree a -> Tree b fmapTree f (Node x ts) = Node (f x) (map (fmapTree f) ts)-#if MIN_VERSION_base(4,8,0)--- Safe coercions were introduced in 4.7.0, but I am not sure if they played--- well enough with RULES to do what we want.++#ifdef __GLASGOW_HASKELL__ {-# NOINLINE [1] fmapTree #-} {-# RULES "fmapTree/coerce" fmapTree coerce = coerce@@ -200,12 +183,11 @@ instance Foldable Tree where     foldMap f (Node x ts) = f x `mappend` foldMap (foldMap f) ts -#if MIN_VERSION_base(4,8,0)     null _ = False     {-# INLINE null #-}+     toList = flatten     {-# INLINE toList #-}-#endif  instance NFData a => NFData (Tree a) where     rnf (Node x ts) = rnf x `seq` rnf ts

@@ -44,23 +44,10 @@     , toListQ     ) where -#if !MIN_VERSION_base(4,8,0)-import Data.Word (Word)-#endif import Utils.Containers.Internal.BitUtil (shiftLL, shiftRL, wordSize) import Data.Bits ((.|.), (.&.), testBit)-#if MIN_VERSION_base(4,8,0) import Data.Bits (countTrailingZeros)-#else-import Data.Bits (popCount)-#endif -#if !MIN_VERSION_base(4,8,0)-countTrailingZeros :: Word -> Int-countTrailingZeros x = popCount ((x .&. (-x)) - 1)-{-# INLINE countTrailingZeros #-}-#endif- -- A bit queue builder. We represent a double word using two words -- because we don't currently have access to proper double words. data BitQueueB = BQB {-# UNPACK #-} !Word@@ -109,7 +96,7 @@   lo' = (lo1 `shiftRL` zeros) .|. (hi1 `shiftLL` (wordSize - zeros))   hi' = hi1 `shiftRL` zeros --- Test if the queue is empty, which occurs when theres+-- Test if the queue is empty, which occurs when there's -- nothing left but a guard bit in the least significant -- place. nullQ :: BitQueue -> Bool

@@ -38,23 +38,10 @@     , wordSize     ) where -#if !MIN_VERSION_base(4,8,0)-import Data.Bits ((.|.), xor)-#endif import Data.Bits (popCount, unsafeShiftL, unsafeShiftR-#if MIN_VERSION_base(4,8,0)-    , countLeadingZeros-#endif+    , countLeadingZeros, finiteBitSize     )-#if MIN_VERSION_base(4,7,0)-import Data.Bits (finiteBitSize)-#else-import Data.Bits (bitSize)-#endif -#if !MIN_VERSION_base (4,8,0)-import Data.Word (Word)-#endif  {----------------------------------------------------------------------   [bitcount] as posted by David F. Place to haskell-cafe on April 11, 2006,@@ -78,21 +65,7 @@  -- | Return a word where only the highest bit is set. highestBitMask :: Word -> Word-#if MIN_VERSION_base(4,8,0) highestBitMask w = shiftLL 1 (wordSize - 1 - countLeadingZeros w)-#else-highestBitMask x1 = let x2 = x1 .|. x1 `shiftRL` 1-                        x3 = x2 .|. x2 `shiftRL` 2-                        x4 = x3 .|. x3 `shiftRL` 4-                        x5 = x4 .|. x4 `shiftRL` 8-                        x6 = x5 .|. x5 `shiftRL` 16-#if !(defined(__GLASGOW_HASKELL__) && WORD_SIZE_IN_BITS==32)-                        x7 = x6 .|. x6 `shiftRL` 32-                     in x7 `xor` (x7 `shiftRL` 1)-#else-                     in x6 `xor` (x6 `shiftRL` 1)-#endif-#endif {-# INLINE highestBitMask #-}  -- Right and left logical shifts.@@ -102,8 +75,4 @@  {-# INLINE wordSize #-} wordSize :: Int-#if MIN_VERSION_base(4,7,0) wordSize = finiteBitSize (0 :: Word)-#else-wordSize = bitSize (0 :: Word)-#endif

@@ -5,12 +5,12 @@  module Utils.Containers.Internal.Coercions where -#if __GLASGOW_HASKELL__ >= 708+#ifdef __GLASGOW_HASKELL__ import Data.Coerce #endif  infixl 8 .#-#if __GLASGOW_HASKELL__ >= 708+#ifdef __GLASGOW_HASKELL__ (.#) :: Coercible b a => (b -> c) -> (a -> b) -> a -> c (.#) f _ = coerce f #else@@ -34,7 +34,7 @@ -- @ --   foldl f b . fmap g = foldl (f .^# g) b -- @-#if __GLASGOW_HASKELL__ >= 708+#ifdef __GLASGOW_HASKELL__ (.^#) :: Coercible c b => (a -> c -> d) -> (b -> c) -> (a -> b -> d) (.^#) f _ = coerce f #else

@@ -11,12 +11,8 @@ #ifdef __GLASGOW_HASKELL__ import GHC.Exts ( reallyUnsafePtrEquality# ) import Unsafe.Coerce ( unsafeCoerce )-#if __GLASGOW_HASKELL__ < 707-import GHC.Exts ( (==#) )-#else import GHC.Exts ( Int#, isTrue# ) #endif-#endif  -- | Checks if two pointers are equal. Yes means yes; -- no means maybe. The values should be forced to at least@@ -30,13 +26,8 @@ hetPtrEq :: a -> b -> Bool  #ifdef __GLASGOW_HASKELL__-#if __GLASGOW_HASKELL__ < 707-ptrEq x y = reallyUnsafePtrEquality# x y ==# 1#-hetPtrEq x y = unsafeCoerce reallyUnsafePtrEquality# x y ==# 1#-#else ptrEq x y = isTrue# (reallyUnsafePtrEquality# x y) hetPtrEq x y = isTrue# (unsafeCoerce (reallyUnsafePtrEquality# :: x -> x -> Int#) x y)-#endif  #else -- Not GHC

@@ -5,13 +5,7 @@ -- | A clone of Control.Monad.State.Strict. module Utils.Containers.Internal.State where -import Prelude hiding (-#if MIN_VERSION_base(4,8,0)-    Applicative-#endif-    )--import Control.Monad (ap)+import Control.Monad (ap, liftM2) import Control.Applicative (Applicative(..), liftA)  newtype State s a = State {runState :: s -> (s, a)}@@ -30,6 +24,11 @@     {-# INLINE pure #-}     pure x = State $ \ s -> (s, x)     (<*>) = ap+    m *> n = State $ \s -> case runState m s of+      (s', _) -> runState n s'+#if MIN_VERSION_base(4,10,0)+    liftA2 = liftM2+#endif  execState :: State s a -> s -> a execState m x = snd (runState m x)

@@ -7,11 +7,6 @@  module Utils.Containers.Internal.StrictMaybe (MaybeS (..), maybeS, toMaybe, toMaybeS) where -#if !MIN_VERSION_base(4,8,0)-import Data.Foldable (Foldable (..))-import Data.Monoid (Monoid (..))-#endif- data MaybeS a = NothingS | JustS !a  instance Foldable MaybeS where

@@ -2,23 +2,17 @@      KindSignatures, TypeFamilies, CPP #-}  #if !defined(TESTING)-# if __GLASGOW_HASKELL__ >= 710 {-# LANGUAGE Safe #-}-# else-{-# LANGUAGE Trustworthy #-} #endif-#endif  -- | Unsatisfiable constraints for functions being removed.  module Utils.Containers.Internal.TypeError where import GHC.TypeLits --- | The constraint @Whoops s@ is unsatisfiable for every 'Symbol' @s@.--- Under GHC 8.0 and above, trying to use a function with a @Whoops s@--- constraint will lead to a pretty type error explaining how to fix--- the problem. Under earlier GHC versions, it will produce an extremely--- ugly type error within which the desired message is buried.+-- | The constraint @Whoops s@ is unsatisfiable for every 'Symbol' @s@.  Trying+-- to use a function with a @Whoops s@ constraint will lead to a pretty type+-- error explaining how to fix the problem. -- -- ==== Example --@@ -28,9 +22,7 @@ -- @ class Whoops (a :: Symbol) -#if __GLASGOW_HASKELL__ >= 800 instance TypeError ('Text a) => Whoops a-#endif  -- Why don't we just use --