| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
GHC.Types.Unique.SDFM
Description
Synopsis
- data UniqSDFM key ele
- emptyUSDFM :: UniqSDFM key ele
- lookupUSDFM :: Uniquable key => UniqSDFM key ele -> key -> Maybe ele
- equateUSDFM :: Uniquable key => UniqSDFM key ele -> key -> key -> (Maybe ele, UniqSDFM key ele)
- addToUSDFM :: Uniquable key => UniqSDFM key ele -> key -> ele -> UniqSDFM key ele
- traverseUSDFM :: forall key a b f. Applicative f => (a -> f b) -> UniqSDFM key a -> f (UniqSDFM key b)
Unique-keyed, shared, deterministic mappings
A UniqDFM whose domain is sets of Uniques, each of which share a
common value of type ele.
Every such set ("equivalence class") has a distinct representative
Unique. Supports merging the entries of multiple such sets in a union-find
like fashion.
An accurate model is that of [(Set key, Maybe ele)]: A finite mapping from
sets of keys to possibly absent entries ele, where the sets don't overlap.
Example:
m = [({u1,u3}, Just ele1), ({u2}, Just ele2), ({u4,u7}, Nothing)]
On this model we support the following main operations:
,lookupUSDFMm u3 == Just ele1,lookupUSDFMm u4 == Nothing.lookupUSDFMm u5 == Nothingis a no-op, butequateUSDFMm u1 u3mergesequateUSDFMm u1 u2{u1,u3}and{u2}to point toJust ele2and returns the old entry of{u1,u3},Just ele1.sets the entry ofaddToUSDFMm u3 ele4{u1,u3}toJust ele4.
As well as a few means for traversal/conversion to list.
Instances
| (Outputable key, Outputable ele) => Outputable (UniqSDFM key ele) # | |
Defined in GHC.Types.Unique.SDFM | |
emptyUSDFM :: UniqSDFM key ele #
lookupUSDFM :: Uniquable key => UniqSDFM key ele -> key -> Maybe ele #
lookupSUDFM env x looks up an entry for x, looking through all
Indirects until it finds a shared Entry.
Examples in terms of the model (see UniqSDFM):
>>> lookupUSDFM [({u1,u3}, Just ele1), ({u2}, Just ele2)] u3 == Just ele1
>>> lookupUSDFM [({u1,u3}, Just ele1), ({u2}, Just ele2)] u4 == Nothing
>>> lookupUSDFM [({u1,u3}, Just ele1), ({u2}, Nothing)] u2 == Nothing
equateUSDFM :: Uniquable key => UniqSDFM key ele -> key -> key -> (Maybe ele, UniqSDFM key ele) #
equateUSDFM env x y makes x and y point to the same entry,
thereby merging x's class with y's.
If both x and y are in the domain of the map, then y's entry will be
chosen as the new entry and x's old entry will be returned.
Examples in terms of the model (see UniqSDFM):
>>> equateUSDFM [] u1 u2 == (Nothing, [({u1,u2}, Nothing)])
>>> equateUSDFM [({u1,u3}, Just ele1)] u3 u4 == (Nothing, [({u1,u3,u4}, Just ele1)])
>>> equateUSDFM [({u1,u3}, Just ele1)] u4 u3 == (Nothing, [({u1,u3,u4}, Just ele1)])
>>> equateUSDFM [({u1,u3}, Just ele1), ({u2}, Just ele2)] u3 u2 == (Just ele1, [({u2,u1,u3}, Just ele2)])
addToUSDFM :: Uniquable key => UniqSDFM key ele -> key -> ele -> UniqSDFM key ele #
addToUSDFM env x a sets the entry x is associated with to a,
thereby modifying its whole equivalence class.
Examples in terms of the model (see UniqSDFM):
>>> addToUSDFM [] u1 ele1 == [({u1}, Just ele1)]
>>> addToUSDFM [({u1,u3}, Just ele1)] u3 ele2 == [({u1,u3}, Just ele2)]
traverseUSDFM :: forall key a b f. Applicative f => (a -> f b) -> UniqSDFM key a -> f (UniqSDFM key b) #