Maps

Maps are the first associative data type in our Data Structures Series. This means they have two parameters, unlike lists and sets. Let's see how they work!

For a more in depth look at this and other data structure types, make sure to look at our eBooks page!

What are Maps good for?

Maps are your most basic associative data structure. They are your go-to whenever you need to associate the "values" in your data structure with a particular "key". Note that the "key" type must be "Ordered" (Ord typeclass). Thus certain max/min operations are efficient with Maps, but primarily with regard to the maximum or minimum "key" in the map, rather than the max or min "value".

Maps have many similarities to sets. Their API is similar, and they also use a binary tree as the underlying structure, resulting in logarithmic time for most operations.

What are Maps not as good for?

As with sets, maps will not keep track of the order in which you inserted the different elements. You need either a normal list or a sequence to do that.

Map Parameters and Constraints

Maps have two type parameters. The first is a "key" type. The second is the "value" type. The "value" is associated with the "key", so you can use the key to look up the value. The key type must satisfy the Ord type class, since maps rely on binary trees just like sets. There are no constraints on the value type.

How do I create a Map?

Maps follow the same initialization pattern as sets, using empty, singleton, and fromList as the most common paths. Note however, that with singleton, the initial key and value are separate arguments, whereas in fromList, each key and value is combined in a tuple.

empty :: Map k v
singleton :: k -> v -> Map k v
fromList :: [(k, v)] -> Map k v

How do I get the size of a Map?

Use Data.Map.size. This operation is constant time, O(1).

size :: Map k v -> Int

How do I insert elements into a Map?

You can add an item to a map with the insert function. The new key and value are separate arguments. If the key already exists in the map, the previous value is overwritten by the new value. This operation is O(log n).

insert :: k -> v -> Map k v -> Map k v

How do I access Map elements?

If you have a key value, you can retrieve the associated value with the lookup function. It will be wrapped as a Maybe value. If the key exists in the map, then you will get a Just result. If not, you will get Nothing.

lookup :: k -> Map k v -> Maybe v

If you are sure the key exists, you can also use the "bang" operator (!). This way, you will get the value directly, rather than having it wrapped in a Maybe value. However, this will throw an error if the value doesn't exist and crash your program.

(!) :: Map k v -> k -> v

As with sets, maps provide a member function. This allows you to quickly check if a particular key already exists in your map.

member :: k -> Map k v -> Bool

You can also find the minimum and maximum key/value pair with a Map, but these functions will error out if the map is empty. Remember, this means the max/min "key" in the map, not the max/min "value".

findMin :: Map k v -> (k, v)
findMax :: Map k v -> (k, v)

As with sets, you can also use toList to get a normal list of key value pairs.

toList :: Map k v -> [(k, v)]

How do I delete elements from a Map?

You can remove elements from a map with delete, using the key as an argument. This operation is O(log n).

delete :: k -> Map k v -> Map k v

You can also delete the minimum or maximum key if you would like. These operations are also logarithmic in time.

deleteMin :: Map k v -> Map k v
deleteMax :: Map k v -> Map k v

How do I combine Maps?

Maps have many of the same combination operators as sets. As always, these perform the operation based on the keys, not the values.

union :: Map k v -> Map k v -> Map k v
unions :: (Foldable f) => f (Map k v) -> Map k v
intersection :: Map k v -> Map k v -> Map k v
difference :: Map k v -> Map k v -> Map k v
(\\) = difference

These aren't used quite as commonly as they are with sets though, especially the difference operators. An important note is that the union functions are left-biased. If a key exists in both input maps, the value for the first (left) input will be used in the resulting map.

If you want more control, you can use the unionWith function. Instead of using a left-bias, this allows you to provide your own function as the first argument to resolve conflicts when both maps contain a key. Your function will take both values and determine which value to place in the new map.

unionWith :: (v -> v -> v) -> Map k v -> Map k v -> Map k v

Import Notes

You should import Map in a qualified way, except for the structure name. Depending on what other structures you're using, you can also import the lookup operator unqualified.

import Data.Map (Map, (!))
import qualified Data.Map as M

Conclusion

If you want to learn about more data structures in Haskell, make sure to head back to the series page! If you're following the order, the next structure to learn is the Hash Set!