packages feed

containers 0.5.1.0 → 0.5.2.0

raw patch · 12 files changed

+508/−136 lines, 12 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

+ Data.Sequence: instance Alternative Seq
+ Data.Sequence: instance Applicative Seq
+ Data.Set: deleteAt :: Int -> Set a -> Set a
+ Data.Set: elemAt :: Int -> Set a -> a
+ Data.Set: findIndex :: Ord a => a -> Set a -> Int
+ Data.Set: lookupIndex :: Ord a => a -> Set a -> Maybe Int
- Data.Set: map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b
+ Data.Set: map :: Ord b => (a -> b) -> Set a -> Set b

Files

Data/IntMap.hs view
@@ -15,8 +15,12 @@ -- An efficient implementation of maps from integer keys to values -- (dictionaries). ----- This module re-exports the value lazy 'Data.IntMap.Lazy' API, plus--- several value strict functions from 'Data.IntMap.Strict'.+-- This module re-exports the value lazy "Data.IntMap.Lazy" API, plus+-- several deprecated value strict functions. Please note that these functions+-- have different strictness properties than those in "Data.IntMap.Strict":+-- they only evaluate the result of the combining function. For example, the+-- default value to 'insertWith'' is only evaluated if the combining function+-- is called and uses it. -- -- These modules are intended to be imported qualified, to avoid name -- clashes with Prelude functions, e.g.@@ -55,26 +59,44 @@     ) where  import Prelude hiding (lookup,map,filter,foldr,foldl,null)+import Data.IntMap.Base (IntMap(..), join, nomatch, zero) import Data.IntMap.Lazy-import qualified Data.IntMap.Strict as S --- | /Deprecated./ As of version 0.5, replaced by 'S.insertWith'.+-- | /Deprecated./ As of version 0.5, replaced by+-- 'Data.IntMap.Strict.insertWith'. ----- /O(log n)/. Same as 'insertWith', but the combining function is--- applied strictly.  This function is deprecated, use 'insertWith' in--- "Data.IntMap.Strict" instead.+-- /O(log n)/. Same as 'insertWith', but the result of the combining function+-- is evaluated to WHNF before inserted to the map. In contrast to+-- 'Data.IntMap.Strict.insertWith', the value argument is not evaluted when not+-- needed by the combining function.+ insertWith' :: (a -> a -> a) -> Key -> a -> IntMap a -> IntMap a-insertWith' = S.insertWith-{-# INLINE insertWith' #-}+-- We do not reuse Data.IntMap.Strict.insertWith, because it is stricter -- it+-- forces evaluation of the given value.+insertWith' f k x t+  = insertWithKey' (\_ x' y' -> f x' y') k x t --- | /Deprecated./ As of version 0.5, replaced by 'S.insertWithKey'.+-- | /Deprecated./ As of version 0.5, replaced by+-- 'Data.IntMap.Strict.insertWithKey'. ----- /O(log n)/. Same as 'insertWithKey', but the combining function is--- applied strictly.  This function is deprecated, use 'insertWithKey'--- in "Data.IntMap.Strict" instead.+-- /O(log n)/. Same as 'insertWithKey', but the result of the combining+-- function is evaluated to WHNF before inserted to the map. In contrast to+-- 'Data.IntMap.Strict.insertWithKey', the value argument is not evaluted when+-- not needed by the combining function.+ insertWithKey' :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> IntMap a-insertWithKey' = S.insertWithKey-{-# INLINE insertWithKey' #-}+-- We do not reuse Data.IntMap.Strict.insertWithKey, because it is stricter -- it+-- forces evaluation of the given value.+insertWithKey' f k x t = k `seq`+  case t of+    Bin p m l r+      | nomatch k p m -> join k (Tip k x) p t+      | zero k m      -> Bin p m (insertWithKey' f k x l) r+      | otherwise     -> Bin p m l (insertWithKey' f k x r)+    Tip ky y+      | k==ky         -> Tip k $! f k x y+      | otherwise     -> join k (Tip k x) ky t+    Nil -> Tip k x  -- | /Deprecated./ As of version 0.5, replaced by 'foldr'. --
Data/IntMap/Base.hs view
@@ -227,7 +227,7 @@  #if __GLASGOW_HASKELL__ import Text.Read-import Data.Data (Data(..), mkNoRepType)+import Data.Data (Data(..), Constr, mkConstr, constrIndex, Fixity(Prefix), DataType, mkDataType) #endif  #if __GLASGOW_HASKELL__@@ -342,15 +342,23 @@ --------------------------------------------------------------------}  -- This instance preserves data abstraction at the cost of inefficiency.--- We omit reflection services for the sake of data abstraction.+-- We provide limited reflection services for the sake of data abstraction.  instance Data a => Data (IntMap a) where   gfoldl f z im = z fromList `f` (toList im)-  toConstr _    = error "toConstr"-  gunfold _ _   = error "gunfold"-  dataTypeOf _  = mkNoRepType "Data.IntMap.IntMap"-  dataCast1 f   = gcast1 f+  toConstr _     = fromListConstr+  gunfold k z c  = case constrIndex c of+    1 -> k (z fromList)+    _ -> error "gunfold"+  dataTypeOf _   = intMapDataType+  dataCast1 f    = gcast1 f +fromListConstr :: Constr+fromListConstr = mkConstr intMapDataType "fromList" [] Prefix++intMapDataType :: DataType+intMapDataType = mkDataType "Data.IntMap.Base.IntMap" [fromListConstr]+ #endif  {--------------------------------------------------------------------@@ -1125,13 +1133,17 @@           go (Bin _ _ _ r') = go r'           go Nil            = error "findMax Nil" --- | /O(min(n,W))/. Delete the minimal key. An error is thrown if the IntMap is already empty.--- Note, this is not the same behavior Map.+-- | /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' –+-- 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. An error is thrown if the IntMap is already empty.--- Note, this is not the same behavior Map.+-- | /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' –+-- versions prior to 0.5 threw an error if the 'IntMap' was already empty. deleteMax :: IntMap a -> IntMap a deleteMax = maybe Nil snd . maxView @@ -2055,59 +2067,23 @@   = intFromNat (highestBitMask (natFromInt p1 `xor` natFromInt p2)) {-# INLINE branchMask #-} -{-----------------------------------------------------------------------  Finding the highest bit (mask) in a word [x] can be done efficiently in-  three ways:-  * convert to a floating point value and the mantissa tells us the-    [log2(x)] that corresponds with the highest bit position. The mantissa-    is retrieved either via the standard C function [frexp] or by some bit-    twiddling on IEEE compatible numbers (float). Note that one needs to-    use at least [double] precision for an accurate mantissa of 32 bit-    numbers.-  * use bit twiddling, a logarithmic sequence of bitwise or's and shifts (bit).-  * use processor specific assembler instruction (asm).--  The most portable way would be [bit], but is it efficient enough?-  I have measured the cycle counts of the different methods on an AMD-  Athlon-XP 1800 (~ Pentium III 1.8Ghz) using the RDTSC instruction:--  highestBitMask: method  cycles-                  ---------------                   frexp   200-                   float    33-                   bit      11-                   asm      12--  highestBit:     method  cycles-                  ---------------                   frexp   195-                   float    33-                   bit      11-                   asm      11--  Wow, the bit twiddling is on today's RISC like machines even faster-  than a single CISC instruction (BSR)!-----------------------------------------------------------------------}+-- The highestBitMask implementation is based on+-- http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2+-- which has been put in the public domain. -{-----------------------------------------------------------------------  [highestBitMask] returns a word where only the highest bit is set.-  It is found by first setting all bits in lower positions than the-  highest bit and than taking an exclusive or with the original value.-  Allthough the function may look expensive, GHC compiles this into-  excellent C code that subsequently compiled into highly efficient-  machine code. The algorithm is derived from Jorg Arndt's FXT library.-----------------------------------------------------------------------}+-- | Return a word where only the highest bit is set. highestBitMask :: Nat -> Nat-highestBitMask x0-  = case (x0 .|. shiftRL x0 1) of-     x1 -> case (x1 .|. shiftRL x1 2) of-      x2 -> case (x2 .|. shiftRL x2 4) of-       x3 -> case (x3 .|. shiftRL x3 8) of-        x4 -> case (x4 .|. shiftRL x4 16) of+highestBitMask x1 = let x2 = x1 .|. x1 `shiftR` 1+                        x3 = x2 .|. x2 `shiftR` 2+                        x4 = x3 .|. x3 `shiftR` 4+                        x5 = x4 .|. x4 `shiftR` 8+                        x6 = x5 .|. x5 `shiftR` 16 #if !(defined(__GLASGOW_HASKELL__) && WORD_SIZE_IN_BITS==32)-         x5 -> case (x5 .|. shiftRL x5 32) of   -- for 64 bit platforms+                        x7 = x6 .|. x6 `shiftR` 32+                     in x7 `xor` (x7 `shiftR` 1)+#else+                     in x6 `xor` (x6 `shiftR` 1) #endif-          x6 -> (x6 `xor` (shiftRL x6 1)) {-# INLINE highestBitMask #-}
Data/IntSet/Base.hs view
@@ -172,7 +172,7 @@  #if __GLASGOW_HASKELL__ import Text.Read-import Data.Data (Data(..), mkNoRepType)+import Data.Data (Data(..), Constr, mkConstr, constrIndex, Fixity(Prefix), DataType, mkDataType) #endif  #if __GLASGOW_HASKELL__@@ -274,14 +274,22 @@ --------------------------------------------------------------------}  -- This instance preserves data abstraction at the cost of inefficiency.--- We omit reflection services for the sake of data abstraction.+-- We provide limited reflection services for the sake of data abstraction.  instance Data IntSet where   gfoldl f z is = z fromList `f` (toList is)-  toConstr _    = error "toConstr"-  gunfold _ _   = error "gunfold"-  dataTypeOf _  = mkNoRepType "Data.IntSet.IntSet"+  toConstr _     = fromListConstr+  gunfold k z c  = case constrIndex c of+    1 -> k (z fromList)+    _ -> error "gunfold"+  dataTypeOf _   = intSetDataType +fromListConstr :: Constr+fromListConstr = mkConstr intSetDataType "fromList" [] Prefix++intSetDataType :: DataType+intSetDataType = mkDataType "Data.IntSet.Base.IntSet" [fromListConstr]+ #endif  {--------------------------------------------------------------------@@ -808,11 +816,17 @@           find Nil            = error "findMax Nil"  --- | /O(min(n,W))/. Delete the minimal element.+-- | /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' –+-- 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.+-- | /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' –+-- versions prior to 0.5 threw an error if the 'IntSet' was already empty. deleteMax :: IntSet -> IntSet deleteMax = maybe Nil snd . maxView @@ -1496,8 +1510,21 @@     by Peter Wegner in CACM 3 (1960), 322. (Also discovered independently by     Derrick Lehmer and published in 1964 in a book edited by Beckenbach.)" ----------------------------------------------------------------------}-bitcount :: Int -> Word -> Int++-- We want to be able to compile without cabal. Nevertheless+-- #if defined(MIN_VERSION_base) && MIN_VERSION_base(4,5,0)+-- does not work, because if MIN_VERSION_base is undefined,+-- the last condition is syntactically wrong.+#define MIN_VERSION_base_4_5_0 0+#ifdef MIN_VERSION_base #if MIN_VERSION_base(4,5,0)+#undef MIN_VERSION_base_4_5_0+#define MIN_VERSION_base_4_5_0 1+#endif+#endif++bitcount :: Int -> Word -> Int+#if MIN_VERSION_base_4_5_0 bitcount a x = a + popCount x #else bitcount a0 x0 = go a0 x0
Data/Map.hs view
@@ -15,8 +15,13 @@ -- An efficient implementation of ordered maps from keys to values -- (dictionaries). ----- This module re-exports the value lazy 'Data.Map.Lazy' API, plus--- several value strict functions from 'Data.Map.Strict'.+-- This module re-exports the value lazy "Data.Map.Lazy" API, plus+-- several deprecated value strict functions. Please note that these functions+-- have different strictness properties than those in "Data.Map.Strict":+-- they only evaluate the values inserted into the map. For example, the+-- default value to 'insertWith'' is only evaluated if it's used, i.e. because+-- there's no value for the key already or because the higher-order argument+-- that combines the old and new value uses it. -- -- These modules are intended to be imported qualified, to avoid name -- clashes with Prelude functions, e.g.@@ -51,50 +56,103 @@     , foldWithKey     ) where +import Prelude hiding (foldr)+import Data.Map.Base (Map(..), balanceL, balanceR) import Data.Map.Lazy-import qualified Data.Map.Lazy as L-import qualified Data.Map.Strict as S+import Data.StrictPair --- | /Deprecated./ As of version 0.5, replaced by 'S.insertWith'.+-- | /Deprecated./ As of version 0.5, replaced by 'Data.Map.Strict.insertWith'. ----- /O(log n)/. Same as 'insertWith', but the combining function is--- applied strictly.  This is often the most desirable behavior.+-- /O(log n)/. Same as 'insertWith', but the value being inserted to the map is+-- evaluated to WHNF beforehand. In contrast to 'Data.Map.Strict.insertWith',+-- the value argument is not evaluted when not needed. -- -- For example, to update a counter: -- -- > insertWith' (+) k 1 m --+ insertWith' :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a-insertWith' = S.insertWith+-- We do not reuse Data.Map.Strict.insertWith, because it is stricter -- it+-- forces evaluation of the given value. Some people depend on the original+-- behaviour, which forces only the key and the result of combining function.+-- Particularly, people use insertWith' as a strict version of adjust, which+-- requires to use undefined in the place of the value.+insertWith' f = insertWithKey' (\_ x' y' -> f x' y')+#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE insertWith' #-}+#else+{-# INLINE insertWith' #-}+#endif --- | /Deprecated./ As of version 0.5, replaced by 'S.insertWithKey'.+-- | /Deprecated./ As of version 0.5, replaced by+-- 'Data.Map.Strict.insertWithKey'. ----- /O(log n)/. Same as 'insertWithKey', but the combining function is--- applied strictly.+-- /O(log n)/. Same as 'insertWithKey', but the value being inserted to the map is+-- evaluated to WHNF beforehand. In contrast to 'Data.Map.Strict.insertWithKey',+-- the value argument is not evaluted when not needed.+ insertWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a-insertWithKey' = S.insertWithKey+-- We do not reuse Data.Map.Strict.insertWithKey, because it is stricter -- it+-- forces evaluation of the given value.+insertWithKey' = go+  where+    go :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a+    go _ kx _ _ | kx `seq` False = undefined+    go _ kx x Tip = x `seq` singleton kx x+    go f kx x (Bin sy ky y l r) =+        case compare kx ky of+            LT -> balanceL ky y (go f kx x l) r+            GT -> balanceR ky y l (go f kx x r)+            EQ -> let x' = f kx x y+                  in x' `seq` Bin sy kx x' l r+#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE insertWithKey' #-}+#else+{-# INLINE insertWithKey' #-}+#endif  -- | /Deprecated./ As of version 0.5, replaced by--- 'S.insertLookupWithKey'.+-- 'Data.Map.Strict.insertLookupWithKey'. ----- /O(log n)/. A strict version of 'insertLookupWithKey'.+-- /O(log n)/. Same as 'insertLookupWithKey', but the value being inserted to+-- the map is evaluated to WHNF beforehand. In contrast to+-- 'Data.Map.Strict.insertLookupWithKey', the value argument is not evaluted+-- when not needed.+ insertLookupWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a                      -> (Maybe a, Map k a)-insertLookupWithKey' = S.insertLookupWithKey+-- We do not reuse Data.Map.Strict.insertLookupWithKey, because it is stricter -- it+-- forces evaluation of the given value.+insertLookupWithKey' f0 kx0 x0 t0 = toPair $ go f0 kx0 x0 t0+  where+    go :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> StrictPair (Maybe a) (Map k a)+    go _ kx _ _ | kx `seq` False = undefined+    go _ kx x Tip = x `seq` Nothing :*: singleton kx x+    go f kx x (Bin sy ky y l r) =+        case compare kx ky of+            LT -> let (found :*: l') = go f kx x l+                  in found :*: balanceL ky y l' r+            GT -> let (found :*: r') = go f kx x r+                  in found :*: balanceR ky y l r'+            EQ -> let x' = f kx x y+                  in x' `seq` (Just y :*: Bin sy kx x' l r)+#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE insertLookupWithKey' #-}+#else+{-# INLINE insertLookupWithKey' #-}+#endif --- | /Deprecated./ As of version 0.5, replaced by 'L.foldr'.+-- | /Deprecated./ As of version 0.5, replaced by 'foldr'. -- -- /O(n)/. Fold the values in the map using the given right-associative -- binary operator. This function is an equivalent of 'foldr' and is present -- for compatibility only. fold :: (a -> b -> b) -> b -> Map k a -> b-fold = L.foldr+fold = foldr {-# INLINE fold #-} --- | /Deprecated./ As of version 0.4, replaced by 'L.foldrWithKey'.+-- | /Deprecated./ As of version 0.4, replaced by 'foldrWithKey'. -- -- /O(n)/. Fold the keys and values in the map using the given right-associative -- binary operator. This function is an equivalent of 'foldrWithKey' and is present
Data/Map/Base.hs view
@@ -335,15 +335,23 @@ --------------------------------------------------------------------}  -- This instance preserves data abstraction at the cost of inefficiency.--- We omit reflection services for the sake of data abstraction.+-- We provide limited reflection services for the sake of data abstraction.  instance (Data k, Data a, Ord k) => Data (Map k a) where   gfoldl f z m   = z fromList `f` toList m-  toConstr _     = error "toConstr"-  gunfold _ _    = error "gunfold"-  dataTypeOf _   = mkNoRepType "Data.Map.Map"+  toConstr _     = fromListConstr+  gunfold k z c  = case constrIndex c of+    1 -> k (z fromList)+    _ -> error "gunfold"+  dataTypeOf _   = mapDataType   dataCast2 f    = gcast2 f +fromListConstr :: Constr+fromListConstr = mkConstr mapDataType "fromList" [] Prefix++mapDataType :: DataType+mapDataType = mkDataType "Data.Map.Base.Map" [fromListConstr]+ #endif  {--------------------------------------------------------------------@@ -912,9 +920,10 @@ {--------------------------------------------------------------------   Indexing --------------------------------------------------------------------}--- | /O(log n)/. Return the /index/ of a key. 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.+-- | /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. -- -- > findIndex 2 (fromList [(5,"a"), (3,"b")])    Error: element is not in the map -- > findIndex 3 (fromList [(5,"a"), (3,"b")]) == 0@@ -937,8 +946,9 @@ {-# INLINABLE findIndex #-} #endif --- | /O(log n)/. Lookup the /index/ of a key. The index is a number from--- /0/ up to, but not including, the 'size' of the map.+-- | /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. -- -- > isJust (lookupIndex 2 (fromList [(5,"a"), (3,"b")]))   == False -- > fromJust (lookupIndex 3 (fromList [(5,"a"), (3,"b")])) == 0@@ -961,8 +971,9 @@ {-# INLINABLE lookupIndex #-} #endif --- | /O(log n)/. Retrieve an element by /index/. Calls 'error' when an--- invalid index is used.+-- | /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. -- -- > elemAt 0 (fromList [(5,"a"), (3,"b")]) == (3,"b") -- > elemAt 1 (fromList [(5,"a"), (3,"b")]) == (5, "a")@@ -979,8 +990,9 @@   where     sizeL = size l --- | /O(log n)/. Update the element at /index/. Calls 'error' when an--- invalid index is used.+-- | /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. -- -- > updateAt (\ _ _ -> Just "x") 0    (fromList [(5,"a"), (3,"b")]) == fromList [(3, "x"), (5, "a")] -- > updateAt (\ _ _ -> Just "x") 1    (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "x")]@@ -1004,8 +1016,9 @@       where         sizeL = size l --- | /O(log n)/. Delete the element at /index/.--- Defined as (@'deleteAt' i map = 'updateAt' (\k x -> 'Nothing') i map@).+-- | /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. -- -- > deleteAt 0  (fromList [(5,"a"), (3,"b")]) == singleton 5 "a" -- > deleteAt 1  (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"@@ -1191,7 +1204,6 @@ -- It prefers @t1@ when duplicate keys are encountered, -- i.e. (@'union' == 'unionWith' 'const'@). -- The implementation uses the efficient /hedge-union/ algorithm.--- Hedge-union is more efficient on (bigset \``union`\` smallset). -- -- > union (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")] @@ -1232,7 +1244,6 @@  -- | /O(n+m)/. -- Union with a combining function. The implementation uses the efficient /hedge-union/ algorithm.--- Hedge-union is more efficient on (bigset \``union`\` smallset). -- -- > 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")]@@ -1311,6 +1322,8 @@ -- | /O(n+m)/. Intersection of two maps. -- Return data in the first map for the keys existing in both maps. -- (@'intersection' m1 m2 == 'intersectionWith' 'const' m1 m2@).+-- The implementation uses an efficient /hedge/ algorithm comparable with+-- /hedge-union/. -- -- > intersection (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "a" @@ -1333,7 +1346,8 @@ {-# INLINABLE hedgeInt #-} #endif --- | /O(n+m)/. Intersection with a combining function.+-- | /O(n+m)/. Intersection with a combining function.  The implementation uses+-- an efficient /hedge/ algorithm comparable with /hedge-union/. -- -- > intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "aA" @@ -1344,8 +1358,8 @@ {-# INLINABLE intersectionWith #-} #endif --- | /O(n+m)/. Intersection with a combining function.--- Intersection is more efficient on (bigset \``intersection`\` smallset).+-- | /O(n+m)/. Intersection with a combining function.  The implementation uses+-- an efficient /hedge/ algorithm comparable with /hedge-union/. -- -- > 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"
Data/Map/Strict.hs view
@@ -713,7 +713,6 @@  -- | /O(n+m)/. -- Union with a combining function. The implementation uses the efficient /hedge-union/ algorithm.--- Hedge-union is more efficient on (bigset \``union`\` smallset). -- -- > 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")]@@ -767,7 +766,8 @@   Intersection --------------------------------------------------------------------} --- | /O(n+m)/. Intersection with a combining function.+-- | /O(n+m)/. Intersection with a combining function.  The implementation uses+-- an efficient /hedge/ algorithm comparable with /hedge-union/. -- -- > intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "aA" @@ -778,8 +778,8 @@ {-# INLINABLE intersectionWith #-} #endif --- | /O(n+m)/. Intersection with a combining function.--- Intersection is more efficient on (bigset \``intersection`\` smallset).+-- | /O(n+m)/. Intersection with a combining function.  The implementation uses+-- an efficient /hedge/ algorithm comparable with /hedge-union/. -- -- > 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"
Data/Sequence.hs view
@@ -142,7 +142,9 @@     scanl, scanl1, scanr, scanr1, replicate, zip, zipWith, zip3, zipWith3,     takeWhile, dropWhile, iterate, reverse, filter, mapM, sum, all) import qualified Data.List-import Control.Applicative (Applicative(..), (<$>), WrappedMonad(..), liftA, liftA2, liftA3)+import Control.Applicative (Applicative(..), (<$>), Alternative,+                            WrappedMonad(..), liftA, liftA2, liftA3)+import qualified Control.Applicative as Applicative (Alternative(..)) import Control.DeepSeq (NFData(rnf)) import Control.Monad (MonadPlus(..), ap) import Data.Monoid (Monoid(..))@@ -198,9 +200,18 @@     xs >>= f = foldl' add empty xs       where add ys x = ys >< f x +instance Applicative Seq where+    pure = singleton+    fs <*> xs = foldl' add empty fs+      where add ys f = ys >< fmap f xs+ instance MonadPlus Seq where     mzero = empty     mplus = (><)++instance Alternative Seq where+    empty = empty+    (<|>) = (><)  instance Eq a => Eq (Seq a) where     xs == ys = length xs == length ys && toList xs == toList ys
Data/Set.hs view
@@ -81,6 +81,12 @@             , split             , splitMember +            -- * Indexed+            , lookupIndex+            , findIndex+            , elemAt+            , deleteAt+             -- * Map             , S.map             , mapMonotonic
Data/Set/Base.hs view
@@ -127,6 +127,12 @@             , split             , splitMember +            -- * Indexed+            , lookupIndex+            , findIndex+            , elemAt+            , deleteAt+             -- * Map             , map             , mapMonotonic@@ -197,6 +203,7 @@ -- want the compilers to be compiled by as many compilers as possible. #define STRICT_1_OF_2(fn) fn arg _ | arg `seq` False = undefined #define STRICT_1_OF_3(fn) fn arg _ _ | arg `seq` False = undefined+#define STRICT_2_OF_3(fn) fn _ arg _ | arg `seq` False = undefined  {--------------------------------------------------------------------   Operators@@ -241,15 +248,23 @@ --------------------------------------------------------------------}  -- This instance preserves data abstraction at the cost of inefficiency.--- We omit reflection services for the sake of data abstraction.+-- We provide limited reflection services for the sake of data abstraction.  instance (Data a, Ord a) => Data (Set a) where   gfoldl f z set = z fromList `f` (toList set)-  toConstr _     = error "toConstr"-  gunfold _ _    = error "gunfold"-  dataTypeOf _   = mkNoRepType "Data.Set.Set"+  toConstr _     = fromListConstr+  gunfold k z c  = case constrIndex c of+    1 -> k (z fromList)+    _ -> error "gunfold"+  dataTypeOf _   = setDataType   dataCast1 f    = gcast1 f +fromListConstr :: Constr+fromListConstr = mkConstr setDataType "fromList" [] Prefix++setDataType :: DataType+setDataType = mkDataType "Data.Set.Base.Set" [fromListConstr]+ #endif  {--------------------------------------------------------------------@@ -510,13 +525,13 @@ findMax (Bin _ _ _ r)    = findMax r findMax Tip              = error "Set.findMax: empty set has no maximal element" --- | /O(log n)/. Delete the minimal element.+-- | /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.+-- | /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)@@ -535,7 +550,6 @@ -- | /O(n+m)/. The union of two sets, preferring the first set when -- equal elements are encountered. -- The implementation uses the efficient /hedge-union/ algorithm.--- Hedge-union is more efficient on (bigset `union` smallset). union :: Ord a => Set a -> Set a -> Set a union Tip t2  = t2 union t1 Tip  = t1@@ -582,8 +596,9 @@ {--------------------------------------------------------------------   Intersection --------------------------------------------------------------------}--- | /O(n+m)/. The intersection of two sets.--- Elements of the result come from the first set, so for example+-- | /O(n+m)/. The intersection of two sets.  The implementation uses an+-- efficient /hedge/ algorithm comparable with /hedge-union/.  Elements of the+-- result come from the first set, so for example -- -- > import qualified Data.Set as S -- > data AB = A | B deriving Show@@ -644,7 +659,7 @@ -- It's worth noting that the size of the result may be smaller if, -- for some @(x,y)@, @x \/= y && f x == f y@ -map :: (Ord a, Ord b) => (a->b) -> Set a -> Set b+map :: Ord b => (a->b) -> Set a -> Set b map f = fromList . List.map f . toList #if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE map #-}@@ -1032,6 +1047,101 @@ #if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE splitMember #-} #endif++{--------------------------------------------------------------------+  Indexing+--------------------------------------------------------------------}++-- | /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.+--+-- > findIndex 2 (fromList [5,3])    Error: element is not in the set+-- > findIndex 3 (fromList [5,3]) == 0+-- > findIndex 5 (fromList [5,3]) == 1+-- > findIndex 6 (fromList [5,3])    Error: element is not in the set++-- See Note: Type of local 'go' function+findIndex :: Ord a => a -> Set a -> Int+findIndex = go 0+  where+    go :: Ord a => Int -> a -> Set a -> Int+    STRICT_1_OF_3(go)+    STRICT_2_OF_3(go)+    go _   _ Tip  = error "Set.findIndex: element is not in the set"+    go idx x (Bin _ kx l r) = case compare x kx of+      LT -> go idx x l+      GT -> go (idx + size l + 1) x r+      EQ -> idx + size l+#if __GLASGOW_HASKELL__ >= 700+{-# INLINABLE findIndex #-}+#endif++-- | /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.+--+-- > isJust   (lookupIndex 2 (fromList [5,3])) == False+-- > fromJust (lookupIndex 3 (fromList [5,3])) == 0+-- > fromJust (lookupIndex 5 (fromList [5,3])) == 1+-- > isJust   (lookupIndex 6 (fromList [5,3])) == False++-- See Note: Type of local 'go' function+lookupIndex :: Ord a => a -> Set a -> Maybe Int+lookupIndex = go 0+  where+    go :: Ord a => Int -> a -> Set a -> Maybe Int+    STRICT_1_OF_3(go)+    STRICT_2_OF_3(go)+    go _   _ Tip  = Nothing+    go idx x (Bin _ kx l r) = case compare x kx of+      LT -> go idx x l+      GT -> go (idx + size l + 1) x r+      EQ -> Just $! idx + size l+#if __GLASGOW_HASKELL__ >= 700+{-# INLINABLE lookupIndex #-}+#endif++-- | /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.+--+-- > elemAt 0 (fromList [5,3]) == 3+-- > elemAt 1 (fromList [5,3]) == 5+-- > elemAt 2 (fromList [5,3])    Error: index out of range++elemAt :: Int -> Set a -> a+STRICT_1_OF_2(elemAt)+elemAt _ Tip = error "Set.elemAt: index out of range"+elemAt i (Bin _ x l r)+  = case compare i sizeL of+      LT -> elemAt i l+      GT -> elemAt (i-sizeL-1) r+      EQ -> x+  where+    sizeL = size l++-- | /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.+--+-- > deleteAt 0    (fromList [5,3]) == singleton 5+-- > deleteAt 1    (fromList [5,3]) == singleton 3+-- > deleteAt 2    (fromList [5,3])    Error: index out of range+-- > deleteAt (-1) (fromList [5,3])    Error: index out of range++deleteAt :: Int -> Set a -> Set a+deleteAt i t = i `seq`+  case t of+    Tip -> error "Set.deleteAt: index out of range"+    Bin _ x l r -> case compare i sizeL of+      LT -> balanceR x (deleteAt i l) r+      GT -> balanceL x l (deleteAt (i-sizeL-1) r)+      EQ -> glue l r+      where+        sizeL = size l+  {--------------------------------------------------------------------   Utility functions that maintain the balance properties of the tree.
containers.cabal view
@@ -1,5 +1,5 @@ name: containers-version: 0.5.1.0+version: 0.5.2.0 license: BSD3 license-file: LICENSE maintainer: fox@ucw.cz@@ -175,6 +175,21 @@         QuickCheck,         test-framework,         test-framework-hunit,+        test-framework-quickcheck2++Test-suite deprecated-properties+    hs-source-dirs: tests, .+    main-is: deprecated-properties.hs+    type: exitcode-stdio-1.0+    cpp-options: -DTESTING++    build-depends: base >= 4.2 && < 5, array, deepseq >= 1.2 && < 1.4, ghc-prim+    ghc-options: -O2+    extensions: MagicHash, DeriveDataTypeable, StandaloneDeriving, Rank2Types++    build-depends:+        QuickCheck,+        test-framework,         test-framework-quickcheck2  Test-suite seq-properties
+ tests/deprecated-properties.hs view
@@ -0,0 +1,102 @@+{-# LANGUAGE CPP #-}++-- This module tests the deprecated properties of Data.Map and Data.IntMap,+-- because these cannot be tested in either map-properties or+-- intmap-properties, as these modules are designed to work with the .Lazy and+-- .Strict modules.++import qualified Data.Map as M+import qualified Data.Map.Strict as SM+import qualified Data.IntMap as IM+import qualified Data.IntMap.Strict as SIM++import Test.Framework+import Test.Framework.Providers.QuickCheck2+import Text.Show.Functions ()++default (Int)++main :: IO ()+main = defaultMain+         [ testProperty "Data.Map.insertWith' as Strict.insertWith" prop_mapInsertWith'Strict+         , testProperty "Data.Map.insertWith' undefined value" prop_mapInsertWith'Undefined+         , testProperty "Data.Map.insertWithKey' as Strict.insertWithKey" prop_mapInsertWithKey'Strict+         , testProperty "Data.Map.insertWithKey' undefined value" prop_mapInsertWithKey'Undefined+         , testProperty "Data.Map.insertLookupWithKey' as Strict.insertLookupWithKey" prop_mapInsertLookupWithKey'Strict+         , testProperty "Data.Map.insertLookupWithKey' undefined value" prop_mapInsertLookupWithKey'Undefined+         , testProperty "Data.IntMap.insertWith' as Strict.insertWith" prop_intmapInsertWith'Strict+         , testProperty "Data.IntMap.insertWith' undefined value" prop_intmapInsertWith'Undefined+         , testProperty "Data.IntMap.insertWithKey' as Strict.insertWithKey" prop_intmapInsertWithKey'Strict+         , testProperty "Data.IntMap.insertWithKey' undefined value" prop_intmapInsertWithKey'Undefined+         ]+++---------- Map properties ----------++prop_mapInsertWith'Strict :: [(Int, Int)] -> (Int -> Int -> Int) -> [(Int, Int)] -> Bool+prop_mapInsertWith'Strict xs f kxxs =+  let m = M.fromList xs+      insertList ins = foldr (\(kx, x) -> ins f kx x) m kxxs+  in insertList M.insertWith' == insertList SM.insertWith++prop_mapInsertWith'Undefined :: [(Int, Int)] -> Bool+prop_mapInsertWith'Undefined xs =+  let m = M.fromList xs+      f _ x = x * 33+      insertList ins = foldr (\(kx, _) -> ins f kx undefined) m xs+  in insertList M.insertWith' == insertList M.insertWith++prop_mapInsertWithKey'Strict :: [(Int, Int)] -> (Int -> Int -> Int -> Int) -> [(Int, Int)] -> Bool+prop_mapInsertWithKey'Strict xs f kxxs =+  let m = M.fromList xs+      insertList ins = foldr (\(kx, x) -> ins f kx x) m kxxs+  in insertList M.insertWithKey' == insertList SM.insertWithKey++prop_mapInsertWithKey'Undefined :: [(Int, Int)] -> Bool+prop_mapInsertWithKey'Undefined xs =+  let m = M.fromList xs+      f k _ x = (k + x) * 33+      insertList ins = foldr (\(kx, _) -> ins f kx undefined) m xs+  in insertList M.insertWithKey' == insertList M.insertWithKey++prop_mapInsertLookupWithKey'Strict :: [(Int, Int)] -> (Int -> Int -> Int -> Int) -> [(Int, Int)] -> Bool+prop_mapInsertLookupWithKey'Strict xs f kxxs =+  let m = M.fromList xs+      insertLookupList insLkp = scanr (\(kx, x) (_, mp) -> insLkp f kx x mp) (Nothing, m) kxxs+  in insertLookupList M.insertLookupWithKey' == insertLookupList SM.insertLookupWithKey++prop_mapInsertLookupWithKey'Undefined :: [(Int, Int)] -> Bool+prop_mapInsertLookupWithKey'Undefined xs =+  let m = M.fromList xs+      f k _ x = (k + x) * 33+      insertLookupList insLkp = scanr (\(kx, _) (_, mp) -> insLkp f kx undefined mp) (Nothing, m) xs+  in insertLookupList M.insertLookupWithKey' == insertLookupList M.insertLookupWithKey+++---------- IntMap properties ----------++prop_intmapInsertWith'Strict :: [(Int, Int)] -> (Int -> Int -> Int) -> [(Int, Int)] -> Bool+prop_intmapInsertWith'Strict xs f kxxs =+  let m = IM.fromList xs+      insertList ins = foldr (\(kx, x) -> ins f kx x) m kxxs+  in insertList IM.insertWith' == insertList SIM.insertWith++prop_intmapInsertWith'Undefined :: [(Int, Int)] -> Bool+prop_intmapInsertWith'Undefined xs =+  let m = IM.fromList xs+      f _ x = x * 33+      insertList ins = foldr (\(kx, _) -> ins f kx undefined) m xs+  in insertList IM.insertWith' == insertList IM.insertWith++prop_intmapInsertWithKey'Strict :: [(Int, Int)] -> (Int -> Int -> Int -> Int) -> [(Int, Int)] -> Bool+prop_intmapInsertWithKey'Strict xs f kxxs =+  let m = IM.fromList xs+      insertList ins = foldr (\(kx, x) -> ins f kx x) m kxxs+  in insertList IM.insertWithKey' == insertList SIM.insertWithKey++prop_intmapInsertWithKey'Undefined :: [(Int, Int)] -> Bool+prop_intmapInsertWithKey'Undefined xs =+  let m = IM.fromList xs+      f k _ x = (k + x) * 33+      insertList ins = foldr (\(kx, _) -> ins f kx undefined) m xs+  in insertList IM.insertWithKey' == insertList IM.insertWithKey
tests/set-properties.hs view
@@ -2,6 +2,7 @@ import Data.List (nub,sort) import qualified Data.List as List import Data.Monoid (mempty)+import Data.Maybe import Data.Set import Prelude hiding (lookup, null, map, filter, foldr, foldl) import Test.Framework@@ -15,6 +16,10 @@                    , testCase "lookupGT" test_lookupGT                    , testCase "lookupLE" test_lookupLE                    , testCase "lookupGE" test_lookupGE+                   , testCase "lookupIndex" test_lookupIndex+                   , testCase "findIndex" test_findIndex+                   , testCase "elemAt" test_elemAt+                   , testCase "deleteAt" test_deleteAt                    , testProperty "prop_Valid" prop_Valid                    , testProperty "prop_Single" prop_Single                    , testProperty "prop_Member" prop_Member@@ -88,6 +93,32 @@    lookupGE 3 (fromList [3, 5]) @?= Just 3    lookupGE 4 (fromList [3, 5]) @?= Just 5    lookupGE 6 (fromList [3, 5]) @?= Nothing++{--------------------------------------------------------------------+  Indexed+--------------------------------------------------------------------}++test_lookupIndex :: Assertion+test_lookupIndex = do+    isJust   (lookupIndex 2 (fromList [5,3])) @?= False+    fromJust (lookupIndex 3 (fromList [5,3])) @?= 0+    fromJust (lookupIndex 5 (fromList [5,3])) @?= 1+    isJust   (lookupIndex 6 (fromList [5,3])) @?= False++test_findIndex :: Assertion+test_findIndex = do+    findIndex 3 (fromList [5,3]) @?= 0+    findIndex 5 (fromList [5,3]) @?= 1++test_elemAt :: Assertion+test_elemAt = do+    elemAt 0 (fromList [5,3]) @?= 3+    elemAt 1 (fromList [5,3]) @?= 5++test_deleteAt :: Assertion+test_deleteAt = do+    deleteAt 0 (fromList [5,3]) @?= singleton 5+    deleteAt 1 (fromList [5,3]) @?= singleton 3  {--------------------------------------------------------------------   Arbitrary, reasonably balanced trees