Since frequency counts are an important use of map-like data structures, I did a brief test of the available options. First using regular strings for input, and Data.Map.fromListWith - i.e. the operational bit being: freqs :: [String] -> M.Map String Int freqs = M.fromListWith (+) . map (,1) This runs on a 14M corpus consisting of King James Bible, collected works of Shakespeare, and War and Peace. ./freqstr1 +RTS -s 5,093,386,368 bytes allocated in the heap 2,682,667,904 bytes copied during GC 261,110,368 bytes maximum residency (20 sample(s)) 9,018,000 bytes maximum slop 623 MB total memory in use (10 MB lost due to fragmentation) ./freqstr1 +RTS -s 21.43s user 0.78s system 99% cpu 22.285 total Kinda expensive, 250MB to store word frequencies of 14MB text. Now, changing to freqs :: [String] -> M.Map String Int freqs = foldl' (\m w -> M.insertWith' (+) w 1 m) M.empty i.e. using strict insertion, avoiding the buildup of lazy thunks for the counts. ./freqstr2 +RTS -s -- strings, using strict insertion 4,754,110,096 bytes allocated in the heap 2,089,527,240 bytes copied during GC 27,039,112 bytes maximum residency (66 sample(s)) 613,192 bytes maximum slop 80 MB total memory in use (2 MB lost due to fragmentation) ./freqstr2 +RTS -s 17.48s user 0.13s system 99% cpu 17.665 total This reduced maximam memory consumption to one tenth, still bigger than input corpus, but clearly not too bad. A bit faster, too, in spite of probably doing more work. Using ByteStrings instead, first fromListWith: ./freq +RTS -s (Just 77432,113931) 3,880,059,568 bytes allocated in the heap 1,467,507,808 bytes copied during GC 174,573,752 bytes maximum residency (14 sample(s)) 8,222,600 bytes maximum slop 385 MB total memory in use (6 MB lost due to fragmentation) ./freq +RTS -s 14.26s user 0.49s system 99% cpu 14.798 total About half the memroy of Strings, and 25% faster. With strict insertion: ./freq2 +RTS -s -- map using strict insertion 3,761,614,312 bytes allocated in the heap 849,806,000 bytes copied during GC 23,950,328 bytes maximum residency (35 sample(s)) 2,376,904 bytes maximum slop 58 MB total memory in use (1 MB lost due to fragmentation) ./freq2 +RTS -s 11.14s user 0.13s system 99% cpu 11.295 total Parallel to the String case, this is a lot more frugal with memory, and 30% faster. Now, I tried Data.HashMap from the hashmap library: ./freqH1 +RTS -s -- hashmap using fromListWith 4,552,922,784 bytes allocated in the heap 2,990,287,536 bytes copied during GC 401,247,912 bytes maximum residency (14 sample(s)) 42,098,016 bytes maximum slop 957 MB total memory in use (15 MB lost due to fragmentation) ./freqH1 +RTS -s 15.68s user 1.53s system 99% cpu 17.277 total ./freqH2 +RTS -s -- hashmap using foldl' insertWith 4,518,146,968 bytes allocated in the heap 2,986,973,352 bytes copied during GC 394,502,832 bytes maximum residency (14 sample(s)) 41,020,040 bytes maximum slop 957 MB total memory in use (15 MB lost due to fragmentation) ./freqH2 +RTS -s 15.86s user 1.62s system 99% cpu 17.537 total HashMap doesn't provide a strict insertWith, so this is similar to the lazy insertions above. A bit worse, actually, probably due to the overhead of hashing. Then, I discovered that Johan's hashmap is a different library, and thought I'd try that too for completeness. ./freqHS +RTS -s -- hashmap strict (unordered-containers) 2,628,628,752 bytes allocated in the heap 945,571,872 bytes copied during GC 26,635,744 bytes maximum residency (32 sample(s)) 2,433,504 bytes maximum slop 66 MB total memory in use (1 MB lost due to fragmentation) ./freqHS +RTS -s 6.90s user 0.16s system 99% cpu 7.082 total Memory residency like the other strict versions, but really fast, probably due to faster comparisons of hash values vs comparisons of strings. Conclusion: make sure you are using a strict map, and if your keys are strings or otherwise have expensive comparisons, unordered-containers is the library for you. -k PS: I also tried mapping 'copy' on the input words to avoid storing large slices of the input, but it only worsened things: ./freqHS3 +RTS -s (Just 77432,113931) 3,109,585,024 bytes allocated in the heap 936,724,184 bytes copied during GC 87,831,888 bytes maximum residency (19 sample(s)) 8,835,440 bytes maximum slop 164 MB total memory in use (3 MB lost due to fragmentation) ./freqHS3 +RTS -s 12.71s user 0.31s system 99% cpu 13.060 total Perhaps if you managed to only copy new words it would look better? PPS: I tried to be careful juggling the results around, but there's always the possiblity of a mistake. Caveat lector! (Or should that be 'cave scriptor'?) PPPS: There are some small interface annoyances around, it'd be nice if I could experiment with this by only changing the imports. Would it be possible to agree on an interface to map-like structures? -- If I haven't seen further, it is by standing in the footprints of giants