Safe Haskell | None |
---|---|

Language | Haskell2010 |

Maps with disjoint sets as the key. The type in this module can be roughly understood as:

DisjointMap k v ≈ Map (Set k) v

Internally, `DisjointMap`

is implemented like a disjoint set
but the data structure that maps representatives to their rank also holds the value
associated with that representative element. Additionally, it holds the set
of all keys that in the same equivalence class as the representative.
This makes it possible to implementat functions like `foldlWithKeys'`

efficiently.

- data DisjointMap k v
- empty :: DisjointMap k v
- singleton :: k -> v -> DisjointMap k v
- singletons :: Eq k => Set k -> v -> DisjointMap k v
- insert :: (Ord k, Monoid v) => k -> v -> DisjointMap k v -> DisjointMap k v
- union :: (Ord k, Monoid v) => k -> k -> DisjointMap k v -> DisjointMap k v
- lookup :: (Ord k, Monoid v) => k -> DisjointMap k v -> v
- lookup' :: Ord k => k -> DisjointMap k v -> Maybe v
- representative :: Ord k => k -> DisjointMap k v -> Maybe k
- representative' :: Ord k => k -> DisjointMap k v -> (Maybe k, DisjointMap k v)
- toLists :: DisjointMap k v -> [([k], v)]
- pretty :: (Show k, Show v) => DisjointMap k v -> String
- prettyList :: (Show k, Show v) => DisjointMap k v -> [String]
- foldlWithKeys' :: (a -> Set k -> v -> a) -> a -> DisjointMap k v -> a

# Documentation

data DisjointMap k v Source #

A map having disjoints sets of `k`

as keys and
`v`

as values.

Functor (DisjointMap k) Source # | |

Foldable (DisjointMap k) Source # | |

Traversable (DisjointMap k) Source # | |

(Ord k, Ord v) => Eq (DisjointMap k v) Source # | |

(Ord k, Ord v) => Ord (DisjointMap k v) Source # | |

(Show k, Ord k, Show v) => Show (DisjointMap k v) Source # | |

(Ord k, Monoid v) => Semigroup (DisjointMap k v) Source # | |

(Ord k, Monoid v) => Monoid (DisjointMap k v) Source # | |

(FromJSON k, FromJSON v, Ord k) => FromJSON (DisjointMap k v) Source # | |

(ToJSON k, ToJSON v) => ToJSON (DisjointMap k v) Source # | |

# Construction

empty :: DisjointMap k v Source #

The empty map

singleton :: k -> v -> DisjointMap k v Source #

Create a disjoint map with one key: a singleton set. O(1).

singletons :: Eq k => Set k -> v -> DisjointMap k v Source #

Create a disjoint map with one key. Everything in the
`Set`

argument is consider part of the same equivalence
class.

insert :: (Ord k, Monoid v) => k -> v -> DisjointMap k v -> DisjointMap k v Source #

Insert a key-value pair into the disjoint map. If the key is is already present in another set, combine the value monoidally with the value belonging to it. Otherwise, this creates a singleton set as a new key and associates it with the value.

union :: (Ord k, Monoid v) => k -> k -> DisjointMap k v -> DisjointMap k v Source #

Create an equivalence relation between x and y. If either x or y
are not already is the disjoint set, they are first created
as singletons with a value that is `mempty`

.

# Query

lookup :: (Ord k, Monoid v) => k -> DisjointMap k v -> v Source #

Find the value associated with the set containing
the provided key. If the key is not found, use `mempty`

.

lookup' :: Ord k => k -> DisjointMap k v -> Maybe v Source #

Find the value associated with the set containing the provided key.

representative :: Ord k => k -> DisjointMap k v -> Maybe k Source #

Find the set representative for this input. This function ignores the values in the map.

representative' :: Ord k => k -> DisjointMap k v -> (Maybe k, DisjointMap k v) Source #

Find the set representative for this input. Returns a new disjoint set in which the path has been compressed.

# Conversion

toLists :: DisjointMap k v -> [([k], v)] Source #

prettyList :: (Show k, Show v) => DisjointMap k v -> [String] Source #

foldlWithKeys' :: (a -> Set k -> v -> a) -> a -> DisjointMap k v -> a Source #

# Tutorial

The disjoint map data structure can be used to model scenarios where the key of a map is a disjoint set. Let us consider trying to find the lowest rating of our by town. Due to differing subcultures, inhabitants do not necessarily agree on a canonical name for each town. Consequently, the survey allows participants to write in their town name as they would call it. We begin with a rating data type:

`>>>`

`import Data.Function ((&))`

`>>>`

`data Rating = Lowest | Low | Medium | High | Highest deriving (Eq,Ord,Show)`

`>>>`

`instance Monoid Rating where mempty = Highest; mappend = min`

Notice that the `Monoid`

instance combines ratings by choosing
the lower one. Now, we consider the data from the survey:

`>>>`

`let resA = [("Big Lake",High),("Newport Lake",Medium),("Dustboro",Low)]`

`>>>`

`let resB = [("Sand Town",Medium),("Sand Town",High),("Mount Lucy",High)]`

`>>>`

`let resC = [("Lucy Hill",Highest),("Dustboro",High),("Dustville",High)]`

`>>>`

`let m1 = foldMap (uncurry singleton) (resA ++ resB ++ resC)`

`>>>`

m1 :: DisjointMap [Char] Rating`:t m1`

`>>>`

{"Big Lake"} -> High {"Dustboro"} -> Low {"Dustville"} -> High {"Lucy Hill"} -> Highest {"Mount Lucy"} -> High {"Newport Lake"} -> Medium {"Sand Town"} -> Medium`mapM_ putStrLn (prettyList m1)`

Since we haven't defined any equivalence classes for the town names yet,
what we have so far is no different from an ordinary `Map`

. Now we
will introduce some equivalences:

`>>>`

`let m2 = m1 & union "Big Lake" "Newport Lake" & union "Sand Town" "Dustboro"`

`>>>`

`let m3 = m2 & union "Dustboro" "Dustville" & union "Lucy Hill" "Mount Lucy"`

`>>>`

{"Dustboro","Dustville","Sand Town"} -> Low {"Lucy Hill","Mount Lucy"} -> High {"Big Lake","Newport Lake"} -> Medium`mapM_ putStrLn (prettyList m3)`

We can now query the map to find the lowest rating in a given town:

`>>>`

Low`lookup "Dustville" m3`

`>>>`

High`lookup "Lucy Hill" m3`