Improve fusion rules.
authorMilan Straka <fox@ucw.cz>
Thu, 24 Nov 2011 19:08:52 +0000 (20:08 +0100)
committerMilan Straka <fox@ucw.cz>
Fri, 25 Nov 2011 09:05:38 +0000 (10:05 +0100)
* 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
Data/IntSet.hs
Data/Map/Base.hs
Data/Set.hs

index 0927f35..c9c35b8 100644 (file)
@@ -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.
 --
index b4f388f..e0d5aec 100644 (file)
@@ -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) #-}
index df6acc5..cd2a110 100644 (file)
@@ -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) #-}
index 1ae2ca6..2ed01b3 100644 (file)
@@ -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) #-}