ghc-9.2.0.20210821: The GHC API
Safe HaskellSafe-Inferred
LanguageHaskell2010

GHC.Types.Unique.SDFM

Description

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

Synopsis

Unique-keyed, shared, deterministic mappings

data UniqSDFM key ele Source #

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:

As well as a few means for traversal/conversion to list.

Instances

Instances details
(Outputable key, Outputable ele) => Outputable (UniqSDFM key ele) Source # 
Instance details

Defined in GHC.Types.Unique.SDFM

Methods

ppr :: UniqSDFM key ele -> SDoc Source #

lookupUSDFM :: Uniquable key => UniqSDFM key ele -> key -> Maybe ele Source #

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) 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 #