GHC.Types.Unique.SDFM

Like a UniqDFM, but maintains equivalence classes of keys sharing the same entry. See UniqSDFM.

Unique-keyed, shared, deterministic mappings

data UniqSDFM key ele

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:

• lookupUSDFM m u3 == Just ele1, lookupUSDFM m u4 == Nothing, lookupUSDFM m u5 == Nothing.
• equateUSDFM m u1 u3 is a no-op, but equateUSDFM m u1 u2 merges {u1,u3} and {u2} to point to Just ele2 and returns the old entry of {u1,u3}, Just ele1.
• addToUSDFM m u3 ele4 sets the entry of {u1,u3} to Just 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

Methods

ppr :: UniqSDFM key ele -> SDoc

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)