Examples.MultiMap.Class

Provides the MultiMap class, which models a total relation from unique keys to sets of values.

Documentation

class (Eq (m k v), Ord k, Ord v) => MultiMap m k v where

Models a total relation from unique keys to sets of values.

Methods

fromList :: [(k, Set v)] -> m k v

Constructs a multimap from a list of key to value set mappings.

Removing empty sets from the input list does not affect the result:

fromList ≡ fromList . filter ((/= Set.empty) . snd)

toList :: m k v -> [(k, Set v)]

Converts a multimap to a list of key to value-set mappings.

Removing empty sets from the output list does not affect the result:

toList ≡ filter ((/= Set.empty) . snd) . toList

The resulting list can be used to reconstruct the original multimap:

fromList . toList ≡ id

empty :: m k v

Constructs an empty multimap.

empty ≡ fromList []

lookup :: k -> m k v -> Set v

Returns the set of values associated with a given key.

lookup k (fromList kvs) ≡ foldMap snd (filter ((== k) . fst) kvs)

null :: m k v -> Bool

Indicates whether or not a multimap is empty.

null m ≡ (∀ k. lookup k m == Set.empty)

nonNull :: m k v -> Bool

Indicates whether or not a multimap is non-empty.

nonNull m ≡ (∃ k. lookup k m /= Set.empty)

nonNullKey :: k -> m k v -> Bool

Returns True iff. the given key is associated with a non-empty set.

nonNullKey k m ≡ (lookup k m /= Set.empty)

nonNullKeys :: m k v -> Set k

Returns the set of keys that are associated with non-empty sets.

all (`nonNullKey` m) (nonNullKeys m)

nonNullCount :: m k v -> Int

Indicates how many keys are associated with non-empty sets.

nonNullCount m ≡ Set.size (nonNullKeys m)

isSubmapOf :: m k v -> m k v -> Bool

Indicates whether or not the first map is a sub-map of the second.

m1 `isSubmapOf` m2 ≡ ∀ k. (lookup k m1 `Set.isSubsetOf` lookup k m2)

update :: k -> Set v -> m k v -> m k v

Updates the set of values associated with a given key.

lookup k1 (update k2 vs m) ≡
    if k1 == k2
    then vs
    else lookup k1 m

insert :: k -> Set v -> m k v -> m k v

Inserts values into the set of values associated with a given key.

lookup k1 (insert k2 vs m) ≡
    if k1 == k2
    then lookup k1 m `Set.union` vs
    else lookup k1 m

remove :: k -> Set v -> m k v -> m k v

Removes values from the set of values associated with a given key.

lookup k1 (remove k2 vs m) ≡
    if k1 == k2
    then lookup k1 m `Set.difference` vs
    else lookup k1 m

union :: m k v -> m k v -> m k v

Computes the union of two multimaps.

Instances must satisfy the following properties:

Idempotence

union m m ≡ m

Identity

union empty m     ≡ m
union m     empty ≡ m

Commutativity

union m1 m2 ≡ union m2 m1

Associativity

union        m1 (union m2  m3) ≡
union (union m1        m2) m3

Containment

m1 `isSubmapOf` union m1 m2
m2 `isSubmapOf` union m1 m2

Distributivity

lookup k (union m1 m2) ≡ Set.union (lookup k m1)
                                   (lookup k m2)

intersection :: m k v -> m k v -> m k v

Computes the intersection of two multimaps.

Instances must satisfy the following properties:

Idempotence

intersection m m ≡ m

Identity

intersection empty m     ≡ empty
intersection m     empty ≡ empty

Commutativity

intersection m1 m2 ≡ intersection m2 m1

Associativity

intersection               m1 (intersection m2  m3) ≡
intersection (intersection m1               m2) m3

Containment

intersection m1 m2 `isSubmapOf` m1
intersection m1 m2 `isSubmapOf` m2

Distributivity

lookup k (intersection m1 m2) ≡ Set.intersection (lookup k m1)
                                                 (lookup k m2)

Instances

(Ord k, Ord v) => MultiMap MultiMap1 k v

Defined in Examples.MultiMap.Instances.MultiMap1

Methods

fromList :: [(k, Set v)] -> MultiMap1 k v

toList :: MultiMap1 k v -> [(k, Set v)]

empty :: MultiMap1 k v

