• Choose a category
• All
• Classic-Fiction

Almost As Good: Association Lists

There are many ways to achieve key/value mappings. One of them is the association list. Association lists (also called dictionaries) are lists that are used to store key/value pairs where ordering doesn’t matter. For instance, we might use an association list to store phone numbers, where phone numbers would be the values and people’s names would be the keys. We don’t care in which order they’re stored; we just want to get the right phone number for the right person.

The most obvious way to represent association lists in Haskell would be by having a list of pairs. The first component in the pair would be the key, and the second component would be the value. Here’s an example of an association list with phone numbers:

phoneBook =

[("betty", "555-2938")

,("bonnie", "452-2928")

,("patsy", "493-2928")

,("lucille", "205-2928")

,("wendy", "939-8282")

,("penny", "853-2492")

]

Despite this seemingly odd indentation, this is just a list of pairs of strings.

The most common task when dealing with association lists is looking up some value by key. Let’s make a function that looks up some value given a key.

findKey :: (Eq k) => k -> [(k, v)] -> v

findKey key xs = snd . head . filter (\(k, v) -> key == k) $ xs

This is pretty simple. The function takes a key and a list, filters the list so that only matching keys remain, gets the first key/value pair that matches, and returns the value.

But what happens if the key we’re looking for isn’t in the association list? Hmm. Here, if a key isn’t in the association list, we’ll end up trying to get the head of an empty list, which throws a runtime error. We should avoid making our programs so easy to crash, so let’s use the Maybe data type. If we don’t find the key, we’ll return a Nothing. If we find it, we’ll return Just something, where something is the value corresponding to that key.

findKey :: (Eq k) => k -> [(k, v)] -> Maybe v

findKey key [] = Nothing

findKey key ((k,v):xs)

| key == x = Just v

| otherwise = findKey key xs

Look at the type declaration. It takes a key that can be equated and an association list, and then it maybe produces a value. Sounds about right.

This is a textbook recursive function that operates on a list. Base case, splitting a list into a head and a tail, recursive calls—they’re all there. This is the classic fold pattern, so let’s see how this would be implemented as a fold.

findKey :: (Eq k) => k -> [(k, v)] -> Maybe v

findKey key xs = foldr (\(k, v) acc -> if key == k then Just v else acc) Nothing xs

Note

It’s usually better to use folds for this standard list recursion pattern, rather than explicitly writing the recursion, because they’re easier to read and identify. Everyone knows it’s a fold when they see the foldr call, but it takes some more thinking to read explicit recursion.

ghci> findKey "penny" phoneBook

Just "853-2492"

ghci> findKey "betty" phoneBook

Just "555-2938"

ghci> findKey "wilma" phoneBook

Nothing

This works like a charm! If we have the girl’s phone number, we Just get the number; otherwise, we get Nothing.

Enter Data.Map

We just implemented the lookup function from Data.List. If we want the value that corresponds to a key, we need to traverse all the elements of the list until we find it.

It turns out that the Data.Map module offers association lists that are much faster, and it also provides a lot of utility functions. From now on, we’ll say we’re working with maps instead of association lists.

Because Data.Map exports functions that clash with the Prelude and Data.List ones, we’ll do a qualified import.

import qualified Data.Map as Map

Put this import statement into a script, and then load the script via GHCi.

We’re going to turn an association list into a map by using the fromList function from Data.Map. fromList takes an association list (in the form of a list) and returns a map with the same associations. Let’s play around a bit with fromList first:

ghci> Map.fromList [(3,"shoes"),(4,"trees"),(9,"bees")]

fromList [(3,"shoes"),(4,"trees"),(9,"bees")]