Data.Map
Map is a balanced tree
Data.Map is a dictionary from keys to values, kept as a balanced tree. The keys must be Ord, and that order is what every operation uses:
empty :: Map k a
lookup :: Ord k => k -> Map k a -> Maybe a
insert :: Ord k => k -> a -> Map k a -> Map k a
toList :: Map k a -> [(k, a)]
A lookup is logarithmic in the size of the map, and toList gives the pairs in ascending key order, which is why a map is also a sorted report waiting to be printed. The module comes in two flavours: Data.Map.Strict, where a value is evaluated when it is inserted, and Data.Map.Lazy, which stores a thunk. The strict one is the right default for counters.
fromList, lookup and insert
fromListWith builds a map from pairs and combines the values of equal keys. The program counts occurrences with it and then reads and writes the map:
module Main (main) where
import qualified Data.Map.Strict as Map
counts :: Map.Map String Int
counts = Map.fromListWith (+) [("a", 1), ("b", 1), ("a", 1), ("c", 1)]
main :: IO ()
main = do
print counts
print (Map.lookup "a" counts)
print (Map.lookup "z" counts)
print (Map.insert "d" 5 counts)
print (Map.adjust (+ 10) "a" counts)
print (Map.toList counts)
print (Map.member "b" counts)
print (Map.size counts)
ghc -Wall -O1 -o counts counts.hs
./counts
fromList [("a",2),("b",1),("c",1)]
Just 2
Nothing
fromList [("a",2),("b",1),("c",1),("d",5)]
fromList [("a",12),("b",1),("c",1)]
[("a",2),("b",1),("c",1)]
True
3
The Show instance prints fromList [...] in key order, and that is also what toList gives. insert and adjust returned a new map and left counts alone: the value is immutable, so the fifth line shows the result of the change and the sixth the original. Every update is a new tree that shares most of its nodes with the old one.
insertWith and adjust
The update functions save a lookup and an insert:
- insertWith f key value inserts the value, or combines it with the value already there using f.
- adjust f key changes an existing value and does nothing if the key is missing.
- alter f key is the general form: the function sees a Maybe and returns one, so it can delete.
- delete, union and difference work on whole maps.
module Main (main) where
import qualified Data.Map.Strict as Map
type Inventory = Map.Map String Int
apply :: String -> Int -> Inventory -> Inventory
apply = Map.insertWith (+)
main :: IO ()
main = do
let inventory = foldr (uncurry apply) Map.empty [("apple", 3), ("pear", 2), ("apple", 4)]
print inventory
print (Map.lookupMin inventory)
print (Map.lookupMax inventory)
print (Map.keys inventory)
print (Map.elems inventory)
print (Map.mapMaybe keepEven inventory)
where
keepEven n
| even n = Just (n * 10)
| otherwise = Nothing
ghc -Wall -O1 -o inventory inventory.hs
./inventory
fromList [("apple",7),("pear",2)]
Just ("apple",7)
Just ("pear",2)
["apple","pear"]
[7,2]
fromList [("pear",20)]
The two apple rows were added by insertWith (+) and the result is one row with 7. mapMaybe changed the values and dropped the entry of apple, because 7 is odd, which is how a filter and a map happen in one pass. A missing key gives Nothing from lookup and a no-op from adjust; the type never lets you forget the missing case.
A price table that may fail
A table of prices and a list of items: the total is a traverse over the lookups, so one unknown item fails the whole order with its name:
module Main (main) where
import qualified Data.Map.Strict as Map
prices :: Map.Map String Int
prices = Map.fromList [("tea", 3), ("coffee", 5), ("cake", 4)]
total :: [String] -> Either String Int
total items = sum <$> traverse price items
where
price item =
case Map.lookup item prices of
Nothing -> Left ("unknown item: " ++ item)
Just cost -> Right cost
main :: IO ()
main = do
print (total ["tea", "cake"])
print (total ["tea", "soup"])
print (Map.map (* 2) prices)
print (Map.union prices (Map.fromList [("tea", 9), ("juice", 6)]))
ghc -Wall -O1 -o prices prices.hs
./prices
Right 7
Left "unknown item: soup"
fromList [("cake",8),("coffee",10),("tea",6)]
fromList [("cake",4),("coffee",5),("juice",6),("tea",3)]
Map.union is left-biased: the first map wins for a key that both have, which is why tea is still 3 and not 9. That bias is the documented behaviour and the reason a default map is written as the second argument of a union with the specific map first. With a map of a few thousand keys the difference between a list lookup and a map lookup is the difference between a scan and a handful of comparisons.
Exercises
- Count the words of a sentence in a Map String Int and print the three most frequent.
- Delete a key with alter and check the result with member.
- Build two maps and print Map.difference in both directions.
- Explain why the keys of a Map must be Ord and not only Eq.
- Use Map.fromListWith max on pairs with repeated keys and say which value survives.
- Change the price table so that an item has a quantity and the total multiplies.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What must the key type of a
Mapbe?Answer
An instance of
OrdThe map is a balanced search tree, so it needs an ordering on the keys.
-
What does
Map.lookupreturn for a missing key?Answer
NothingThe result is a Maybe, so the missing case is in the type and cannot be forgotten.
-
What does
fromListWith (+)do with duplicate keys?Answer
Combines their values with +
The function is applied to the old and the new value of a repeated key.
-
What does this program print?
module Main (main) where import qualified Data.Map.Strict as Map main :: IO () main = print (Map.toList (Map.fromList [(2, "b"), (1, "a")] :: Map.Map Int String))Answer
[(1,"a"),(2,"b")]
toList gives the pairs in ascending key order, whatever the order of the input.
-
What does
Map.union a bdo for a key present in both maps?Answer
Keeps the value from the first map
The union is left-biased, so the first map wins.
-
What does this program print?
module Main (main) where import qualified Data.Map.Strict as Map main :: IO () main = print (Map.lookup 2 (Map.fromList [(1, "a"), (2, "b")] :: Map.Map Int String))Answer
Just "b"
The key 2 is present, so the lookup gives its value wrapped in Just.
-
What does
Data.Map.Strictdo differently fromData.Map.Lazy?Answer
It evaluates the value when it is inserted
The strict variant avoids a chain of thunks in the values, which matters for counters and accumulators.
-
What does
Map.adjust f keydo when the key is missing?Answer
Nothing, it returns the map unchanged
adjust only changes an existing entry; insertWith or alter is the function that can add one.
-
What is the cost of one lookup in a map of n keys?
Answer
Logarithmic in n
The balanced tree has a height of about log n, so a lookup follows that many nodes.
-
What does
Map.mapMaybe f mreturn?Answer
A map with the values changed and the Nothing entries dropped
The function sees each value and can keep a changed one or drop the entry, as the inventory program showed.
The code on this page was built with GHC 9.10.3 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev