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 <[email protected]> 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. _______________________________________________ Cvs-libraries mailing list [email protected] http://www.haskell.org/mailman/listinfo/cvs-libraries
