relation-0.2.1: A data structure representing Relations on Sets.

Portability portable experimental Drew Day Safe-Infered

Data.Relation

Description

Relations are modeled as assciations between two elements.

Relations offer efficient search for any of the two elements.

Unlike Data.Map, an element ca be associated more than once.

The two purposes of this structure are:

1. Associating elements
2. Provide efficient searches for either of the two elements.

Since neither `map` nor `fold` are implemented, you must convert the structure to a list to process sequentially.

Synopsis

# The `Relation` Type

data Relation a b Source

This implementation avoids using `S.Set (a,b)` because it it is necessary to search for an item without knowing both `D` and `R`.

In S.Set, you must know both values to search.

Thus, we have are two maps to updated together.

1. Always be careful with the associated set of the key.
2. If you union two relations, apply union to the set of values.
3. If you subtract, take care when handling the set of values.

As a multi-map, each key is asscoated with a Set of values v.

We do not allow the associations with the `empty` Set.

Instances

 (Eq a, Eq b) => Eq (Relation a b) (Ord a, Ord b) => Ord (Relation a b) (Show a, Show b) => Show (Relation a b)

# Provided functionality:

## Questions

size :: Relation a b -> IntSource

`size r` returns the number of tuples in the relation.

null :: Relation a b -> BoolSource

True if the relation `r` is the `empty` relation.

## Construction

empty :: Relation a bSource

Construct a relation with no elements.

fromList :: (Ord a, Ord b) => [(a, b)] -> Relation a bSource

The list must be formatted like: [(k1, v1), (k2, v2),..,(kn, vn)].

singleton :: a -> b -> Relation a bSource

Builds a `Relation` consiting of an association between: `x` and `y`.

## Operations

union :: (Ord a, Ord b) => Relation a b -> Relation a b -> Relation a bSource

The `Relation` that results from the union of two relations: `r` and `s`.

unions :: (Ord a, Ord b) => [Relation a b] -> Relation a bSource

Union a list of relations using the `empty` relation.

insert :: (Ord a, Ord b) => a -> b -> Relation a b -> Relation a bSource

Insert a relation ` x ` and ` y ` in the relation ` r `

delete :: (Ord a, Ord b) => a -> b -> Relation a b -> Relation a bSource

Delete an association in the relation.

lookupDom :: Ord a => a -> Relation a b -> Maybe (Set b)Source

The Set of values associated with a value in the domain.

lookupRan :: Ord b => b -> Relation a b -> Maybe (Set a)Source

The Set of values associated with a value in the range.

memberDom :: Ord a => a -> Relation a b -> BoolSource

True if the element ` x ` exists in the domain of ` r `.

memberRan :: Ord b => b -> Relation a b -> BoolSource

True if the element exists in the range.

member :: (Ord a, Ord b) => a -> b -> Relation a b -> BoolSource

True if the relation contains the association `x` and `y`

notMember :: (Ord a, Ord b) => a -> b -> Relation a b -> BoolSource

True if the relation does not contain the association `x` and `y`

## Conversion

toList :: Relation a b -> [(a, b)]Source

Builds a List from a Relation.

dom :: Relation a b -> Set aSource

Returns the domain in the relation, as a Set, in its entirety.

ran :: Relation a b -> Set bSource

Returns the range of the relation, as a Set, in its entirety.

## Utilities

compactSet :: Ord a => Set (Maybe (Set a)) -> Set aSource

A compact set of sets the values of which can be `Just (Set x)` or `Nothing`.

The cases of `Nothing` are purged.

It is similar to `concat`.

Primitive implementation for the right selection and left selection operators.

PICA provides both operators: `|>` and `<|` and `|\$>` and `<\$|`

in this library, for working with Relations and OIS (Ordered, Inductive Sets?).

PICA exposes the operators defined here, so as not to interfere with the abstraction of the Relation type and because having access to Relation hidden components is a more efficient implementation of the operation of restriction.

``` (a <\$| b) r denotes: for every element ```b` from the Set `B```, select an element ```a` from the Set `A``` , if ```a``` is related to ```b``` in ```r``` ```

``` (a |\$> b) r denotes: for every element ```a` from the Set `A``` , select an element ```b` from the Set `B```, if ```a``` is related to ```b``` in ```r``` ```

With regard to domain restriction and range restriction operators of the language, those are described differently and return the domain or the range.

(|\$>) :: (Ord a, Ord b) => Set a -> Set b -> Relation a b -> Set bSource

`( Case a |> r b )`

(<\$|) :: (Ord a, Ord b) => Set a -> Set b -> Relation a b -> Set aSource

`(Case b <| r a)`

(<|) :: (Ord a, Ord b) => Set a -> Relation a b -> Relation a bSource

Domain restriction for a relation. Modeled on z.

(|>) :: (Ord a, Ord b) => Relation a b -> Set b -> Relation a bSource

Range restriction for a relation. Modeled on z.