Added `foldMapWithKey`.
authorEdward Kmett <ekmett@gmail.com>
Tue, 25 Dec 2012 10:57:40 +0000 (05:57 -0500)
committerEdward Kmett <ekmett@gmail.com>
Tue, 25 Dec 2012 10:59:21 +0000 (05:59 -0500)
Data/IntMap/Base.hs
Data/IntMap/Lazy.hs
Data/IntMap/Strict.hs
Data/Map/Base.hs
Data/Map/Lazy.hs
Data/Map/Strict.hs

index 73b05b2..05dd3fa 100644 (file)
@@ -123,6 +123,8 @@ module Data.IntMap.Base (
     , foldl
     , foldrWithKey
     , foldlWithKey
+    , foldMapWithKey
+
     -- ** Strict folds
     , foldr'
     , foldl'
@@ -1670,6 +1672,19 @@ foldlWithKey' f z = \t ->      -- Use lambda t to be inlinable with two argument
     go z' (Bin _ _ l r) = go (go z' l) r
 {-# INLINE foldlWithKey' #-}
 
+-- | /O(n)/. Fold the keys and values in the map using the given monoid, such that
+--
+-- @'foldMapWithKey' f = 'Prelude.fold' . 'mapWithKey' f@
+--
+-- This can be an asymptotically faster than 'foldrWithKey' or 'foldlWithKey' for some monoids.
+foldMapWithKey :: Monoid m => (Key -> a -> m) -> IntMap a -> m
+foldMapWithKey f = go
+  where
+    go Nil           = mempty
+    go (Tip kx x)    = f kx x
+    go (Bin _ _ l r) = go l `mappend` go r
+{-# INLINE foldMapWithKey #-}
+
 {--------------------------------------------------------------------
   List variations
 --------------------------------------------------------------------}
index fed6538..6de26f8 100644 (file)
@@ -133,6 +133,8 @@ module Data.IntMap.Lazy (
     , IM.foldl
     , foldrWithKey
     , foldlWithKey
+    , foldMapWithKey
+
     -- ** Strict folds
     , foldr'
     , foldl'
index e6b3708..168d7a8 100644 (file)
@@ -139,6 +139,8 @@ module Data.IntMap.Strict (
     , foldl
     , foldrWithKey
     , foldlWithKey
+    , foldMapWithKey
+
     -- ** Strict folds
     , foldr'
     , foldl'
index 3e240e8..670cdd0 100644 (file)
@@ -169,6 +169,8 @@ module Data.Map.Base (
     , foldl
     , foldrWithKey
     , foldlWithKey
+    , foldMapWithKey
+
     -- ** Strict folds
     , foldr'
     , foldl'
@@ -1873,6 +1875,18 @@ foldlWithKey' f z = go z
     go z' (Bin _ kx x l r) = go (f (go z' l) kx x) r
 {-# INLINE foldlWithKey' #-}
 
+-- | /O(n)/. Fold the keys and values in the map using the given monoid, such that
+--
+-- @'foldMapWithKey' f = 'Prelude.fold' . 'mapWithKey' f@
+--
+-- This can be an asymptotically faster than 'foldrWithKey' or 'foldlWithKey' for some monoids.
+foldMapWithKey :: Monoid m => (k -> a -> m) -> Map k a -> m
+foldMapWithKey f = go
+  where
+    go Tip             = mempty
+    go (Bin _ k v l r) = go l `mappend` f k v `mappend` go r
+{-# INLINE foldMapWithKey #-}
+
 {--------------------------------------------------------------------
   List variations
 --------------------------------------------------------------------}
index e637376..1b939f7 100644 (file)
@@ -129,6 +129,8 @@ module Data.Map.Lazy (
     , M.foldl
     , foldrWithKey
     , foldlWithKey
+    , foldMapWithKey
+
     -- ** Strict folds
     , foldr'
     , foldl'
index faa0478..9e91f40 100644 (file)
@@ -136,6 +136,8 @@ module Data.Map.Strict
     , foldl
     , foldrWithKey
     , foldlWithKey
+    , foldMapWithKey
+
     -- ** Strict folds
     , foldr'
     , foldl'