Safe Haskell | Safe-Inferred |
---|---|
Language | Haskell2010 |
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
data UniqSDFM key ele Source #
A UniqDFM
whose domain is sets of Unique
s, 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 key
s 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:
,lookupUSDFM
m u3 == Just ele1
,lookupUSDFM
m u4 == Nothing
.lookupUSDFM
m u5 == Nothing
is a no-op, butequateUSDFM
m u1 u3
mergesequateUSDFM
m u1 u2{u1,u3}
and{u2}
to point toJust ele2
and returns the old entry of{u1,u3}
,Just ele1
.
sets the entry ofaddToUSDFM
m 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) Source # | |
emptyUSDFM :: UniqSDFM key ele Source #
lookupUSDFM :: Uniquable key => UniqSDFM key ele -> key -> Maybe ele Source #
lookupSUDFM env x
looks up an entry for x
, looking through all
Indirect
s 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) Source #
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 Source #
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) Source #