A lookup operation searches an associative list for a key and returns its associated value as Maybe: Just value when found, or Nothing when absent. In an AssocMap, it wraps recursive list traversal behind the map interface. section 5.2.3
The operation supports several practical design choices:
- Match each key-value pair recursively, stopping at the first equal key. section 5.2.3
- Handle absence explicitly with Nothing, or convert it to a supplied fallback using findWithDefault. section 5.2.3
- Avoid a naming collision with Prelude.lookup by hiding the imported function or qualifying occurrences with a module name. section 5.2.3
Listing 5.6 Definitions for lookup functions on maps built from associated lists
lookup :: (Eq k) => k -> AssocMap k v -> Maybe v
lookup key (AssocMap xs) = lookup' key xs #1
where
lookup' _ [] = Nothing #2
lookup' key ((key', value) : xs) #3
| key == key' = Just value #3
| otherwise = lookup' key xs #3
findWithDefault :: (Eq k) => v -> k -> AssocMap k v -> v
findWithDefault defaultValue key map =
case lookup key map of
Nothing -> defaultValue #4
Just value -> value #5
The complete definitions show the Maybe result, recursive traversal, equality constraint, and default-value wrapper. section 5.2.3
Performance in a graph application
Profiling a ladder-game program reveals that lookup consumes more than half of the runtime. Because each operation may traverse the entire associative list, larger dictionaries and graphs make repeated lookups slower; replacing the underlying representation becomes the optimization target. section 6.3.1
