Safe Haskell | None |
---|---|

Language | GHC2021 |

## 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, but`equateUSDFM`

m u1 u3

merges`equateUSDFM`

m u1 u2`{u1,u3}`

and`{u2}`

to point to`Just ele2`

and returns the old entry of`{u1,u3}`

,`Just ele1`

.

sets the entry of`addToUSDFM`

m u3 ele4`{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) 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 #