containers 0.4.1.0 → 0.4.2.0

raw patch · 8 files changed

+500/−106 lines, 8 filesdep +deepseqdep ~basenew-uploaderPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependencies added: deepseq

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• Data/Graph.hs +3/−0
• Data/IntMap.hs +192/−41
• Data/IntSet.hs +99/−14
• Data/Map.hs +120/−39
• Data/Sequence.hs +3/−1
• Data/Set.hs +73/−8
• Data/Tree.hs +7/−0
• containers.cabal +3/−3

@@ -1,3 +1,6 @@+#if __GLASGOW_HASKELL__ >= 703+{-# LANGUAGE Trustworthy #-}+#endif ----------------------------------------------------------------------------- -- | -- Module      :  Data.Graph

@@ -1,4 +1,7 @@-{-# LANGUAGE CPP, NoBangPatterns, MagicHash, ScopedTypeVariables #-}+{-# LANGUAGE NoBangPatterns, ScopedTypeVariables #-}+#if !defined(TESTING) && __GLASGOW_HASKELL__ >= 703+{-# LANGUAGE Trustworthy #-}+#endif ----------------------------------------------------------------------------- -- | -- Module      :  Data.IntMap@@ -111,7 +114,17 @@             , mapAccumWithKey             , mapAccumRWithKey -            -- ** Fold+            -- * Folds+            , foldr+            , foldl+            , foldrWithKey+            , foldlWithKey+            -- ** Strict folds+            , foldr'+            , foldl'+            , foldrWithKey'+            , foldlWithKey'+            -- ** Legacy folds             , fold             , foldWithKey @@ -179,10 +192,11 @@ import Data.Monoid (Monoid(..)) import Data.Maybe (fromMaybe) import Data.Typeable-import Data.Foldable (Foldable(foldMap))+import qualified Data.Foldable as Foldable import Data.Traversable (Traversable(traverse)) import Control.Applicative (Applicative(pure,(<*>)),(<$>)) import Control.Monad ( liftM )+import Control.DeepSeq (NFData(rnf)) {- -- just for testing import qualified Prelude@@ -205,6 +219,12 @@ import Data.Word #endif +-- Use macros to define strictness of functions.+-- STRICT_x_OF_y denotes an y-ary function strict in the x-th parameter.+-- We do not use BangPatterns, because they are not in any standard and we+-- want the compilers to be compiled by as many compilers as possible.+#define STRICT_1_OF_2(fn) fn arg _ | arg `seq` False = undefined+ infixl 9 \\{-This comment teaches CPP correct behaviour -}  -- A "Nat" is a natural machine word (an unsigned Int)@@ -250,10 +270,18 @@ {--------------------------------------------------------------------   Types   --------------------------------------------------------------------}++-- The order of constructors of IntMap matters when considering performance.+-- Currently in GHC 7.0, when type has 3 constructors, they are matched from+-- the first to the last -- the best performance is achieved when the+-- constructors are ordered by frequency.+-- On GHC 7.0, reordering constructors from Nil | Tip | Bin to Bin | Tip | Nil+-- improves the containers_benchmark by 9.5% on x86 and by 8% on x86_64.+ -- | A map of integers to values @a@.-data IntMap a = Nil+data IntMap a = Bin {-# UNPACK #-} !Prefix {-# UNPACK #-} !Mask !(IntMap a) !(IntMap a)               | Tip {-# UNPACK #-} !Key a-              | Bin {-# UNPACK #-} !Prefix {-# UNPACK #-} !Mask !(IntMap a) !(IntMap a) +              | Nil  type Prefix = Int type Mask   = Int@@ -264,16 +292,26 @@     mappend = union     mconcat = unions -instance Foldable IntMap where-    foldMap _ Nil = mempty-    foldMap f (Tip _k v) = f v-    foldMap f (Bin _ _ l r) = foldMap f l `mappend` foldMap f r+instance Foldable.Foldable IntMap where+  fold Nil = mempty+  fold (Tip _ v) = v+  fold (Bin _ _ l r) = Foldable.fold l `mappend` Foldable.fold r+  foldr = foldr+  foldl = foldl+  foldMap _ Nil = mempty+  foldMap f (Tip _k v) = f v+  foldMap f (Bin _ _ l r) = Foldable.foldMap f l `mappend` Foldable.foldMap f r  instance Traversable IntMap where     traverse _ Nil = pure Nil     traverse f (Tip k v) = Tip k <$> f v     traverse f (Bin p m l r) = Bin p m <$> traverse f l <*> traverse f r +instance NFData a => NFData (IntMap a) where+    rnf Nil = ()+    rnf (Tip _ v) = rnf v+    rnf (Bin _ _ l r) = rnf l `seq` rnf r+ #if __GLASGOW_HASKELL__  {--------------------------------------------------------------------@@ -1365,47 +1403,158 @@ {--------------------------------------------------------------------   Fold --------------------------------------------------------------------}--- | /O(n)/. Fold the values in the map, such that--- @'fold' f z == 'Prelude.foldr' f z . 'elems'@.+-- | /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.+--+-- /Please note that fold will be deprecated in the future and removed./+fold :: (a -> b -> b) -> b -> IntMap a -> b+fold = foldr+{-# INLINE fold #-}++-- | /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, ----- > elems map = fold (:) [] map+-- > elems map = foldr (:) [] map -- -- > let f a len = len + (length a)--- > fold f 0 (fromList [(5,"a"), (3,"bbb")]) == 4+-- > foldr f 0 (fromList [(5,"a"), (3,"bbb")]) == 4+foldr :: (a -> b -> b) -> b -> IntMap a -> b+foldr f z t =+  case t of Bin 0 m l r | m < 0 -> go (go z l) r -- put negative numbers before+            _                   -> go z t+  where+    go z' Nil           = z'+    go z' (Tip _ x)     = f x z'+    go z' (Bin _ _ l r) = go (go z' r) l+{-# INLINE foldr #-} -fold :: (a -> b -> b) -> b -> IntMap a -> b-fold f = foldWithKey (\_ x y -> f x y)-{-# INLINE fold #-}+-- | /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+foldr' f z t =+  case t of Bin 0 m l r | m < 0 -> go (go z l) r -- put negative numbers before+            _                   -> go z t+  where+    STRICT_1_OF_2(go)+    go z' Nil           = z'+    go z' (Tip _ x)     = f x z'+    go z' (Bin _ _ l r) = go (go z' r) l+{-# INLINE foldr' #-} --- | /O(n)/. Fold the keys and values in the map, such that--- @'foldWithKey' f z == 'Prelude.foldr' ('uncurry' f) z . 'toAscList'@.+-- | /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, ----- > keys map = foldWithKey (\k x ks -> k:ks) [] map+-- > elems = reverse . foldl (flip (:)) [] ----- > let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"--- > foldWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)"+-- > let f len a = len + (length a)+-- > foldl f 0 (fromList [(5,"a"), (3,"bbb")]) == 4+foldl :: (a -> b -> a) -> a -> IntMap b -> a+foldl f z t =+  case t of Bin 0 m l r | m < 0 -> go (go z r) l -- put negative numbers before+            _                   -> go z t+  where+    go z' Nil           = z'+    go z' (Tip _ x)     = f z' x+    go z' (Bin _ _ l r) = go (go z' l) r+{-# INLINE foldl #-} -foldWithKey :: (Key -> a -> b -> b) -> b -> IntMap a -> b-foldWithKey-  = foldr+-- | /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+foldl' f z t =+  case t of Bin 0 m l r | m < 0 -> go (go z r) l -- put negative numbers before+            _                   -> go z t+  where+    STRICT_1_OF_2(go)+    go z' Nil           = z'+    go z' (Tip _ x)     = f z' x+    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+-- binary operator. This function is an equivalent of 'foldrWithKey' and is present+-- for compatibility only.+--+-- /Please note that foldWithKey will be deprecated in the future and removed./+foldWithKey :: (Int -> a -> b -> b) -> b -> IntMap a -> b+foldWithKey = foldrWithKey {-# INLINE foldWithKey #-} -foldr :: (Key -> a -> b -> b) -> b -> IntMap a -> b-foldr f z t-  = case t of-      Bin 0 m l r | m < 0 -> go (go z l) r  -- put negative numbers before.-      Bin _ _ _ _ -> go z t-      Tip k x     -> f k x z-      Nil         -> z+-- | /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'@.+--+-- For example,+--+-- > keys map = foldrWithKey (\k x ks -> k:ks) [] map+--+-- > let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"+-- > foldrWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)"+foldrWithKey :: (Int -> a -> b -> b) -> b -> IntMap a -> b+foldrWithKey f z t =+  case t of Bin 0 m l r | m < 0 -> go (go z l) r -- put negative numbers before+            _                   -> go z t   where+    go z' Nil           = z'+    go z' (Tip kx x)    = f kx x z'     go z' (Bin _ _ l r) = go (go z' r) l-    go z' (Tip k x)     = f k x z'+{-# INLINE foldrWithKey #-}++-- | /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' :: (Int -> a -> b -> b) -> b -> IntMap a -> b+foldrWithKey' f z t =+  case t of Bin 0 m l r | m < 0 -> go (go z l) r -- put negative numbers before+            _                   -> go z t+  where+    STRICT_1_OF_2(go)     go z' Nil           = z'-{-# INLINE foldr #-}+    go z' (Tip kx x)    = f kx x z'+    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+-- binary operator, such that+-- @'foldlWithKey' f z == 'Prelude.foldl' (\\z' (kx, x) -> f z' kx x) z . 'toAscList'@.+--+-- For example,+--+-- > keys = reverse . foldlWithKey (\ks k x -> k:ks) []+--+-- > let f result k a = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"+-- > foldlWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (3:b)(5:a)"+foldlWithKey :: (a -> Int -> b -> a) -> a -> IntMap b -> a+foldlWithKey f z t =+  case t of Bin 0 m l r | m < 0 -> go (go z r) l -- put negative numbers before+            _                   -> go z t+  where+    go z' Nil           = z'+    go z' (Tip kx x)    = f z' kx x+    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+-- evaluated before using the result in the next application. This+-- function is strict in the starting value.+foldlWithKey' :: (a -> Int -> b -> a) -> a -> IntMap b -> a+foldlWithKey' f z t =+  case t of Bin 0 m l r | m < 0 -> go (go z r) l -- put negative numbers before+            _                   -> go z t+  where+    STRICT_1_OF_2(go)+    go z' Nil           = z'+    go z' (Tip kx x)    = f z' kx x+    go z' (Bin _ _ l r) = go (go z' l) r+{-# INLINE foldlWithKey' #-}+ {--------------------------------------------------------------------   List variations  --------------------------------------------------------------------}@@ -1417,7 +1566,7 @@  elems :: IntMap a -> [a] elems-  = foldWithKey (\_ x xs -> x:xs) []+  = foldr (:) []  -- | /O(n)/. Return all keys of the map in ascending order. --@@ -1426,7 +1575,7 @@  keys  :: IntMap a -> [Key] keys-  = foldWithKey (\k _ ks -> k:ks) []+  = foldrWithKey (\k _ ks -> k:ks) []  -- | /O(n*min(n,W))/. The set of all keys of the map. --@@ -1457,7 +1606,7 @@  toList :: IntMap a -> [(Key,a)] toList-  = foldWithKey (\k x xs -> (k,x):xs) []+  = foldrWithKey (\k x xs -> (k,x):xs) []  -- | /O(n)/. Convert the map to a list of key\/value pairs where the -- keys are in ascending order.@@ -1467,7 +1616,7 @@ toAscList :: IntMap a -> [(Key,a)] toAscList t      = -- NOTE: the following algorithm only works for big-endian trees-    let (pos,neg) = span (\(k,_) -> k >=0) (foldr (\k x xs -> (k,x):xs) [] t) in neg ++ pos+    let (pos,neg) = span (\(k,_) -> k >=0) (foldrWithKey (\k x xs -> (k,x):xs) [] t) in neg ++ pos  -- | /O(n*min(n,W))/. Create a map from a list of key\/value pairs. --@@ -1483,7 +1632,7 @@  -- | /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 (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"c")] == fromList [(3, "ab"), (5, "cba")] -- > fromListWith (++) [] == empty  fromListWith :: (a -> a -> a) -> [(Key,a)] -> IntMap a @@ -1492,8 +1641,9 @@  -- | /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+-- > 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")]+-- > fromListWithKey f [] == empty  fromListWithKey :: (Key -> a -> a -> a) -> [(Key,a)] -> IntMap a  fromListWithKey f xs @@ -1525,7 +1675,8 @@ -- the keys are in ascending order, with a combining function on equal keys. -- /The precondition (input list is ascending) is not checked./ ----- > fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")]+-- > let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value+-- > fromAscListWithKey f [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "5:b|a")]  fromAscListWithKey :: (Key -> a -> a -> a) -> [(Key,a)] -> IntMap a fromAscListWithKey _ []         = Nil

@@ -1,4 +1,6 @@-{-# LANGUAGE CPP, MagicHash #-}+#if !defined(TESTING) && __GLASGOW_HASKELL__ >= 703+{-# LANGUAGE Trustworthy #-}+#endif ----------------------------------------------------------------------------- -- | -- Module      :  Data.IntSet@@ -81,7 +83,13 @@             -- * Map             , map -            -- * Fold+            -- * Folds+            , foldr+            , foldl+            -- ** Strict folds+            , foldr'+            , foldl'+            -- ** Legacy folds             , fold              -- * Min\/Max@@ -124,6 +132,7 @@ import Data.Monoid (Monoid(..)) import Data.Maybe (fromMaybe) import Data.Typeable+import Control.DeepSeq (NFData)  #if __GLASGOW_HASKELL__ import Text.Read@@ -139,6 +148,12 @@ import Data.Word #endif +-- Use macros to define strictness of functions.+-- STRICT_x_OF_y denotes an y-ary function strict in the x-th parameter.+-- We do not use BangPatterns, because they are not in any standard and we+-- want the compilers to be compiled by as many compilers as possible.+#define STRICT_1_OF_2(fn) fn arg _ | arg `seq` False = undefined+ infixl 9 \\{-This comment teaches CPP correct behaviour -}  -- A "Nat" is a natural machine word (an unsigned Int)@@ -174,10 +189,18 @@ {--------------------------------------------------------------------   Types   --------------------------------------------------------------------}++-- The order of constructors of IntSet matters when considering performance.+-- Currently in GHC 7.0, when type has 3 constructors, they are matched from+-- the first to the last -- the best performance is achieved when the+-- constructors are ordered by frequency.+-- On GHC 7.0, reordering constructors from Nil | Tip | Bin to Bin | Tip | Nil+-- improves the containers_benchmark by 11% on x86 and by 9% on x86_64.+ -- | A set of integers.-data IntSet = Nil+data IntSet = Bin {-# UNPACK #-} !Prefix {-# UNPACK #-} !Mask !IntSet !IntSet             | Tip {-# UNPACK #-} !Int-            | Bin {-# UNPACK #-} !Prefix {-# UNPACK #-} !Mask !IntSet !IntSet+            | Nil -- Invariant: Nil is never found as a child of Bin. -- Invariant: The Mask is a power of 2.  It is the largest bit position at which --            two elements of the set differ.@@ -659,23 +682,76 @@ {--------------------------------------------------------------------   Fold --------------------------------------------------------------------}--- | /O(n)/. Fold over the elements of a set in an unspecified order.+-- | /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. ----- > sum set   == fold (+) 0 set--- > elems set == fold (:) [] set+-- /Please note that fold will be deprecated in the future and removed./ fold :: (Int -> b -> b) -> b -> IntSet -> b-fold f z t-  = case t of-      Bin 0 m l r | m < 0 -> go (go z l) r  -- put negative numbers before.-      Bin _ _ _ _ -> go z t-      Tip x       -> f x z-      Nil         -> z+fold = foldr+{-# INLINE fold #-}++-- | /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,+--+-- > toAscList set = foldr (:) [] set+foldr :: (Int -> b -> b) -> b -> IntSet -> b+foldr f z t =+  case t of Bin 0 m l r | m < 0 -> go (go z l) r -- put negative numbers before+            _                   -> go z t   where+    go z' Nil           = z'+    go z' (Tip x)       = f x z'     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+-- evaluated before using the result in the next application. This+-- function is strict in the starting value.+foldr' :: (Int -> b -> b) -> b -> IntSet -> b+foldr' f z t =+  case t of Bin 0 m l r | m < 0 -> go (go z l) r -- put negative numbers before+            _                   -> go z t+  where+    STRICT_1_OF_2(go)+    go z' Nil           = z'     go z' (Tip x)       = f x z'+    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+-- binary operator, such that @'foldl' f z == 'Prelude.foldl' f z . 'toAscList'@.+--+-- For example,+--+-- > toDescList set = foldl (flip (:)) [] set+foldl :: (a -> Int -> a) -> a -> IntSet -> a+foldl f z t =+  case t of Bin 0 m l r | m < 0 -> go (go z r) l -- put negative numbers before+            _                   -> go z t+  where+    STRICT_1_OF_2(go)     go z' Nil           = z'-{-# INLINE fold #-}+    go z' (Tip x)       = f z' x+    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+-- evaluated before using the result in the next application. This+-- function is strict in the starting value.+foldl' :: (a -> Int -> a) -> a -> IntSet -> a+foldl' f z t =+  case t of Bin 0 m l r | m < 0 -> go (go z r) l -- put negative numbers before+            _                   -> go z t+  where+    STRICT_1_OF_2(go)+    go z' Nil           = z'+    go z' (Tip x)       = f z' x+    go z' (Bin _ _ l r) = go (go z' l) r+{-# INLINE foldl' #-}+ {--------------------------------------------------------------------   List variations  --------------------------------------------------------------------}@@ -813,6 +889,15 @@  #include "Typeable.h" INSTANCE_TYPEABLE0(IntSet,intSetTc,"IntSet")++{--------------------------------------------------------------------+  NFData+--------------------------------------------------------------------}++-- The IntSet constructors consist only of strict fields of Ints and+-- IntSets, thus the default NFData instance which evaluates to whnf+-- should suffice+instance NFData IntSet  {--------------------------------------------------------------------   Debugging

@@ -1,4 +1,7 @@-{-# LANGUAGE CPP, NoBangPatterns #-}+{-# LANGUAGE NoBangPatterns #-}+#if !defined(TESTING) && __GLASGOW_HASKELL__ >= 703+{-# LANGUAGE Safe #-}+#endif ----------------------------------------------------------------------------- -- | -- Module      :  Data.Map@@ -122,13 +125,19 @@             , mapKeysWith             , mapKeysMonotonic -            -- ** Fold-            , fold-            , foldWithKey+            -- * Folds+            , foldr+            , foldl             , foldrWithKey-            , foldrWithKey'             , foldlWithKey+            -- ** Strict folds+            , foldr'+            , foldl'+            , foldrWithKey'             , foldlWithKey'+            -- ** Legacy folds+            , fold+            , foldWithKey              -- * Conversion             , elems@@ -206,14 +215,15 @@              ) where -import Prelude hiding (lookup,map,filter,null)+import Prelude hiding (lookup,map,filter,foldr,foldl,null) import qualified Data.Set as Set import qualified Data.List as List import Data.Monoid (Monoid(..)) import Control.Applicative (Applicative(..), (<$>)) import Data.Traversable (Traversable(traverse))-import Data.Foldable (Foldable(foldMap))+import qualified Data.Foldable as Foldable import Data.Typeable+import Control.DeepSeq (NFData(rnf))  #if __GLASGOW_HASKELL__ import Text.Read@@ -1644,68 +1654,132 @@   Folds   --------------------------------------------------------------------} --- | /O(n)/. Fold the values in the map, such that--- @'fold' f z == 'Prelude.foldr' f z . 'elems'@.+-- | /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.+--+-- /Please note that fold will be deprecated in the future and removed./+fold :: (a -> b -> b) -> b -> Map k a -> b+fold = foldr+{-# INLINE fold #-}++-- | /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, ----- > elems map = fold (:) [] map+-- > elems map = foldr (:) [] map -- -- > let f a len = len + (length a)--- > fold f 0 (fromList [(5,"a"), (3,"bbb")]) == 4-fold :: (a -> b -> b) -> b -> Map k a -> b-fold f = foldWithKey (\_ x' z' -> f x' z')-{-# INLINE fold #-}+-- > foldr f 0 (fromList [(5,"a"), (3,"bbb")]) == 4+foldr :: (a -> b -> b) -> b -> Map k a -> b+foldr f = go+  where+    go z Tip             = z+    go z (Bin _ _ x l r) = go (f x (go z r)) l+{-# INLINE foldr #-} --- | /O(n)/. Fold the keys and values in the map, such that--- @'foldWithKey' f z == 'Prelude.foldr' ('uncurry' f) z . 'toAscList'@.+-- | /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+foldr' f = go+  where+    STRICT_1_OF_2(go)+    go z Tip             = z+    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+-- binary operator, such that @'foldl' f z == 'Prelude.foldl' f z . 'elems'@.+-- -- For example, ----- > keys map = foldWithKey (\k x ks -> k:ks) [] map+-- > elems = reverse . foldl (flip (:)) [] ----- > let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"--- > foldWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)"+-- > let f len a = len + (length a)+-- > foldl f 0 (fromList [(5,"a"), (3,"bbb")]) == 4+foldl :: (a -> b -> a) -> a -> Map k b -> a+foldl f = go+  where+    go z Tip             = z+    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+-- 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+foldl' f = go+  where+    STRICT_1_OF_2(go)+    go z Tip             = z+    go z (Bin _ _ x l r) = go (f (go z l) x) r+{-# INLINE foldl' #-}++-- | /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+-- for compatibility only. ----- This is identical to 'foldrWithKey', and you should use that one instead of--- this one.  This name is kept for backward compatibility.+-- /Please note that foldWithKey will be deprecated in the future and removed./ foldWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b foldWithKey = foldrWithKey-{-# DEPRECATED foldWithKey "Use foldrWithKey instead" #-} {-# INLINE foldWithKey #-} --- | /O(n)/. Post-order fold.  The function will be applied from the lowest--- value to the highest.+-- | /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'@.+--+-- For example,+--+-- > keys map = foldrWithKey (\k x ks -> k:ks) [] map+--+-- > let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"+-- > foldrWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)" foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b foldrWithKey f = go   where-    go z Tip              = z+    go z Tip             = z     go z (Bin _ kx x l r) = go (f kx x (go z r)) l {-# INLINE foldrWithKey #-} --- | /O(n)/. A strict version of 'foldrWithKey'.+-- | /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 foldrWithKey' f = go   where+    STRICT_1_OF_2(go)     go z Tip              = z-    go z (Bin _ kx x l r) = let z' = go z r-                            in z `seq` z' `seq` go (f kx x z') l+    go z (Bin _ kx x l r) = go (f kx x (go z r)) l {-# INLINE foldrWithKey' #-} --- | /O(n)/. Pre-order fold.  The function will be applied from the highest--- value to the lowest.-foldlWithKey :: (b -> k -> a -> b) -> b -> Map k a -> b+-- | /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'@.+--+-- For example,+--+-- > keys = reverse . foldlWithKey (\ks k x -> k:ks) []+--+-- > let f result k a = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"+-- > foldlWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (3:b)(5:a)"+foldlWithKey :: (a -> k -> b -> a) -> a -> Map k b -> a foldlWithKey f = go   where     go z Tip              = z     go z (Bin _ kx x l r) = go (f (go z l) kx x) r {-# INLINE foldlWithKey #-} --- | /O(n)/. A strict version of 'foldlWithKey'.-foldlWithKey' :: (b -> k -> a -> b) -> b -> Map k a -> b+-- | /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 foldlWithKey' f = go   where+    STRICT_1_OF_2(go)     go z Tip              = z-    go z (Bin _ kx x l r) = let z' = go z l-                            in z `seq` z' `seq` go (f z' kx x) r+    go z (Bin _ kx x l r) = go (f (go z l) kx x) r {-# INLINE foldlWithKey' #-}  {--------------------------------------------------------------------@@ -2387,10 +2461,17 @@   traverse f (Bin s k v l r)     = flip (Bin s k) <$> traverse f l <*> f v <*> traverse f r -instance Foldable (Map k) where-  foldMap _f Tip = mempty-  foldMap f (Bin _s _k v l r)-    = foldMap f l `mappend` f v `mappend` foldMap f r+instance Foldable.Foldable (Map k) where+  fold Tip = mempty+  fold (Bin _ _ v l r) = Foldable.fold l `mappend` v `mappend` Foldable.fold r+  foldr = foldr+  foldl = foldl+  foldMap _ Tip = mempty+  foldMap f (Bin _ _ v l r) = Foldable.foldMap f l `mappend` f v `mappend` Foldable.foldMap f r++instance (NFData k, NFData a) => NFData (Map k a) where+    rnf Tip = ()+    rnf (Bin _ kx x l r) = rnf kx `seq` rnf x `seq` rnf l `seq` rnf r  {--------------------------------------------------------------------   Read

@@ -1,4 +1,6 @@-{-# LANGUAGE CPP, DeriveDataTypeable #-}+#if __GLASGOW_HASKELL__ >= 703+{-# LANGUAGE Trustworthy #-}+#endif ----------------------------------------------------------------------------- -- | -- Module      :  Data.Sequence

@@ -1,4 +1,6 @@-{-# LANGUAGE CPP #-}+#if !defined(TESTING) && __GLASGOW_HASKELL__ >= 703+{-# LANGUAGE Safe #-}+#endif ----------------------------------------------------------------------------- -- | -- Module      :  Data.Set@@ -90,7 +92,13 @@             , map             , mapMonotonic -            -- * Fold+            -- * Folds+            , foldr+            , foldl+            -- ** Strict folds+            , foldr'+            , foldl'+            -- ** Legacy folds             , fold              -- * Min\/Max@@ -129,11 +137,12 @@ #endif             ) where -import Prelude hiding (filter,foldr,null,map)+import Prelude hiding (filter,foldl,foldr,null,map) import qualified Data.List as List import Data.Monoid (Monoid(..))-import Data.Foldable (Foldable(foldMap))+import qualified Data.Foldable as Foldable import Data.Typeable+import Control.DeepSeq (NFData(rnf))  {- -- just for testing@@ -179,9 +188,13 @@     mappend = union     mconcat = unions -instance Foldable Set where+instance Foldable.Foldable Set where+    fold Tip = mempty+    fold (Bin _ k l r) = Foldable.fold l `mappend` k `mappend` Foldable.fold r+    foldr = foldr+    foldl = foldl     foldMap _ Tip = mempty-    foldMap f (Bin _s k l r) = foldMap f l `mappend` f k `mappend` foldMap f r+    foldMap f (Bin _ k l r) = Foldable.foldMap f l `mappend` f k `mappend` Foldable.foldMap f r  #if __GLASGOW_HASKELL__ @@ -541,12 +554,21 @@ {--------------------------------------------------------------------   Fold --------------------------------------------------------------------}--- | /O(n)/. Fold over the elements of a set in an unspecified order.+-- | /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.+--+-- /Please note that fold will be deprecated in the future and removed./ fold :: (a -> b -> b) -> b -> Set a -> b fold = foldr {-# INLINE fold #-} --- | /O(n)/. Post-order fold.+-- | /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,+--+-- > toAscList set = foldr (:) [] set foldr :: (a -> b -> b) -> b -> Set a -> b foldr f = go   where@@ -554,6 +576,41 @@     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+-- 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+foldr' f = go+  where+    STRICT_1_OF_2(go)+    go z Tip           = z+    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+-- binary operator, such that @'foldl' f z == 'Prelude.foldl' f z . 'toAscList'@.+--+-- For example,+--+-- > toDescList set = foldl (flip (:)) [] set+foldl :: (a -> b -> a) -> a -> Set b -> a+foldl f = go+  where+    go z Tip           = z+    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+-- 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+foldl' f = go+  where+    STRICT_1_OF_2(go)+    go z Tip           = z+    go z (Bin _ x l r) = go (f (go z l) x) r+{-# INLINE foldl' #-}+ {--------------------------------------------------------------------   List variations  --------------------------------------------------------------------}@@ -689,6 +746,14 @@  #include "Typeable.h" INSTANCE_TYPEABLE1(Set,setTc,"Set")++{--------------------------------------------------------------------+  NFData+--------------------------------------------------------------------}++instance NFData a => NFData (Set a) where+    rnf Tip           = ()+    rnf (Bin _ y l r) = rnf y `seq` rnf l `seq` rnf r  {--------------------------------------------------------------------   Utility functions that return sub-ranges of the original

@@ -1,3 +1,6 @@+#if __GLASGOW_HASKELL__ >= 703+{-# LANGUAGE Safe #-}+#endif ----------------------------------------------------------------------------- -- | -- Module      :  Data.Tree@@ -32,6 +35,7 @@ import Data.Foldable (Foldable(foldMap), toList) import Data.Traversable (Traversable(traverse)) import Data.Typeable+import Control.DeepSeq (NFData(rnf))  #ifdef __GLASGOW_HASKELL__ import Data.Data (Data)@@ -70,6 +74,9 @@  instance Foldable Tree where     foldMap f (Node x ts) = f x `mappend` foldMap (foldMap f) ts++instance NFData a => NFData (Tree a) where+    rnf (Node x ts) = rnf x `seq` rnf ts  -- | Neat 2-dimensional drawing of a tree. drawTree :: Tree String -> String

@@ -1,8 +1,8 @@ name: containers-version: 0.4.1.0+version: 0.4.2.0 license: BSD3 license-file: LICENSE-maintainer: libraries@haskell.org+maintainer: fox@ucw.cz bug-reports: http://hackage.haskell.org/trac/ghc/newticket?component=libraries%20%28other%29 synopsis: Assorted concrete container types category: Data Structures@@ -20,7 +20,7 @@     location: http://github.com/haskell/containers.git  Library {-    build-depends: base >= 4.2 && < 6, array+    build-depends: base >= 4.2 && < 5, array, deepseq >= 1.2 && < 1.3     ghc-options: -O2     if impl(ghc>6.10)         Ghc-Options: -fregs-graph