Add toDescList.
authorMilan Straka <fox@ucw.cz>
Mon, 12 Dec 2011 12:08:36 +0000 (13:08 +0100)
committerMilan Straka <fox@ucw.cz>
Sun, 4 Mar 2012 15:38:12 +0000 (16:38 +0100)
Add toDescList to IntMap, Set and IntSet. Also add
corresponding fusion RULES and tests.

The function is added as community was opposed to removing
toDescList from Map.

Data/IntMap/Base.hs
Data/IntMap/Lazy.hs
Data/IntMap/Strict.hs
Data/IntSet.hs
Data/Map/Base.hs
Data/Set.hs
tests/intmap-properties.hs
tests/intset-properties.hs
tests/map-properties.hs
tests/set-properties.hs

index a8dd2a4..aa122a4 100644 (file)
@@ -113,6 +113,7 @@ module Data.IntMap.Base (
 
             -- ** Ordered lists
             , toAscList
+            , toDescList
             , fromAscList
             , fromAscListWith
             , fromAscListWithKey
@@ -1567,6 +1568,14 @@ toList = toAscList
 toAscList :: IntMap a -> [(Key,a)]
 toAscList = foldrWithKey (\k x xs -> (k,x):xs) []
 
+-- | /O(n)/. Convert the map to a list of key\/value pairs where the keys
+-- are in descending order. Subject to list fusion.
+--
+-- > toDescList (fromList [(5,"a"), (3,"b")]) == [(5,"a"), (3,"b")]
+
+toDescList :: IntMap a -> [(Key,a)]
+toDescList = foldlWithKey (\xs k x -> (k,x):xs) []
+
 #if __GLASGOW_HASKELL__
 -- List fusion for the list generating functions
 {-# RULES "IntMap/elems" forall im . elems im = build (\c n -> foldr c n im) #-}
@@ -1574,6 +1583,7 @@ toAscList = foldrWithKey (\k x xs -> (k,x):xs) []
 {-# 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) #-}
+{-# RULES "IntMap/toDescList" forall im . toDescList im = build (\c n -> foldlWithKey (\xs k x -> c (k,x) xs) n im) #-}
 #endif
 
 
index e414efc..e6b2d99 100644 (file)
@@ -145,6 +145,7 @@ module Data.IntMap.Lazy (
 
             -- ** Ordered lists
             , toAscList
+            , toDescList
             , fromAscList
             , fromAscListWith
             , fromAscListWithKey
index b0bfb47..17d6b5d 100644 (file)
@@ -149,6 +149,7 @@ module Data.IntMap.Strict (
 
             -- ** Ordered lists
             , toAscList
+            , toDescList
             , fromAscList
             , fromAscListWith
             , fromAscListWithKey
index 4f5c3dd..10d7b85 100644 (file)
@@ -125,6 +125,7 @@ module Data.IntSet (
 
             -- ** Ordered list
             , toAscList
+            , toDescList
             , fromAscList
             , fromDistinctAscList
 
@@ -789,11 +790,17 @@ toList
 toAscList :: IntSet -> [Int]
 toAscList = foldr (:) []
 
+-- | /O(n)/. Convert the set to a descending list of elements. Subject to list
+-- fusion.
+toDescList :: IntSet -> [Int]
+toDescList = foldl (flip (:)) []
+
 #if __GLASGOW_HASKELL__
 -- 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/toDescList" forall is . toDescList is = build (\c n -> foldl (\xs x -> c x xs) n is) #-}
 #endif
 
 
index c8382d7..3c5171e 100644 (file)
@@ -1758,8 +1758,11 @@ toAscList = foldrWithKey (\k x xs -> (k,x):xs) []
 
 -- | /O(n)/. Convert the map to a list of key\/value pairs where the keys
 -- are in descending order. Subject to list fusion.
+--
+-- > toDescList (fromList [(5,"a"), (3,"b")]) == [(5,"a"), (3,"b")]
+
 toDescList :: Map k a -> [(k,a)]
-toDescList t  = foldlWithKey (\xs k x -> (k,x):xs) [] t
+toDescList = foldlWithKey (\xs k x -> (k,x):xs) []
 
 #if __GLASGOW_HASKELL__
 -- List fusion for the list generating functions
index 6940298..0ec2eb9 100644 (file)
@@ -127,6 +127,7 @@ module Data.Set (
 
             -- ** Ordered list
             , toAscList
+            , toDescList
             , fromAscList
             , fromDistinctAscList
 
@@ -622,11 +623,17 @@ toList = toAscList
 toAscList :: Set a -> [a]
 toAscList = foldr (:) []
 
+-- | /O(n)/. Convert the set to a descending list of elements. Subject to list
+-- fusion.
+toDescList :: Set a -> [a]
+toDescList = foldl (flip (:)) []
+
 #if __GLASGOW_HASKELL__
 -- 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/toDescList" forall s . toDescList s = build (\c n -> foldl (\xs x -> c x xs) n s) #-}
 #endif
 
 -- | /O(n*log n)/. Create a set from a list of elements.
index 3081d7f..b6dcc12 100644 (file)
@@ -79,6 +79,7 @@ main = defaultMainWithOpts
              , testCase "fromListWith" test_fromListWith
              , testCase "fromListWithKey" test_fromListWithKey
              , testCase "toAscList" test_toAscList
+             , testCase "toDescList" test_toDescList
              , testCase "showTree" test_showTree
              , testCase "fromAscList" test_fromAscList
              , testCase "fromAscListWith" test_fromAscListWith
@@ -125,6 +126,8 @@ main = defaultMainWithOpts
              , testProperty "intersection model"   prop_intersectionModel
              , testProperty "fromAscList"          prop_ordered
              , testProperty "fromList then toList" prop_list
+             , testProperty "toDescList"           prop_descList
+             , testProperty "toAscList+toDescList" prop_ascDescList
              , testProperty "alter"                prop_alter
              , testProperty "index"                prop_index
              , testProperty "null"                 prop_null
@@ -496,6 +499,9 @@ test_fromListWithKey = do
 test_toAscList :: Assertion
 test_toAscList = toAscList (fromList [(5,"a"), (3,"b")]) @?= [(3,"b"), (5,"a")]
 
+test_toDescList :: Assertion
+test_toDescList = toDescList (fromList [(5,"a"), (3,"b")]) @?= [(5,"a"), (3,"b")]
+
 test_showTree :: Assertion
 test_showTree =
        (let t = fromDistinctAscList [(x,()) | x <- [1..5]]
@@ -745,6 +751,13 @@ prop_ordered
 prop_list :: [Int] -> Bool
 prop_list xs = (sort (nub xs) == [x | (x,()) <- toList (fromList [(x,()) | x <- xs])])
 
+prop_descList :: [Int] -> Bool
+prop_descList xs = (reverse (sort (nub xs)) == [x | (x,()) <- toDescList (fromList [(x,()) | x <- xs])])
+
+prop_ascDescList :: [Int] -> Bool
+prop_ascDescList xs = toAscList m == reverse (toDescList m)
+  where m = fromList $ zip xs $ repeat ()
+
 ----------------------------------------------------------------
 
 prop_alter :: UMap -> Int -> Bool
index b80d27d..7ed7bc9 100644 (file)
@@ -20,6 +20,8 @@ main = defaultMainWithOpts [ testProperty "prop_Single" prop_Single
                            , testProperty "prop_Int" prop_Int
                            , testProperty "prop_Ordered" prop_Ordered
                            , testProperty "prop_List" prop_List
+                           , testProperty "prop_DescList" prop_DescList
+                           , testProperty "prop_AscDescList" prop_AscDescList
                            , testProperty "prop_fromList" prop_fromList
                            , testProperty "prop_MaskPow2" prop_MaskPow2
                            , testProperty "prop_Prefix" prop_Prefix
@@ -114,6 +116,13 @@ prop_List :: [Int] -> Bool
 prop_List xs
   = (sort (nub xs) == toAscList (fromList xs))
 
+prop_DescList :: [Int] -> Bool
+prop_DescList xs = (reverse (sort (nub xs)) == toDescList (fromList xs))
+
+prop_AscDescList :: [Int] -> Bool
+prop_AscDescList xs = toAscList s == reverse (toDescList s)
+  where s = fromList xs
+
 prop_fromList :: [Int] -> Bool
 prop_fromList xs
   = case fromList xs of
index 470e613..b6dc089 100644 (file)
@@ -145,6 +145,8 @@ main = defaultMainWithOpts
          , testProperty "intersection model"   prop_intersectionModel
          , testProperty "fromAscList"          prop_ordered
          , testProperty "fromList then toList" prop_list
+         , testProperty "toDescList"           prop_descList
+         , testProperty "toAscList+toDescList" prop_ascDescList
          , testProperty "alter"                prop_alter
          , testProperty "index"                prop_index
          , testProperty "null"                 prop_null
@@ -878,6 +880,13 @@ prop_ordered
 prop_list :: [Int] -> Bool
 prop_list xs = (sort (nub xs) == [x | (x,()) <- toList (fromList [(x,()) | x <- xs])])
 
+prop_descList :: [Int] -> Bool
+prop_descList xs = (reverse (sort (nub xs)) == [x | (x,()) <- toDescList (fromList [(x,()) | x <- xs])])
+
+prop_ascDescList :: [Int] -> Bool
+prop_ascDescList xs = toAscList m == reverse (toDescList m)
+  where m = fromList $ zip xs $ repeat ()
+
 ----------------------------------------------------------------
 
 prop_alter :: UMap -> Int -> Bool
index 260b42f..19a678a 100644 (file)
@@ -26,6 +26,8 @@ main = defaultMainWithOpts [ testProperty "prop_Valid" prop_Valid
                            , testProperty "prop_Int" prop_Int
                            , testProperty "prop_Ordered" prop_Ordered
                            , testProperty "prop_List" prop_List
+                           , testProperty "prop_DescList" prop_DescList
+                           , testProperty "prop_AscDescList" prop_AscDescList
                            , testProperty "prop_fromList" prop_fromList
                            , testProperty "prop_isProperSubsetOf" prop_isProperSubsetOf
                            , testProperty "prop_isProperSubsetOf2" prop_isProperSubsetOf2
@@ -170,6 +172,13 @@ prop_Ordered = forAll (choose (5,100)) $ \n ->
 prop_List :: [Int] -> Bool
 prop_List xs = (sort (nub xs) == toList (fromList xs))
 
+prop_DescList :: [Int] -> Bool
+prop_DescList xs = (reverse (sort (nub xs)) == toDescList (fromList xs))
+
+prop_AscDescList :: [Int] -> Bool
+prop_AscDescList xs = toAscList s == reverse (toDescList s)
+  where s = fromList xs
+
 prop_fromList :: [Int] -> Bool
 prop_fromList xs
   = case fromList xs of