[commit: containers] master: Add list fusion RULES for keys and elems. (79e11f5)

[Ian Lynagh]

Repository : ssh://darcs.haskell.org//srv/darcs/packages/containers

On branch  : master

http://hackage.haskell.org/trac/ghc/changeset/79e11f5719a7cba91f70491e4cf9b5a63538e13e

>---------------------------------------------------------------

commit 79e11f5719a7cba91f70491e4cf9b5a63538e13e
Author: Milan Straka <fox at ucw.cz>
Date:   Mon Nov 28 12:40:37 2011 +0100

    Add list fusion RULES for keys and elems.

>---------------------------------------------------------------

 Data/IntMap/Base.hs |   14 ++++++++------
 Data/IntSet.hs      |    4 ++--
 Data/Map/Base.hs    |   14 ++++++++------
 Data/Set.hs         |    4 ++--
 4 files changed, 20 insertions(+), 16 deletions(-)

diff --git a/Data/IntMap/Base.hs b/Data/IntMap/Base.hs
index 9ff9a16..c8c96c2 100644
--- a/Data/IntMap/Base.hs
+++ b/Data/IntMap/Base.hs
@@ -1454,22 +1454,22 @@ foldlWithKey' f z t =
 --------------------------------------------------------------------}
 -- | /O(n)/.
 -- Return all elements of the map in the ascending order of their keys.
+-- Subject to list fusion.
 --
 -- > elems (fromList [(5,"a"), (3,"b")]) == ["b","a"]
 -- > elems empty == []
 
 elems :: IntMap a -> [a]
-elems
-  = foldr (:) []
+elems = foldr (:) []
 
--- | /O(n)/. Return all keys of the map in ascending order.
+-- | /O(n)/. Return all keys of the map in ascending order. Subject to list
+-- fusion.
 --
 -- > keys (fromList [(5,"a"), (3,"b")]) == [3,5]
 -- > keys empty == []
 
 keys  :: IntMap a -> [Key]
-keys
-  = foldrWithKey (\k _ ks -> k:ks) []
+keys = foldrWithKey (\k _ ks -> k : ks) []
 
 -- | /O(n*min(n,W))/. The set of all keys of the map.
 --
@@ -1514,7 +1514,9 @@ toAscList
   = foldrWithKey (\k x xs -> (k,x):xs) []
 
 #if __GLASGOW_HASKELL__
--- List fusion for the above three functions
+-- List fusion for the list generating functions
+{-# RULES "IntMap/elems" forall im . elems im = build (\c n -> foldr c n im) #-}
+{-# RULES "IntMap/keys" forall im . keys im = build (\c n -> foldrWithKey (\k _ ks -> c k ks) n im) #-}
 {-# 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) #-}
diff --git a/Data/IntSet.hs b/Data/IntSet.hs
index ad4e5fc..ff66b47 100644
--- a/Data/IntSet.hs
+++ b/Data/IntSet.hs
@@ -790,10 +790,10 @@ toAscList :: IntSet -> [Int]
 toAscList = foldr (:) []
 
 #if __GLASGOW_HASKELL__
--- List fusion for the above three functions
+-- List fusion for the list generating functions
+{-# RULES "IntSet/elems" forall is . elems is = build (\c n -> foldr c n is) #-}
 {-# 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) #-}
-{-# RULES "IntSet/elems" forall is . elems is = build (\c n -> foldr c n is) #-}
 #endif
 
 
diff --git a/Data/Map/Base.hs b/Data/Map/Base.hs
index 723003f..7fc0576 100644
--- a/Data/Map/Base.hs
+++ b/Data/Map/Base.hs
@@ -1659,22 +1659,22 @@ foldlWithKey' f = go
 --------------------------------------------------------------------}
 -- | /O(n)/.
 -- Return all elements of the map in the ascending order of their keys.
+-- Subject to list fusion.
 --
 -- > elems (fromList [(5,"a"), (3,"b")]) == ["b","a"]
 -- > elems empty == []
 
 elems :: Map k a -> [a]
-elems m
-  = [x | (_,x) <- assocs m]
+elems = foldr (:) []
 
--- | /O(n)/. Return all keys of the map in ascending order.
+-- | /O(n)/. Return all keys of the map in ascending order. Subject to list
+-- fusion.
 --
 -- > keys (fromList [(5,"a"), (3,"b")]) == [3,5]
 -- > keys empty == []
 
 keys  :: Map k a -> [k]
-keys m
-  = [k | (k,_) <- assocs m]
+keys = foldrWithKey (\k _ ks -> k : ks) []
 
 -- | /O(n)/. The set of all keys of the map.
 --
@@ -1764,7 +1764,9 @@ toDescList :: Map k a -> [(k,a)]
 toDescList t  = foldlWithKey (\xs k x -> (k,x):xs) [] t
 
 #if __GLASGOW_HASKELL__
--- List fusion for the above four functions
+-- List fusion for the list generating functions
+{-# RULES "Map/elems" forall m . elems m = build (\c n -> foldr c n m) #-}
+{-# RULES "Map/keys" forall m . keys m = build (\c n -> foldrWithKey (\k _ ks -> c k ks) n m) #-}
 {-# 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) #-}
 {-# RULES "Map/toAscList" forall m . toAscList 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 fda120d..6940298 100644
--- a/Data/Set.hs
+++ b/Data/Set.hs
@@ -623,10 +623,10 @@ toAscList :: Set a -> [a]
 toAscList = foldr (:) []
 
 #if __GLASGOW_HASKELL__
--- List fusion for the above three functions
+-- List fusion for the list generating functions
+{-# RULES "Set/elems" forall s . elems s = build (\c n -> foldr c n s) #-}
 {-# 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) #-}
-{-# RULES "Set/elems" forall s . elems s = build (\c n -> foldr c n s) #-}
 #endif
 
 -- | /O(n*log n)/. Create a set from a list of elements.