GHC.Types.Unique.SDFM

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.

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