lookup :: k -> MultiMap1 k v -> Set v

null :: MultiMap1 k v -> Bool

nonNull :: MultiMap1 k v -> Bool

nonNullKey :: k -> MultiMap1 k v -> Bool

nonNullKeys :: MultiMap1 k v -> Set k

nonNullCount :: MultiMap1 k v -> Int

isSubmapOf :: MultiMap1 k v -> MultiMap1 k v -> Bool

update :: k -> Set v -> MultiMap1 k v -> MultiMap1 k v

insert :: k -> Set v -> MultiMap1 k v -> MultiMap1 k v

remove :: k -> Set v -> MultiMap1 k v -> MultiMap1 k v

union :: MultiMap1 k v -> MultiMap1 k v -> MultiMap1 k v

intersection :: MultiMap1 k v -> MultiMap1 k v -> MultiMap1 k v

(Ord k, Ord v) => MultiMap MultiMap2 k v

Defined in Examples.MultiMap.Instances.MultiMap2

Methods

fromList :: [(k, Set v)] -> MultiMap2 k v

toList :: MultiMap2 k v -> [(k, Set v)]

empty :: MultiMap2 k v

lookup :: k -> MultiMap2 k v -> Set v

null :: MultiMap2 k v -> Bool

nonNull :: MultiMap2 k v -> Bool

nonNullKey :: k -> MultiMap2 k v -> Bool

nonNullKeys :: MultiMap2 k v -> Set k

nonNullCount :: MultiMap2 k v -> Int

isSubmapOf :: MultiMap2 k v -> MultiMap2 k v -> Bool

update :: k -> Set v -> MultiMap2 k v -> MultiMap2 k v

insert :: k -> Set v -> MultiMap2 k v -> MultiMap2 k v

remove :: k -> Set v -> MultiMap2 k v -> MultiMap2 k v

union :: MultiMap2 k v -> MultiMap2 k v -> MultiMap2 k v

intersection :: MultiMap2 k v -> MultiMap2 k v -> MultiMap2 k v

(Ord k, Ord v) => MultiMap MultiMap3 k v

Defined in Examples.MultiMap.Instances.MultiMap3

Methods

fromList :: [(k, Set v)] -> MultiMap3 k v

toList :: MultiMap3 k v -> [(k, Set v)]

empty :: MultiMap3 k v

lookup :: k -> MultiMap3 k v -> Set v

null :: MultiMap3 k v -> Bool

nonNull :: MultiMap3 k v -> Bool

nonNullKey :: k -> MultiMap3 k v -> Bool

nonNullKeys :: MultiMap3 k v -> Set k

nonNullCount :: MultiMap3 k v -> Int

isSubmapOf :: MultiMap3 k v -> MultiMap3 k v -> Bool

update :: k -> Set v -> MultiMap3 k v -> MultiMap3 k v

insert :: k -> Set v -> MultiMap3 k v -> MultiMap3 k v

remove :: k -> Set v -> MultiMap3 k v -> MultiMap3 k v

union :: MultiMap3 k v -> MultiMap3 k v -> MultiMap3 k v

intersection :: MultiMap3 k v -> MultiMap3 k v -> MultiMap3 k v

(Ord k, Ord v) => MultiMap MultiMap4 k v

Defined in Examples.MultiMap.Instances.MultiMap4

Methods

fromList :: [(k, Set v)] -> MultiMap4 k v

toList :: MultiMap4 k v -> [(k, Set v)]

empty :: MultiMap4 k v

lookup :: k -> MultiMap4 k v -> Set v

null :: MultiMap4 k v -> Bool

nonNull :: MultiMap4 k v -> Bool

nonNullKey :: k -> MultiMap4 k v -> Bool

nonNullKeys :: MultiMap4 k v -> Set k

nonNullCount :: MultiMap4 k v -> Int

isSubmapOf :: MultiMap4 k v -> MultiMap4 k v -> Bool

update :: k -> Set v -> MultiMap4 k v -> MultiMap4 k v

insert :: k -> Set v -> MultiMap4 k v -> MultiMap4 k v

remove :: k -> Set v -> MultiMap4 k v -> MultiMap4 k v

union :: MultiMap4 k v -> MultiMap4 k v -> MultiMap4 k v

intersection :: MultiMap4 k v -> MultiMap4 k v -> MultiMap4 k v