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

In 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 associated with a Set of values v.

We do not allow the associations with the empty Set.

Construct a relation with no elements.

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

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

Construct a relation from a mapping from the domain and range mappings.

Precondition: the multimaps together form a valid relation; i.e. if x is related to y in one map then y is related to x in the other.

O(1).

True if the relation r is the empty relation.

O(1).

size r returns the number of tuples in the relation.

True if the relation contains the association x and y

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

True if the element exists in the domain.

True if the element exists in the range.

True if a value appears more than one time in the relation.

(Case b <| r a)

( Case a |> r b )

Restricts the relation to domain elements having multiple range elements

Named version of (<||).

Restrict the domain to not include these as.

Named version of (||>).

Restrict the range to not include these bs.

Domain restriction for a relation. Modeled on z.

Domain restriction for a relation. Modeled on z.

Range restriction for a relation. Modeled on z.

Range restriction for a relation. Modeled on z.

This fragment provided by:

  Module      :  Data.Map
  Copyright   :  (c) Daan Leijen 2002
                 (c) Andriy Palamarchuk 2008
  License     :  BSD-style
  Maintainer  :  libraries@haskell.org
  Stability   :  provisional
  Portability :  portable

Like mapDom, but takes a function that must be monotonic; i.e. compare x y == compare (f x) (f y).

Like mapRan, but takes a function that must be monotonic; i.e. compare x y == compare (f x) (f y).

Insert a relation x and y in the relation r

Delete an association in the relation.

replaceDom x y r replaces all (x, _) with (y, _) in r.

replaceRan x y r replaces all (_, x) with (_, y) in r.

Compute the difference of two relations.

Like difference, but returns Nothing if the difference is empty.

innerJoinDomMultimaps xs ys returns the "inner join" of the domains of xs and ys, which has intersection-like semantics:

• as that do not exist in both xs and ys are dropped.
• The as that remain are therefore associated with non-empty sets of bs and cs.

O(a2 * log(a1a2 + 1)), a1 <= a2, where a1 and a2/ are the numbers of elements in each relation's domain.

innerJoinRanMultimaps xs ys returns the "inner join" of the ranges of xs and ys. See innerJoinDomMultimaps for more info.

O(c2 * log(c1c2 + 1)), c1 <= c2, where c1 and c2/ are the numbers of elements in each relation's range.

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

Union a list of relations using the empty relation.

Builds a List from a Relation.

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

O(a).

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

O(b).

Builds a Set from a Relation