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:

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

  1. Count the words of a sentence in a Map String Int and print the three most frequent.
  2. Delete a key with alter and check the result with member.
  3. Build two maps and print Map.difference in both directions.
  4. Explain why the keys of a Map must be Ord and not only Eq.
  5. Use Map.fromListWith max on pairs with repeated keys and say which value survives.
  6. 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.

  1. What must the key type of a Map be?

    Answer

    An instance of Ord

    The map is a balanced search tree, so it needs an ordering on the keys.

  2. What does Map.lookup return for a missing key?

    Answer

    Nothing

    The result is a Maybe, so the missing case is in the type and cannot be forgotten.

  3. 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.

  4. 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.

  5. What does Map.union a b do 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.

  6. 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.

  7. What does Data.Map.Strict do differently from Data.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.

  8. What does Map.adjust f key do 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.

  9. 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.

  10. What does Map.mapMaybe f m return?

    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