MapTest extended with Shachaf's suggestion

MapTest2.hs

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

main :: IO ()
main = do
  t0 <- getCurrentTime
  let m0 = M.fromList (map (\i -> (i,i)) [1..1000000::Int])
  evaluate$ rnf m0 
  t1 <- getCurrentTime
  performGC
  s1 <- getGCStats  
  putStrLn$"Constructed map in "++show (diffUTCTime t1 t0)++"\n "++ show s1++"\n"
  let fn 500000 v = putStrLn "Got it!"
      fn _      _ = return ()

  -- Regular traverseWithKey uses 48MB
  -- traverseWithKey_ usse 200K of allocation:
  M.traverseWithKey_ fn m0
  t2 <- getCurrentTime
  performGC
  s2 <- getGCStats 
  putStrLn$"[traverseWithKey_] Consumed map in "++show (diffUTCTime t2 t1)++"\n "++ show s2++"\n"
  putStrLn$"Bytes allocated during consume:  "++show (bytesAllocated s2 - bytesAllocated s1)

  -- foldrWithKey uses 32MB allocation:
  M.foldrWithKey (\k a -> (fn k a >>)) (return ()) m0
  t3 <- getCurrentTime
  performGC
  s3 <- getGCStats 
  putStrLn$"[foldrWithKey] Consumed map in "++show (diffUTCTime t3 t2)++"\n "++ show s3++"\n"
  putStrLn$"Bytes allocated during consume:  "++show (bytesAllocated s3 - bytesAllocated s2)
  return ()

  M.foldrWithKey (\k a -> (fn k a >>)) (return ()) m0
  t4 <- getCurrentTime
  performGC
  s4 <- getGCStats 
  putStrLn$"[alternate traverseWithKey_] Consumed map in "++show (diffUTCTime t4 t3)++"\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)))

output.txt

Constructed map in 0.5413s
 GCStats {bytesAllocated = 168034848, numGcs = 323, maxBytesUsed = 72033480, numByteUsageSamples = 10, cumulativeBytesUsed = 242248208, bytesCopied = 411511480, currentBytesUsed = 72033480, currentBytesSlop = 0, maxBytesSlop = 897336, peakMegabytesAllocated = 149, mutatorCpuSeconds = 8.1987e-2, mutatorWallSeconds = 7.7435565e-2, gcCpuSeconds = 0.497924, gcWallSeconds = 0.553027456, cpuSeconds = 0.579911, wallSeconds = 0.630463021, parTotBytesCopied = 0, parMaxBytesCopied = 0}

Got it!
[traverseWithKey_] Consumed map in 0.111508s
 GCStats {bytesAllocated = 168250096, numGcs = 324, maxBytesUsed = 72114216, numByteUsageSamples = 11, cumulativeBytesUsed = 314362424, bytesCopied = 483559536, currentBytesUsed = 72114216, currentBytesSlop = 0, maxBytesSlop = 897336, peakMegabytesAllocated = 149, mutatorCpuSeconds = 0.102984, mutatorWallSeconds = 9.9839041e-2, gcCpuSeconds = 0.585911, gcWallSeconds = 0.640092837, cpuSeconds = 0.688895, wallSeconds = 0.739931878, parTotBytesCopied = 0, parMaxBytesCopied = 0}

Bytes allocated during consume:  215248
Got it!
[foldrWithKey] Consumed map in 0.116716s
 GCStats {bytesAllocated = 200369072, numGcs = 386, maxBytesUsed = 72114216, numByteUsageSamples = 12, cumulativeBytesUsed = 386476640, bytesCopied = 555626312, currentBytesUsed = 72114216, currentBytesSlop = 0, maxBytesSlop = 897336, peakMegabytesAllocated = 149, mutatorCpuSeconds = 0.131979, mutatorWallSeconds = 0.129205453, gcCpuSeconds = 0.673898, gcWallSeconds = 0.727731758, cpuSeconds = 0.805877, wallSeconds = 0.856937211, parTotBytesCopied = 0, parMaxBytesCopied = 0}

Bytes allocated during consume:  32118976
Got it!
[alternate traverseWithKey_] Consumed map in 0.116897s
 GCStats {bytesAllocated = 232488048, numGcs = 448, maxBytesUsed = 72114216, numByteUsageSamples = 13, cumulativeBytesUsed = 386591064, bytesCopied = 555691952, currentBytesUsed = 114424, currentBytesSlop = 0, maxBytesSlop = 897336, peakMegabytesAllocated = 149, mutatorCpuSeconds = 0.160975, mutatorWallSeconds = 0.158479698, gcCpuSeconds = 0.674897, gcWallSeconds = 0.740772793, cpuSeconds = 0.835872, wallSeconds = 0.899252491, parTotBytesCopied = 0, parMaxBytesCopied = 0}

Bytes allocated during consume:  32118976
     232,624,368 bytes allocated in the heap
     555,695,648 bytes copied during GC
      72,114,216 bytes maximum residency (14 sample(s))
         897,336 bytes maximum slop
             149 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
  Gen  0       435 colls,     0 par    0.17s    0.18s     0.0004s    0.0013s
  Gen  1        14 colls,     0 par    0.50s    0.56s     0.0399s    0.1160s

  INIT    time    0.00s  (  0.00s elapsed)
  MUT     time    0.16s  (  0.16s elapsed)
  GC      time    0.67s  (  0.74s elapsed)
  EXIT    time    0.00s  (  0.00s elapsed)
  Total   time    0.84s  (  0.90s elapsed)

  %GC     time      80.7%  (82.3% elapsed)

  Alloc rate    1,445,096,244 bytes per MUT second

  Productivity  19.3% of total user, 17.9% of total elapsed