Haskell Data.Map Tutorial for Fast Key Value Lookups
You reached for a list of pairs and the lookup function, and now a report that should take a second takes forty.

You reached for a list of pairs and the lookup function, and now a report that should take a second takes forty. Haskell Data.Map is the fix most people need, but the introductions show three functions and stop right before the parts that trip you up: strictness, the qualified import dance, and choosing between insertWith, alter and adjust.
This tutorial assumes you can already write a small program and read a type signature. If that still feels shaky, the guide on getting started with Haskell as a complete beginner covers the ground you need first. Everything below uses the containers package, which ships with GHC; just add it to build-depends.
Why Haskell Data.Map beats a list of pairs
A list of pairs with lookup is a linear scan. With 10 keys you will never notice. With 200,000 customer records, every lookup walks the list from the front, and a loop that does one lookup per record becomes quadratic. On a laptop that can mean the difference between 0.3 seconds and several minutes.
Data.Map is a balanced binary search tree. Lookup, insert and delete are all O(log n), which for 200,000 keys is about 18 comparisons. The keys only need an Ord instance, so strings, numbers, tuples and your own types with a derived Ord all work. If you want a refresher on how that constraint works, the post on type classes in Haskell with real examples explains what deriving Ord actually gives you.
The map is also immutable. Inserting a key returns a new map that shares almost all of its structure with the old one, so keeping the previous version around costs very little memory.
Importing it the way everyone else does
Data.Map exports functions called filter, map, lookup, foldr and null, which clash with the Prelude. The standard answer is two import lines: an unqualified import of just the Map type, and a qualified import of the module under the short name M or Map. You then write M.insert, M.lookup and M.fromList, while the bare type name stays readable in signatures.
Pick one alias per project and keep it.
The five operations you will use every day
- M.fromList builds a map from a list of pairs. If a key appears twice, the last value wins, which surprises people who expected an error.
- M.lookup returns a Maybe. Pattern match on it, or use M.findWithDefault when a missing key has an obvious fallback such as 0.
- M.insert adds or replaces a key. It never fails and never warns you that it overwrote something.
- M.insertWith takes a combining function for the case where the key already exists. Counting words is the classic example: insertWith (+) word 1 adds one to an existing count or starts a new one at 1.
- M.toList gives the pairs back in ascending key order, every time. That ordering is guaranteed, so you can rely on it for stable output in reports and test snapshots.
When a lookup can fail, keep the Maybe flowing instead of unwrapping it early. Mixing Maybe with your error types is easier than it looks, and the article on Haskell Either for error handling without exceptions shows how to turn a missing key into a descriptive error with a single helper.
Updating values without reading them first
Lookup, compute, then insert walks the tree twice. These functions do the read and write in one pass.
| Function | What it does | Missing key |
|---|---|---|
| M.adjust | Applies a function to an existing value | Map returned unchanged |
| M.insertWith | Combines a new value with the old one | Inserts the new value |
| M.alter | Receives Maybe old value, returns Maybe new value | You decide, including delete |
| M.update | Returns Nothing to delete, Just to replace | Map returned unchanged |
M.alter is the general one. Its function gets Nothing when the key is absent and Just v when present, and returning Nothing removes the key. That lets a stock counter decrement a quantity and drop the item at zero in one expression. Still, prefer adjust or insertWith when they fit.
The advice to always use Data.Map.Strict is not quite right
Most guides now say: import Data.Map.Strict and never think about it again. For counters and running totals that is correct. A lazy map that receives insertWith (+) a million times stores a chain of a million unevaluated additions, and your program can climb past 1 GB of memory before printing anything. A heap profile of that program shows one tall band of thunks growing until the very end.
But strict is not free. Data.Map.Strict evaluates each value to weak head normal form on insert, which means the outer constructor only. A strict map of lists still holds lazy list contents, and a strict map of tuples still holds lazy fields inside each tuple.
And sometimes lazy is what you want. A memo table where each value is an expensive computation that most callers never request is a perfect lazy map: you build it with fromList over every possible key, and only the entries someone looks up ever get computed. With the strict module, building that table would compute every entry up front.
The rule I give is simpler than "always strict". Use Data.Map.Strict when values are numbers or small records you update often. Use the lazy module on purpose, with a comment, when deferred values are the point. And if your values contain fields, give those fields strictness annotations so the strictness reaches all the way down.
Folding, filtering and combining maps
M.foldrWithKey and M.foldlWithKey let you walk the map with access to both key and value, again in ascending key order. For totals, M.foldl' with the strict accumulator avoids the same thunk build up described above.
M.partition splits a map into the entries that pass a test and those that fail, which separates valid and invalid records in one pass.
For two maps, M.union is left biased: when both contain a key, the left value wins. M.unionWith takes a function to merge clashes, so merging two weekly sales maps with unionWith (+) gives a fortnight total.
Range queries are where the ordered tree shines. M.split cuts a map at a key into everything below and everything above, and M.lookupLE finds the largest key at or below a target. That last one is ideal for price bands or time series where you want the most recent reading before a given timestamp.
When Data.Map is the wrong container
If your keys are Int, use Data.IntMap. It has the same interface and is usually faster, often by 20 to 40 percent on lookups in benchmarks with dense integer keys. If you never need ordering and your keys hash well, the unordered-containers package offers HashMap, which can beat Data.Map on large string keys. For membership without values, use Data.Set.
For a few dozen entries that never change, a list of pairs is honestly fine.
Frequently asked questions
Is Haskell Data.Map a hash map?
No. It is a size balanced binary tree ordered by the keys, so keys need Ord rather than Hashable. That is why toList returns sorted pairs and why range functions like split and lookupLE exist. For a hash based structure, use HashMap from unordered-containers.
How do I get a value from a Map without a Maybe?
Use M.findWithDefault with a sensible fallback, or the operator M.! if you are certain the key exists. The bang operator throws an error on a missing key, so keep it for cases where absence is truly a bug. Most of the time a Maybe or a default is the safer choice.
Why does my Data.Map program use so much memory?
Usually because the lazy module is storing unevaluated thunks from repeated insertWith or adjust calls. Switch to Data.Map.Strict and use foldl' for totals. If memory is still high, check whether your values are records or tuples with lazy fields, and add strictness annotations to those fields.
More in Tutorials
Tutorials
Haskell Reader Monad Tutorial for App Configuration
You start a service with one configuration field, a database connection string.
Tutorials
Haskell Data.Vector Tutorial for Fast Numeric Arrays
Your program reads 8 million sensor readings, sums them, and takes nineteen seconds while resident memory climbs past 900 MB.
Tutorials
Haskell traverse and sequenceA for Everyday Code
You wrote a function that parses one line of a config file and hands back a Maybe Int.