Oops, that was sloppy. Yes, your version does get the job done without allocating. The corrected test is attached to this email.
The lens interface does look quite full featured! And it's nice to see that it consistently includes '_' variants. I cite that as additional evidence for the norm ;-).
Personally, I still want traverseWithKey_ for convenience, especially because the solution you used is non-obvious. I imagine many Data.Map users would not come up with it (as the rest of us on this thread didn't).
import Control.Applicative
import Control.Monad
import Control.DeepSeq
import Control.Exception
import GHC.Stats
import qualified Data.Map.Strict as M
import Data.Time.Clock
import Data.Monoid
import System.Mem
import System.Environment
main :: IO ()
main = do
args <- getArgs
let size = case args of
[] -> 1000000::Int
[n] -> read n
let m0 = M.fromList (map (\i -> (i,i)) [1..size])
let fn 500000 v = putStrLn "Got it!"
fn _ _ = return ()
-- let fn i v = putStrLn$"fn: "++show(i,v)
st <- getCurrentTime
evaluate$ rnf m0
en <- getCurrentTime
performGC
s1 <- getGCStats
putStrLn$"Constructed map in "++show (diffUTCTime en st)++"\n "++ show s1++"\n"
------------------------------------------------------------
-- Regular traverseWithKey uses 48MB
-- traverseWithKey_ uses 200K of allocation:
st <- getCurrentTime
M.traverseWithKey_ fn m0
en <- getCurrentTime
performGC
s2 <- getGCStats
putStrLn$"[traverseWithKey_] Consumed map in "++show (diffUTCTime en st)++"\n "++ show s2++"\n"
putStrLn$"Bytes allocated during consume: "++show (bytesAllocated s2 - bytesAllocated s1)
------------------------------------------------------------
-- foldrWithKey uses 32MB allocation:
st <- getCurrentTime
M.foldrWithKey (\k a -> (fn k a >>)) (return ()) m0
en <- getCurrentTime
performGC
s3 <- getGCStats
putStrLn$"[foldrWithKey] Consumed map in "++show (diffUTCTime en st)++"\n "++ show s3++"\n"
putStrLn$"Bytes allocated during consume: "++show (bytesAllocated s3 - bytesAllocated s2)
------------------------------------------------------------
-- An alternate version was proposed by Shachaf Ben-Kiki:
st <- getCurrentTime
traverseWithKey_ fn m0
en <- getCurrentTime
performGC
s4 <- getGCStats
putStrLn$"[alternate traverseWithKey_] Consumed map in "++show (diffUTCTime en st)++"\n "++ show s4++"\n"
putStrLn$"Bytes allocated during consume: "++show (bytesAllocated s4 - bytesAllocated s3)
return ()
foldMapWithKey :: Monoid r => (k -> a -> r) -> M.Map k a -> r
foldMapWithKey f = getConst . M.traverseWithKey (\k x -> Const (f k x))
-- Since the Applicative used is Const (newtype Const m a = Const m), the
-- structure is never built up.
--(b) You can derive traverseWithKey_ from foldMapWithKey, e.g. as follows:
newtype Traverse_ f = Traverse_ { runTraverse_ :: f () }
instance Applicative f => Monoid (Traverse_ f) where
mempty = Traverse_ (pure ())
Traverse_ a `mappend` Traverse_ b = Traverse_ (a *> b)
traverseWithKey_ :: Applicative f => (k -> a -> f ()) -> M.Map k a -> f ()
traverseWithKey_ f = runTraverse_ .
foldMapWithKey (\k x -> Traverse_ (void (f k x)))