An invariant is a rule that every valid value must satisfy. For an associative map, the rule is simple: each key may appear only once. A plain list of key-value pairs can break that rule, such as [(1,1), (1,2)], leaving map operations unable to give a dependable answer for key 1. section 5.2.2
Make invalid states harder to create by wrapping the list in an AssocMap newtype and hiding its constructor. Code outside the module can use the AssocMap type, but cannot pattern match on it or build arbitrary values from its underlying list. This keeps representation details private and makes the module responsible for preserving the rule. section 5.2.2 section 5.2.3
Listing 5.4 The module structure for AssocMap
module Data.AssocMap
( AssocMap, #1
member, #2
alter, #2
)
where
newtype AssocMap k v = AssocMap [(k, v)] #3
member :: Eq k => k -> AssocMap k v -> Bool
member key (AssocMap xs) = member' key xs #4
where #5
member' :: Eq k => k -> [(k, v)] -> Bool
member' _ [] = False
member' x ((x', _) : xs)
| x' == x = True
| otherwise = member' x xs
alter :: Eq k => (Maybe v -> Maybe v) -> k -> AssocMap k v -> AssocMap k v
alter f key (AssocMap xs) = AssocMap (alter' f key xs) #4
where #6
alter' :: Eq k => (Maybe v -> Maybe v) -> k -> [(k, v)] -> [(k, v)]
alter' f key [] =
case f Nothing of
Nothing -> []
Just value -> [(key, value)]
alter' f key ((key', value') : xs)
| key == key' =
case f (Just value') of
Nothing -> xs
Just value -> (key, value) : xs
| otherwise =
(key', value') : alter' f key xs
The module exports the AssocMap type and selected operations while keeping the AssocMap constructor private; internal functions may still unwrap and rebuild the representation. section 5.2.2
Preserve the unique-key invariant by exposing operations that control every modification:
- Use empty to create a map with no entries. section 5.2.2
- Use alter as the central update operation; delete and insert are defined through it. section 5.2.2
- Use member, lookup, or findWithDefault to inspect a map without exposing its list. section 5.2.2 section 5.2.3
A protected associative map
After inserting 'b' with "Hello" and 'a' with "World", the map can be displayed as AssocMap [('b',"Hello"),('a',"World")]. Deleting 'a' produces AssocMap []. These operations preserve the map rule because clients use insert and delete rather than constructing the underlying list directly. section 5.2.3
This design supports later graph construction: a graph can rely on maps whose keys are well-formed because map creation and modification pass through the protected API. section 5.0 section 5.2.3
