Data Maps

Now that we are familiar with the standard type classes, we can look at one of their applications: First, the Map datastructure

Data.Map

The Data.Map module defines the Map type. Maps are search trees for key-value pairs. It is similar to the dictionaries you have seen in Python. One way to look at this is that a value of type Map k v is roughly the same as a value of type [(k,v)], a list of pairs. However, the operations on a map are more efficient than operations on a list.

Since Data.Map contains some function with the same names as Prelude functions, the namespace needs to be imported qualified:

import qualified Data.Map as Map

Now we can refer to the map type as Map.Map, and to various map functions like Map.insert. Here are the most important functions for maps:

-- Create a Map from a list of key-value pairs
Map.fromList :: Ord k => [(k, a)] -> Map.Map k a

-- Insert a value into a map. Overrides any previous value with the same key.
-- Returns a new map. Does not mutate the given map.
Map.insert :: Ord k => k -> a -> Map.Map k a -> Map.Map k a

-- Get a value from a map using a key. Returns Nothing if the key was not present in the map.
Map.lookup :: Ord k => k -> Map.Map k a -> Maybe a

-- An empty map
Map.empty :: Map.Map k a

The Ord constraint for the key type of the map is needed because maps are implemented as ordered binary search trees.

Note that like all Haskell values, maps are immutable meaning you can’t change a map once you define it. However, map operations like insert produce a new map. To perform multiple map operations you need to reuse the return value. Here’s a GHCi session operating on a map.

Prelude> import qualified Data.Map as Map
Prelude Map> values = Map.fromList [("z",3),("w",4)]
Prelude Map> Map.lookup "z" values
Just 3
Prelude Map> Map.lookup "banana" values
Nothing
Prelude Map> Map.insert "x" 7 values
fromList [("w",4),("x",7),("z",3)]
Prelude Map> values                                       -- note immutability!
fromList [("w",4),("z",3)]
Prelude Map> Map.insert "x" 1 (Map.insert "y" 2 values)   -- two insertions
fromList [("w",4),("x",1),("y",2),("z",3)]
Prelude Map>

Here’s an example of representing a bank as a Map String Int (map from account name to account balance), and withdrawing some money from an account:

withdraw :: String -> Int -> Map.Map String Int -> Map.Map String Int
withdraw account amount bank =
    case Map.lookup account bank of
    Nothing  -> bank                                   -- account not found, no change
    Just sum -> Map.insert account (sum-amount) bank   -- set new balance

Here’s how you might use the withdraw function in GHCi. Note how the maps get printed as fromList invocations. Also note how calling withdraw ... bank returns a new bank and doesn’t change the existing bank.

GHCi> bank = Map.fromList [("Bob",100),("Mike",50)]
GHCi> withdraw "Bob" 80 bank
fromList [("Bob",20),("Mike",50)]
GHCi> bank                         -- note immutability
fromList [("Bob",100),("Mike",50)]
GHCi> withdraw "Bozo" 1000 bank
fromList [("Bob",100),("Mike",50)]

Data.Map defines all sorts of useful higher-order functions for updating maps. We can rewrite the withdraw function using Data.Map.adjust:

withdraw :: String -> Int -> Map.Map String Int -> Map.Map String Int
withdraw account amount bank = Map.adjust (\x -> x-amount) account bank

Note! There are separate Data.Map.Strict and Data.Map.Lazy implementations. When you import Data.Map you get Data.Map.Lazy. You can find the documentation for all the Data.Map functions in the docs for Data.Map.Lazy. We won’t go into their differences here, but mostly you should use Data.Map.Strict in real code.

Exercises

All exercises can be found in Set4a and Set4b. Please pay attention in the title of the exercise in which file the exercises of this section can be found.

Exercises from 4a:

You can check your current points from the blue blob in the bottom-right corner of the page.