A map associates each key with a value. A simple Haskell representation is an associative list: a list of two-element tuples, such as line numbers paired with lines. Unlike a plain list of values, it makes the mapping explicit while retaining list order and the ability to grow. section 4.1.1
type NumberedLines = [(Int, String)]
A type synonym can name a list of key-value tuples as a mapping from line numbers to text. section 4.1.1
Maps are useful when a project needs to relate values: numbered lines to their contents, or graph nodes to the nodes connected to them. Keys should occur only once, so insertion first needs a key-membership check. Matching a key with `==` means the key type needs the `Eq` constraint. section 5.1.2 section 5.0
`zip` constructs an associative list by pairing two lists element by element; it stops when either input ends. `unzip` separates pairs again, but cannot recover values discarded when `zip` received lists of unequal length. These general functions avoid writing specialized recursive code for assembling or taking apart maps. section 4.3.3
Pairing line numbers with lines
`zip [1,2,3] ["Hello", "World", "!"]` produces `[(1,"Hello"),(2,"World"),(3,"!")]`. The first list supplies keys and the second supplies values; an empty input produces an empty map. section 4.3.3
A single higher-order `alter` operation can centralize map changes. It receives the current value as `Nothing` when a key is absent or `Just value` when present. Returning `Nothing` removes an existing mapping; returning `Just value` adds or replaces one. Because the map is a list, the operation returns a new list rather than changing one in place. section 5.2 section 5.2.1
Listing 5.3 The function to modify an associative list
alter :: Eq k => (Maybe v -> Maybe v) -> k -> [(k, v)] -> [(k, v)]
alter f key [] = #1
case f Nothing of #2
Nothing -> [] #3
Just value -> [(key, value)] #4
alter f key ((key', value') : xs) #5
| key == key' = #6
case f (Just value') of #7
Nothing -> xs #8
Just value -> (key, value) : xs #9
| otherwise =
(key', value') : alter f key xs #10
`alter` searches recursively, then uses `Maybe` to decide whether to preserve, delete, add, or replace a key-value pair. section 5.2
The same `alter` function supports several common operations:
- Remove a key by returning `Nothing`. section 5.2.1
- Add a key by returning `Just` with a new value when it is absent. section 5.2.1
- Update only an existing key by returning `Nothing` for a missing value and `Just` for a present one. section 5.2.1
Associative lists are versatile and practical when performance is not important, but lookup may have to traverse the entire list. In a graph search over a larger dictionary, profiling shows lookup consuming much of the runtime, so this representation may need replacement with a faster map. section 4.1.1 section 6.3.1
