Data.Relation

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.

The Relation Type

data Relation a b

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)

Defined in Data.Relation

Methods

(==) :: Relation a b -> Relation a b -> Bool

(/=) :: Relation a b -> Relation a b -> Bool

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

Defined in Data.Relation

Methods

compare :: Relation a b -> Relation a b -> Ordering

(<) :: Relation a b -> Relation a b -> Bool

(<=) :: Relation a b -> Relation a b -> Bool

(>) :: Relation a b -> Relation a b -> Bool

(>=) :: Relation a b -> Relation a b -> Bool

max :: Relation a b -> Relation a b -> Relation a b

min :: Relation a b -> Relation a b -> Relation a b

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

Defined in Data.Relation

Methods

showsPrec :: Int -> Relation a b -> ShowS

show :: Relation a b -> String

showList :: [Relation a b] -> ShowS

Provided functionality:

Questions

size :: Relation a b -> Int

size r returns the number of tuples in the relation.

null :: Relation a b -> Bool

True if the relation r is the empty relation.

Construction

empty :: Relation a b

Construct a relation with no elements.

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

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

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

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 b

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

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

Union a list of relations using the empty relation.

intersection :: (Ord a, Ord b) => Relation a b -> Relation a b -> Relation a b

Intersection of two relations: a and b are related by intersection r s exactly when a and b are related by r and s.

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

Insert a relation x and y in the relation r

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

Delete an association in the relation.

lookupDom :: Ord a => a -> Relation a b -> Set b

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

lookupRan :: Ord b => b -> Relation a b -> Set a

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

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

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

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

True if the element exists in the range.

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

True if the relation contains the association x and y

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

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

Conversion

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

Builds a List from a Relation.

dom :: Relation a b -> Set a

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

ran :: Relation a b -> Set b

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

Invertible Relations

c :: Relation a b -> Relation b a

Returns the converse of the relation.

Utilities

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

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 b

( Case a |> r b )

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

(Case b <| r a)

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

Domain restriction for a relation. Modeled on z.

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

Range restriction for a relation. Modeled on z.