[commit: containers] master: Improve fusion rules. (b49d06b)
Ian Lynagh
igloo at earth.li
Thu Feb 23 01:15:03 CET 2012
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 <fox at ucw.cz>
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) #-}
More information about the Cvs-libraries
mailing list