Add all fold variants.
authorMilan Straka <fox@ucw.cz>
Wed, 13 Jul 2011 10:31:39 +0000 (12:31 +0200)
committerMilan Straka <fox@ucw.cz>
Wed, 13 Jul 2011 10:58:37 +0000 (12:58 +0200)
Add foldr, foldl, foldr', foldl' to Data.*Set and Data.*Map.
The fold function is in Legacy section and said to be deprecated
and removed in the future.

Also add foldrWithKey, foldlWithKey, foldrWithKey', foldlWithKey
to Data.*Map. The foldWithKey function is in Legacy section and said
to be deprecated and removed in the future.

Data/IntMap.hs
Data/IntSet.hs
Data/Map.hs
Data/Set.hs

index 9016b37..99b2ddb 100644 (file)
@@ -111,7 +111,17 @@ module Data.IntMap (
             , mapAccumWithKey
             , mapAccumRWithKey
 
-            -- ** Fold
+            -- * Folds
+            , foldr
+            , foldl
+            , foldrWithKey
+            , foldlWithKey
+            -- ** Strict folds
+            , foldr'
+            , foldl'
+            , foldrWithKey'
+            , foldlWithKey'
+            -- ** Legacy folds
             , fold
             , foldWithKey
 
@@ -205,6 +215,12 @@ import GlaExts ( Word(..), Int(..), shiftRL# )
 import Data.Word
 #endif
 
+-- Use macros to define strictness of functions.
+-- STRICT_x_OF_y denotes an y-ary function strict in the x-th parameter.
+-- We do not use BangPatterns, because they are not in any standard and we
+-- want the compilers to be compiled by as many compilers as possible.
+#define STRICT_1_OF_2(fn) fn arg _ | arg `seq` False = undefined
+
 infixl 9 \\{-This comment teaches CPP correct behaviour -}
 
 -- A "Nat" is a natural machine word (an unsigned Int)
@@ -1373,46 +1389,157 @@ splitLookup' k t
 {--------------------------------------------------------------------
   Fold
 --------------------------------------------------------------------}
--- | /O(n)/. Fold the values in the map, such that
--- @'fold' f z == 'Prelude.foldr' f z . 'elems'@.
+-- | /O(n)/. Fold the values in the map using the given right-associative
+-- binary operator. This function is an equivalent of 'foldr' and is present
+-- for compatibility only.
+--
+-- /Please note that fold will be deprecated in the future and removed./
+fold :: (a -> b -> b) -> b -> IntMap a -> b
+fold = foldr
+{-# INLINE fold #-}
+
+-- | /O(n)/. Fold the values in the map using the given right-associative
+-- binary operator, such that @'foldr' f z == 'Prelude.foldr' f z . 'elems'@.
+--
 -- For example,
 --
--- > elems map = fold (:) [] map
+-- > elems map = foldr (:) [] map
 --
 -- > let f a len = len + (length a)
--- > fold f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
+-- > foldr f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
+foldr :: (a -> b -> b) -> b -> IntMap a -> b
+foldr f z t =
+  case t of Bin 0 m l r | m < 0 -> go (go z l) r -- put negative numbers before
+            _                   -> go z t
+  where
+    go z' Nil           = z'
+    go z' (Tip _ x)     = f x z'
+    go z' (Bin _ _ l r) = go (go z' r) l
+{-# INLINE foldr #-}
 
-fold :: (a -> b -> b) -> b -> IntMap a -> b
-fold f = foldWithKey (\_ x y -> f x y)
-{-# INLINE fold #-}
+-- | /O(n)/. A strict version of 'foldr'. Each application of the operator is
+-- evaluated before using the result in the next application. This
+-- function is strict in the starting value.
+foldr' :: (a -> b -> b) -> b -> IntMap a -> b
+foldr' f z t =
+  case t of Bin 0 m l r | m < 0 -> go (go z l) r -- put negative numbers before
+            _                   -> go z t
+  where
+    STRICT_1_OF_2(go)
+    go z' Nil           = z'
+    go z' (Tip _ x)     = f x z'
+    go z' (Bin _ _ l r) = go (go z' r) l
+{-# INLINE foldr' #-}
 
--- | /O(n)/. Fold the keys and values in the map, such that
--- @'foldWithKey' f z == 'Prelude.foldr' ('uncurry' f) z . 'toAscList'@.
+-- | /O(n)/. Fold the values in the map using the given left-associative
+-- binary operator, such that @'foldl' f z == 'Prelude.foldl' f z . 'elems'@.
+--
 -- For example,
 --
--- > keys map = foldWithKey (\k x ks -> k:ks) [] map
+-- > elems = reverse . foldl (flip (:)) []
 --
--- > let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
--- > foldWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)"
+-- > let f len a = len + (length a)
+-- > foldl f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
+foldl :: (a -> b -> a) -> a -> IntMap b -> a
+foldl f z t =
+  case t of Bin 0 m l r | m < 0 -> go (go z r) l -- put negative numbers before
+            _                   -> go z t
+  where
+    go z' Nil           = z'
+    go z' (Tip _ x)     = f z' x
+    go z' (Bin _ _ l r) = go (go z' l) r
+{-# INLINE foldl #-}
+
+-- | /O(n)/. A strict version of 'foldl'. Each application of the operator is
+-- evaluated before using the result in the next application. This
+-- function is strict in the starting value.
+foldl' :: (a -> b -> a) -> a -> IntMap b -> a
+foldl' f z t =
+  case t of Bin 0 m l r | m < 0 -> go (go z r) l -- put negative numbers before
+            _                   -> go z t
+  where
+    STRICT_1_OF_2(go)
+    go z' Nil           = z'
+    go z' (Tip _ x)     = f z' x
+    go z' (Bin _ _ l r) = go (go z' l) r
+{-# INLINE foldl' #-}
 
-foldWithKey :: (Key -> a -> b -> b) -> b -> IntMap a -> b
-foldWithKey
-  = foldr
+-- | /O(n)/. Fold the keys and values in the map using the given right-associative
+-- binary operator. This function is an equivalent of 'foldrWithKey' and is present
+-- for compatibility only.
+--
+-- /Please note that foldWithKey will be deprecated in the future and removed./
+foldWithKey :: (Int -> a -> b -> b) -> b -> IntMap a -> b
+foldWithKey = foldrWithKey
 {-# INLINE foldWithKey #-}
 
-foldr :: (Key -> a -> b -> b) -> b -> IntMap a -> b
-foldr f z t
-  = case t of
-      Bin 0 m l r | m < 0 -> go (go z l) r  -- put negative numbers before.
-      Bin _ _ _ _ -> go z t
-      Tip k x     -> f k x z
-      Nil         -> z
+-- | /O(n)/. Fold the keys and values in the map using the given right-associative
+-- binary operator, such that
+-- @'foldrWithKey' f z == 'Prelude.foldr' ('uncurry' f) z . 'toAscList'@.
+--
+-- For example,
+--
+-- > keys map = foldrWithKey (\k x ks -> k:ks) [] map
+--
+-- > let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
+-- > foldrWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)"
+foldrWithKey :: (Int -> a -> b -> b) -> b -> IntMap a -> b
+foldrWithKey f z t =
+  case t of Bin 0 m l r | m < 0 -> go (go z l) r -- put negative numbers before
+            _                   -> go z t
   where
+    go z' Nil           = z'
+    go z' (Tip kx x)    = f kx x z'
     go z' (Bin _ _ l r) = go (go z' r) l
-    go z' (Tip k x)     = f k x z'
+{-# INLINE foldrWithKey #-}
+
+-- | /O(n)/. A strict version of 'foldrWithKey'. Each application of the operator is
+-- evaluated before using the result in the next application. This
+-- function is strict in the starting value.
+foldrWithKey' :: (Int -> a -> b -> b) -> b -> IntMap a -> b
+foldrWithKey' f z t =
+  case t of Bin 0 m l r | m < 0 -> go (go z l) r -- put negative numbers before
+            _                   -> go z t
+  where
+    STRICT_1_OF_2(go)
     go z' Nil           = z'
-{-# INLINE foldr #-}
+    go z' (Tip kx x)    = f kx x z'
+    go z' (Bin _ _ l r) = go (go z' r) l
+{-# INLINE foldrWithKey' #-}
 
+-- | /O(n)/. Fold the keys and values in the map using the given left-associative
+-- binary operator, such that
+-- @'foldlWithKey' f z == 'Prelude.foldl' (\\z' (kx, x) -> f z' kx x) z . 'toAscList'@.
+--
+-- For example,
+--
+-- > keys = reverse . foldlWithKey (\ks k x -> k:ks) []
+--
+-- > let f result k a = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
+-- > foldlWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (3:b)(5:a)"
+foldlWithKey :: (a -> Int -> b -> a) -> a -> IntMap b -> a
+foldlWithKey f z t =
+  case t of Bin 0 m l r | m < 0 -> go (go z r) l -- put negative numbers before
+            _                   -> go z t
+  where
+    go z' Nil           = z'
+    go z' (Tip kx x)    = f z' kx x
+    go z' (Bin _ _ l r) = go (go z' l) r
+{-# INLINE foldlWithKey #-}
+
+-- | /O(n)/. A strict version of 'foldlWithKey'. Each application of the operator is
+-- evaluated before using the result in the next application. This
+-- function is strict in the starting value.
+foldlWithKey' :: (a -> Int -> b -> a) -> a -> IntMap b -> a
+foldlWithKey' f z t =
+  case t of Bin 0 m l r | m < 0 -> go (go z r) l -- put negative numbers before
+            _                   -> go z t
+  where
+    STRICT_1_OF_2(go)
+    go z' Nil           = z'
+    go z' (Tip kx x)    = f z' kx x
+    go z' (Bin _ _ l r) = go (go z' l) r
+{-# INLINE foldlWithKey' #-}
 
 {--------------------------------------------------------------------
   List variations 
@@ -1425,7 +1552,7 @@ foldr f z t
 
 elems :: IntMap a -> [a]
 elems
-  = foldWithKey (\_ x xs -> x:xs) []
+  = foldr (:) []
 
 -- | /O(n)/. Return all keys of the map in ascending order.
 --
@@ -1434,7 +1561,7 @@ elems
 
 keys  :: IntMap a -> [Key]
 keys
-  = foldWithKey (\k _ ks -> k:ks) []
+  = foldrWithKey (\k _ ks -> k:ks) []
 
 -- | /O(n*min(n,W))/. The set of all keys of the map.
 --
@@ -1465,7 +1592,7 @@ assocs m
 
 toList :: IntMap a -> [(Key,a)]
 toList
-  = foldWithKey (\k x xs -> (k,x):xs) []
+  = foldrWithKey (\k x xs -> (k,x):xs) []
 
 -- | /O(n)/. Convert the map to a list of key\/value pairs where the
 -- keys are in ascending order.
@@ -1475,7 +1602,7 @@ toList
 toAscList :: IntMap a -> [(Key,a)]
 toAscList t   
   = -- NOTE: the following algorithm only works for big-endian trees
-    let (pos,neg) = span (\(k,_) -> k >=0) (foldr (\k x xs -> (k,x):xs) [] t) in neg ++ pos
+    let (pos,neg) = span (\(k,_) -> k >=0) (foldrWithKey (\k x xs -> (k,x):xs) [] t) in neg ++ pos
 
 -- | /O(n*min(n,W))/. Create a map from a list of key\/value pairs.
 --
index d513a1a..aa3af01 100644 (file)
@@ -81,7 +81,13 @@ module Data.IntSet (
             -- * Map
             , map
 
-            -- * Fold
+            -- * Folds
+            , foldr
+            , foldl
+            -- ** Strict folds
+            , foldr'
+            , foldl'
+            -- ** Legacy folds
             , fold
 
             -- * Min\/Max
@@ -139,6 +145,12 @@ import GlaExts ( Word(..), Int(..), shiftRL# )
 import Data.Word
 #endif
 
+-- Use macros to define strictness of functions.
+-- STRICT_x_OF_y denotes an y-ary function strict in the x-th parameter.
+-- We do not use BangPatterns, because they are not in any standard and we
+-- want the compilers to be compiled by as many compilers as possible.
+#define STRICT_1_OF_2(fn) fn arg _ | arg `seq` False = undefined
+
 infixl 9 \\{-This comment teaches CPP correct behaviour -}
 
 -- A "Nat" is a natural machine word (an unsigned Int)
@@ -667,22 +679,75 @@ map f = fromList . List.map f . toList
 {--------------------------------------------------------------------
   Fold
 --------------------------------------------------------------------}
--- | /O(n)/. Fold over the elements of a set in an unspecified order.
+-- | /O(n)/. Fold the elements in the set using the given right-associative
+-- binary operator. This function is an equivalent of 'foldr' and is present
+-- for compatibility only.
 --
--- > sum set   == fold (+) 0 set
--- > elems set == fold (:) [] set
+-- /Please note that fold will be deprecated in the future and removed./
 fold :: (Int -> b -> b) -> b -> IntSet -> b
-fold f z t
-  = case t of
-      Bin 0 m l r | m < 0 -> go (go z l) r  -- put negative numbers before.
-      Bin _ _ _ _ -> go z t
-      Tip x       -> f x z
-      Nil         -> z
+fold = foldr
+{-# INLINE fold #-}
+
+-- | /O(n)/. Fold the elements in the set using the given right-associative
+-- binary operator, such that @'foldr' f z == 'Prelude.foldr' f z . 'toAscList'@.
+--
+-- For example,
+--
+-- > toAscList set = foldr (:) [] set
+foldr :: (Int -> b -> b) -> b -> IntSet -> b
+foldr f z t =
+  case t of Bin 0 m l r | m < 0 -> go (go z l) r -- put negative numbers before
+            _                   -> go z t
   where
+    go z' Nil           = z'
+    go z' (Tip x)       = f x z'
     go z' (Bin _ _ l r) = go (go z' r) l
+{-# INLINE foldr #-}
+
+-- | /O(n)/. A strict version of 'foldr'. Each application of the operator is
+-- evaluated before using the result in the next application. This
+-- function is strict in the starting value.
+foldr' :: (Int -> b -> b) -> b -> IntSet -> b
+foldr' f z t =
+  case t of Bin 0 m l r | m < 0 -> go (go z l) r -- put negative numbers before
+            _                   -> go z t
+  where
+    STRICT_1_OF_2(go)
+    go z' Nil           = z'
     go z' (Tip x)       = f x z'
+    go z' (Bin _ _ l r) = go (go z' r) l
+{-# INLINE foldr' #-}
+
+-- | /O(n)/. Fold the elements in the set using the given left-associative
+-- binary operator, such that @'foldl' f z == 'Prelude.foldl' f z . 'toAscList'@.
+--
+-- For example,
+--
+-- > toDescList set = foldl (flip (:)) [] set
+foldl :: (a -> Int -> a) -> a -> IntSet -> a
+foldl f z t =
+  case t of Bin 0 m l r | m < 0 -> go (go z r) l -- put negative numbers before
+            _                   -> go z t
+  where
+    STRICT_1_OF_2(go)
     go z' Nil           = z'
-{-# INLINE fold #-}
+    go z' (Tip x)       = f z' x
+    go z' (Bin _ _ l r) = go (go z' l) r
+{-# INLINE foldl #-}
+
+-- | /O(n)/. A strict version of 'foldl'. Each application of the operator is
+-- evaluated before using the result in the next application. This
+-- function is strict in the starting value.
+foldl' :: (a -> Int -> a) -> a -> IntSet -> a
+foldl' f z t =
+  case t of Bin 0 m l r | m < 0 -> go (go z r) l -- put negative numbers before
+            _                   -> go z t
+  where
+    STRICT_1_OF_2(go)
+    go z' Nil           = z'
+    go z' (Tip x)       = f z' x
+    go z' (Bin _ _ l r) = go (go z' l) r
+{-# INLINE foldl' #-}
 
 {--------------------------------------------------------------------
   List variations 
index 73a254a..cd63266 100644 (file)
@@ -122,13 +122,19 @@ module Data.Map (
             , mapKeysWith
             , mapKeysMonotonic
 
-            -- ** Fold
-            , fold
-            , foldWithKey
+            -- * Folds
+            , foldr
+            , foldl
             , foldrWithKey
-            , foldrWithKey'
             , foldlWithKey
+            -- ** Strict folds
+            , foldr'
+            , foldl'
+            , foldrWithKey'
             , foldlWithKey'
+            -- ** Legacy folds
+            , fold
+            , foldWithKey
 
             -- * Conversion
             , elems
@@ -206,7 +212,7 @@ module Data.Map (
 
             ) where
 
-import Prelude hiding (lookup,map,filter,null)
+import Prelude hiding (lookup,map,filter,foldr,foldl,null)
 import qualified Data.Set as Set
 import qualified Data.List as List
 import Data.Monoid (Monoid(..))
@@ -1644,68 +1650,132 @@ mapKeysMonotonic f (Bin sz k x l r) =
   Folds  
 --------------------------------------------------------------------}
 
--- | /O(n)/. Fold the values in the map, such that
--- @'fold' f z == 'Prelude.foldr' f z . 'elems'@.
+-- | /O(n)/. Fold the values in the map using the given right-associative
+-- binary operator. This function is an equivalent of 'foldr' and is present
+-- for compatibility only.
+--
+-- /Please note that fold will be deprecated in the future and removed./
+fold :: (a -> b -> b) -> b -> Map k a -> b
+fold = foldr
+{-# INLINE fold #-}
+
+-- | /O(n)/. Fold the values in the map using the given right-associative
+-- binary operator, such that @'foldr' f z == 'Prelude.foldr' f z . 'elems'@.
+--
 -- For example,
 --
--- > elems map = fold (:) [] map
+-- > elems map = foldr (:) [] map
 --
 -- > let f a len = len + (length a)
--- > fold f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
-fold :: (a -> b -> b) -> b -> Map k a -> b
-fold f = foldWithKey (\_ x' z' -> f x' z')
-{-# INLINE fold #-}
+-- > foldr f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
+foldr :: (a -> b -> b) -> b -> Map k a -> b
+foldr f = go
+  where
+    go z Tip             = z
+    go z (Bin _ _ x l r) = go (f x (go z r)) l
+{-# INLINE foldr #-}
+
+-- | /O(n)/. A strict version of 'foldr'. Each application of the operator is
+-- evaluated before using the result in the next application. This
+-- function is strict in the starting value.
+foldr' :: (a -> b -> b) -> b -> Map k a -> b
+foldr' f = go
+  where
+    STRICT_1_OF_2(go)
+    go z Tip             = z
+    go z (Bin _ _ x l r) = go (f x (go z r)) l
+{-# INLINE foldr' #-}
 
--- | /O(n)/. Fold the keys and values in the map, such that
--- @'foldWithKey' f z == 'Prelude.foldr' ('uncurry' f) z . 'toAscList'@.
+-- | /O(n)/. Fold the values in the map using the given left-associative
+-- binary operator, such that @'foldl' f z == 'Prelude.foldl' f z . 'elems'@.
+--
 -- For example,
 --
--- > keys map = foldWithKey (\k x ks -> k:ks) [] map
+-- > elems = reverse . foldl (flip (:)) []
 --
--- > let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
--- > foldWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)"
+-- > let f len a = len + (length a)
+-- > foldl f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
+foldl :: (a -> b -> a) -> a -> Map k b -> a
+foldl f = go
+  where
+    go z Tip             = z
+    go z (Bin _ _ x l r) = go (f (go z l) x) r
+{-# INLINE foldl #-}
+
+-- | /O(n)/. A strict version of 'foldl'. Each application of the operator is
+-- evaluated before using the result in the next application. This
+-- function is strict in the starting value.
+foldl' :: (a -> b -> a) -> a -> Map k b -> a
+foldl' f = go
+  where
+    STRICT_1_OF_2(go)
+    go z Tip             = z
+    go z (Bin _ _ x l r) = go (f (go z l) x) r
+{-# INLINE foldl' #-}
+
+-- | /O(n)/. Fold the keys and values in the map using the given right-associative
+-- binary operator. This function is an equivalent of 'foldrWithKey' and is present
+-- for compatibility only.
 --
--- This is identical to 'foldrWithKey', and you should use that one instead of
--- this one.  This name is kept for backward compatibility.
+-- /Please note that foldWithKey will be deprecated in the future and removed./
 foldWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
 foldWithKey = foldrWithKey
-{-# DEPRECATED foldWithKey "Use foldrWithKey instead" #-}
 {-# INLINE foldWithKey #-}
 
--- | /O(n)/. Post-order fold.  The function will be applied from the lowest
--- value to the highest.
+-- | /O(n)/. Fold the keys and values in the map using the given right-associative
+-- binary operator, such that
+-- @'foldrWithKey' f z == 'Prelude.foldr' ('uncurry' f) z . 'toAscList'@.
+--
+-- For example,
+--
+-- > keys map = foldrWithKey (\k x ks -> k:ks) [] map
+--
+-- > let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
+-- > foldrWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)"
 foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
 foldrWithKey f = go
   where
-    go z Tip              = z
+    go z Tip             = z
     go z (Bin _ kx x l r) = go (f kx x (go z r)) l
 {-# INLINE foldrWithKey #-}
 
--- | /O(n)/. A strict version of 'foldrWithKey'.
+-- | /O(n)/. A strict version of 'foldrWithKey'. Each application of the operator is
+-- evaluated before using the result in the next application. This
+-- function is strict in the starting value.
 foldrWithKey' :: (k -> a -> b -> b) -> b -> Map k a -> b
 foldrWithKey' f = go
   where
+    STRICT_1_OF_2(go)
     go z Tip              = z
-    go z (Bin _ kx x l r) = let z' = go z r
-                            in z `seq` z' `seq` go (f kx x z') l
+    go z (Bin _ kx x l r) = go (f kx x (go z r)) l
 {-# INLINE foldrWithKey' #-}
 
--- | /O(n)/. Pre-order fold.  The function will be applied from the highest
--- value to the lowest.
-foldlWithKey :: (b -> k -> a -> b) -> b -> Map k a -> b
+-- | /O(n)/. Fold the keys and values in the map using the given left-associative
+-- binary operator, such that
+-- @'foldlWithKey' f z == 'Prelude.foldl' (\\z' (kx, x) -> f z' kx x) z . 'toAscList'@.
+--
+-- For example,
+--
+-- > keys = reverse . foldlWithKey (\ks k x -> k:ks) []
+--
+-- > let f result k a = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
+-- > foldlWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (3:b)(5:a)"
+foldlWithKey :: (a -> k -> b -> a) -> a -> Map k b -> a
 foldlWithKey f = go
   where
     go z Tip              = z
     go z (Bin _ kx x l r) = go (f (go z l) kx x) r
 {-# INLINE foldlWithKey #-}
 
--- | /O(n)/. A strict version of 'foldlWithKey'.
-foldlWithKey' :: (b -> k -> a -> b) -> b -> Map k a -> b
+-- | /O(n)/. A strict version of 'foldlWithKey'. Each application of the operator is
+-- evaluated before using the result in the next application. This
+-- function is strict in the starting value.
+foldlWithKey' :: (a -> k -> b -> a) -> a -> Map k b -> a
 foldlWithKey' f = go
   where
+    STRICT_1_OF_2(go)
     go z Tip              = z
-    go z (Bin _ kx x l r) = let z' = go z l
-                            in z `seq` z' `seq` go (f z' kx x) r
+    go z (Bin _ kx x l r) = go (f (go z l) kx x) r
 {-# INLINE foldlWithKey' #-}
 
 {--------------------------------------------------------------------
index eb778e4..5ef1f42 100644 (file)
@@ -90,7 +90,13 @@ module Data.Set (
             , map
             , mapMonotonic
 
-            -- * Fold
+            -- * Folds
+            , foldr
+            , foldl
+            -- ** Strict folds
+            , foldr'
+            , foldl'
+            -- ** Legacy folds
             , fold
 
             -- * Min\/Max
@@ -129,7 +135,7 @@ module Data.Set (
 #endif
             ) where
 
-import Prelude hiding (filter,foldr,null,map)
+import Prelude hiding (filter,foldl,foldr,null,map)
 import qualified Data.List as List
 import Data.Monoid (Monoid(..))
 import Data.Foldable (Foldable(foldMap))
@@ -541,12 +547,21 @@ mapMonotonic f (Bin sz x l r) = Bin sz (f x) (mapMonotonic f l) (mapMonotonic f
 {--------------------------------------------------------------------
   Fold
 --------------------------------------------------------------------}
--- | /O(n)/. Fold over the elements of a set in an unspecified order.
+-- | /O(n)/. Fold the elements in the set using the given right-associative
+-- binary operator. This function is an equivalent of 'foldr' and is present
+-- for compatibility only.
+--
+-- /Please note that fold will be deprecated in the future and removed./
 fold :: (a -> b -> b) -> b -> Set a -> b
 fold = foldr
 {-# INLINE fold #-}
 
--- | /O(n)/. Post-order fold.
+-- | /O(n)/. Fold the elements in the set using the given right-associative
+-- binary operator, such that @'foldr' f z == 'Prelude.foldr' f z . 'toAscList'@.
+--
+-- For example,
+--
+-- > toAscList set = foldr (:) [] set
 foldr :: (a -> b -> b) -> b -> Set a -> b
 foldr f = go
   where
@@ -554,6 +569,41 @@ foldr f = go
     go z (Bin _ x l r) = go (f x (go z r)) l
 {-# INLINE foldr #-}
 
+-- | /O(n)/. A strict version of 'foldr'. Each application of the operator is
+-- evaluated before using the result in the next application. This
+-- function is strict in the starting value.
+foldr' :: (a -> b -> b) -> b -> Set a -> b
+foldr' f = go
+  where
+    STRICT_1_OF_2(go)
+    go z Tip           = z
+    go z (Bin _ x l r) = go (f x (go z r)) l
+{-# INLINE foldr' #-}
+
+-- | /O(n)/. Fold the elements in the set using the given left-associative
+-- binary operator, such that @'foldl' f z == 'Prelude.foldl' f z . 'toAscList'@.
+--
+-- For example,
+--
+-- > toDescList set = foldl (flip (:)) [] set
+foldl :: (a -> b -> a) -> a -> Set b -> a
+foldl f = go
+  where
+    go z Tip           = z
+    go z (Bin _ x l r) = go (f (go z l) x) r
+{-# INLINE foldl #-}
+
+-- | /O(n)/. A strict version of 'foldl'. Each application of the operator is
+-- evaluated before using the result in the next application. This
+-- function is strict in the starting value.
+foldl' :: (a -> b -> a) -> a -> Set b -> a
+foldl' f = go
+  where
+    STRICT_1_OF_2(go)
+    go z Tip           = z
+    go z (Bin _ x l r) = go (f (go z l) x) r
+{-# INLINE foldl' #-}
+
 {--------------------------------------------------------------------
   List variations 
 --------------------------------------------------------------------}