Repository : ssh://darcs.haskell.org//srv/darcs/packages/containers On branch : master
http://hackage.haskell.org/trac/ghc/changeset/b49d06bdbabea296ca6846d4a0572bc358c47d3c >--------------------------------------------------------------- commit b49d06bdbabea296ca6846d4a0572bc358c47d3c Author: Milan Straka <[email protected]> Date: Thu Nov 24 20:08:52 2011 +0100 Improve fusion rules. * Add fusion rule for Data.IntMap.toAscList. * Remove the GHC >= 503 condition. * Make assocs, elems and toList call toAscList. * Improve documentation of assocs, elems, toList, toAscList. >--------------------------------------------------------------- Data/IntMap/Base.hs | 32 ++++++++++++++++---------------- Data/IntSet.hs | 16 ++++++++-------- Data/Map/Base.hs | 21 +++++++++++---------- Data/Set.hs | 11 +++++------ 4 files changed, 40 insertions(+), 40 deletions(-) diff --git a/Data/IntMap/Base.hs b/Data/IntMap/Base.hs index 0927f35..c9c35b8 100644 --- a/Data/IntMap/Base.hs +++ b/Data/IntMap/Base.hs @@ -1480,15 +1480,15 @@ keysSet :: IntMap a -> IntSet.IntSet keysSet m = IntSet.fromDistinctAscList (keys m) --- | /O(n)/. Return all key\/value pairs in the map in ascending key order. --- Subject to list Fusion. +-- | /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")] -- > assocs empty == [] assocs :: IntMap a -> [(Key,a)] -assocs m - = toList m +assocs + = toAscList {-------------------------------------------------------------------- @@ -1502,24 +1502,24 @@ assocs m toList :: IntMap a -> [(Key,a)] toList - = foldrWithKey (\k x xs -> (k,x):xs) [] - -#if __GLASGOW_HASKELL__ >= 503 --- List fusion for the above two functions -{-# RULES "IntMap/toList" forall im . toList im = build (\c n -> foldrWithKey (\k x xs -> c (k,x) xs) n im) #-} -{-# RULES "IntMap/assocs" forall im . assocs im = build (\c n -> foldrWithKey (\k x xs -> c (k,x) xs) n im) #-} -#endif - + = toAscList -- | /O(n)/. Convert the map to a list of key\/value pairs where the --- keys are in ascending order. +-- keys are in ascending order. Subject to list fusion. -- -- > toAscList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")] toAscList :: IntMap a -> [(Key,a)] -toAscList t - = -- NOTE: the following algorithm only works for big-endian trees - let (pos,neg) = span (\(k,_) -> k >=0) (foldrWithKey (\k x xs -> (k,x):xs) [] t) in neg ++ pos +toAscList + = foldrWithKey (\k x xs -> (k,x):xs) [] + +#if __GLASGOW_HASKELL__ +-- List fusion for the above three functions +{-# RULES "IntMap/assocs" forall im . assocs im = build (\c n -> foldrWithKey (\k x xs -> c (k,x) xs) n im) #-} +{-# RULES "IntMap/toList" forall im . toList im = build (\c n -> foldrWithKey (\k x xs -> c (k,x) xs) n im) #-} +{-# RULES "IntMap/toAscList" forall im . toAscList im = build (\c n -> foldrWithKey (\k x xs -> c (k,x) xs) n im) #-} +#endif + -- | /O(n*min(n,W))/. Create a map from a list of key\/value pairs. -- diff --git a/Data/IntSet.hs b/Data/IntSet.hs index b4f388f..e0d5aec 100644 --- a/Data/IntSet.hs +++ b/Data/IntSet.hs @@ -757,26 +757,26 @@ foldl' f z t = {-------------------------------------------------------------------- List variations --------------------------------------------------------------------} --- | /O(n)/. The elements of a set. (For sets, this is equivalent to toList.) --- Subject to list fusion +-- | /O(n)/. An alias of 'toAscList'. The elements of a set in ascending order. +-- Subject to list fusion. elems :: IntSet -> [Int] -elems t - = toAscList t +elems + = toAscList {-------------------------------------------------------------------- Lists --------------------------------------------------------------------} -- | /O(n)/. Convert the set to a list of elements. Subject to list fusion. toList :: IntSet -> [Int] -toList t - = toAscList t +toList + = toAscList -- | /O(n)/. Convert the set to an ascending list of elements. Subject to list -- fusion. toAscList :: IntSet -> [Int] -toAscList t = foldr (:) [] t +toAscList = foldr (:) [] -#if __GLASGOW_HASKELL__ >= 503 +#if __GLASGOW_HASKELL__ -- List fusion for the above three functions {-# RULES "IntSet/toList" forall is . toList is = build (\c n -> foldr c n is) #-} {-# RULES "IntSet/toAscList" forall is . toAscList is = build (\c n -> foldr c n is) #-} diff --git a/Data/Map/Base.hs b/Data/Map/Base.hs index df6acc5..cd2a110 100644 --- a/Data/Map/Base.hs +++ b/Data/Map/Base.hs @@ -228,9 +228,7 @@ import Data.Typeable import Control.DeepSeq (NFData(rnf)) #if __GLASGOW_HASKELL__ -#if __GLASGOW_HASKELL__ >= 503 import GHC.Exts ( build ) -#endif import Text.Read import Data.Data #endif @@ -1760,14 +1758,15 @@ keysSet m = Set.fromDistinctAscList (keys m) {-# INLINABLE keysSet #-} #endif --- | /O(n)/. Return all key\/value pairs in the map in ascending key order. +-- | /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")] -- > assocs empty == [] assocs :: Map k a -> [(k,a)] assocs m - = toList m + = toAscList m #if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE assocs #-} #endif @@ -1820,35 +1819,37 @@ fromListWithKey f xs {-# INLINABLE fromListWithKey #-} #endif --- | /O(n)/. Convert 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 == [] toList :: Map k a -> [(k,a)] -toList t = toAscList t +toList = toAscList #if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE toList #-} #endif --- | /O(n)/. Convert to an ascending list. Subject to list fusion. +-- | /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")] toAscList :: Map k a -> [(k,a)] -toAscList t = foldrWithKey (\k x xs -> (k,x):xs) [] t +toAscList = foldrWithKey (\k x xs -> (k,x):xs) [] #if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE toAscList #-} #endif --- | /O(n)/. Convert to a descending list. Subject to list fusion. +-- | /O(n)/. Convert the map to a list of key\/value pairs where the keys +-- are in descending order. Subject to list fusion. toDescList :: Map k a -> [(k,a)] toDescList t = foldlWithKey (\xs k x -> (k,x):xs) [] t #if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE toDescList #-} #endif -#if __GLASGOW_HASKELL__ >= 503 +#if __GLASGOW_HASKELL__ -- List fusion for the above four functions {-# RULES "Map/assocs" forall m . assocs m = build (\c n -> foldrWithKey (\k x xs -> c (k,x) xs) n m) #-} {-# RULES "Map/toList" forall m . toList m = build (\c n -> foldrWithKey (\k x xs -> c (k,x) xs) n m) #-} diff --git a/Data/Set.hs b/Data/Set.hs index 1ae2ca6..2ed01b3 100644 --- a/Data/Set.hs +++ b/Data/Set.hs @@ -156,11 +156,9 @@ import qualified List -} #if __GLASGOW_HASKELL__ +import GHC.Exts ( build ) import Text.Read import Data.Data -#if __GLASGOW_HASKELL__ >= 503 -import GHC.Exts ( build ) -#endif #endif -- Use macros to define strictness of functions. @@ -621,9 +619,10 @@ foldl' f = go {-------------------------------------------------------------------- List variations --------------------------------------------------------------------} --- | /O(n)/. The elements of a set. Subject to list fusion. +-- | /O(n)/. An alias of 'toAscList'. The elements of a set in ascending order. +-- Subject to list fusion. elems :: Set a -> [a] -elems = toList +elems = toAscList #if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE elems #-} #endif @@ -645,7 +644,7 @@ toAscList = foldr (:) [] {-# INLINABLE toAscList #-} #endif -#if __GLASGOW_HASKELL__ >= 503 +#if __GLASGOW_HASKELL__ -- List fusion for the above three functions {-# RULES "Set/toList" forall s . toList s = build (\c n -> foldr c n s) #-} {-# RULES "Set/toAscList" forall s . toAscList s = build (\c n -> foldr c n s) #-} _______________________________________________ Cvs-libraries mailing list [email protected] http://www.haskell.org/mailman/listinfo/cvs-libraries
