Portability | portable |
---|---|

Stability | experimental |

Maintainer | Drew Day<drewday@gmail.com> |

Safe Haskell | Safe-Infered |

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:

- Associating elements
- 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.

- data Relation a b
- size :: Relation a b -> Int
- null :: Relation a b -> Bool
- empty :: Relation a b
- fromList :: (Ord a, Ord b) => [(a, b)] -> Relation a b
- singleton :: a -> b -> Relation a b
- union :: (Ord a, Ord b) => Relation a b -> Relation a b -> Relation a b
- unions :: (Ord a, Ord b) => [Relation a b] -> Relation a b
- insert :: (Ord a, Ord b) => a -> b -> Relation a b -> Relation a b
- delete :: (Ord a, Ord b) => a -> b -> Relation a b -> Relation a b
- lookupDom :: Ord a => a -> Relation a b -> Maybe (Set b)
- lookupRan :: Ord b => b -> Relation a b -> Maybe (Set a)
- memberDom :: Ord a => a -> Relation a b -> Bool
- memberRan :: Ord b => b -> Relation a b -> Bool
- member :: (Ord a, Ord b) => a -> b -> Relation a b -> Bool
- notMember :: (Ord a, Ord b) => a -> b -> Relation a b -> Bool
- toList :: Relation a b -> [(a, b)]
- dom :: Relation a b -> Set a
- ran :: Relation a b -> Set b
- compactSet :: Ord a => Set (Maybe (Set a)) -> Set a
- (|$>) :: (Ord a, Ord b) => Set a -> Set b -> Relation a b -> Set b
- (<$|) :: (Ord a, Ord b) => Set a -> Set b -> Relation a b -> Set a
- (<|) :: (Ord a, Ord b) => Set a -> Relation a b -> Relation a b
- (|>) :: (Ord a, Ord b) => Relation a b -> Set b -> Relation a b

# The `Relation`

Type

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.

- Always be careful with the associated set of the key.
- If you union two relations, apply union to the set of values.
- 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.

# Provided functionality:

## Questions

## Construction

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 `

.

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

## Utilities

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.