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

Representation of a relation on ordered (Ord) values

Instances

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

Defined in Data.Relation.Internal

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.Internal

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.Internal

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. >>> size (fromList []) == 0 True >>> size (fromList [(a, 1)]) == 1 True

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. >>> toList (fromList []) == [] True

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

The list must be formatted like: [(k1, v1), (k2, v2),..,(kn, vn)]. >>> toList (fromList [(a, 1)]) == [(a, 1)] True >>> fromList [(a, 1), (a, 1)] == fromList [(a, 1), (a, 1)] True >>> fromList [(a, 1), (b, 1)] == fromList [(a, 1), (b, 1)] True

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

Builds a Relation consiting of an association between: x and y. >>> singleton a 1 == fromList [(a, 1)] True

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. >>> fromList [(a, 1)] union fromList [(a, 1)] == fromList [(a, 1)] True >>> fromList [(a, 2)] union fromList [(a, 2)] == fromList [(a, 2)] True >>> fromList [(a, 1)] union fromList [(b, 2)] == fromList [(a, 1), (b, 2)] True

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

Union a list of relations using the empty relation. >>> unions [] == fromList [] True >>> unions [fromList [(a, 1)]] == fromList [(a, 1)] True >>> unions [fromList [(a, 1)], fromList [(a, 1)]] == fromList [(a, 1)] True >>> unions [fromList [(a, 2)], fromList [(a, 2)]] == fromList [(a, 2)] True >>> unions [fromList [(a, 1)], fromList [(b, 2)]] == fromList [(a, 1), (b, 2)] True

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. >>> fromList [(a, 1)] intersection fromList [(a, 1)] == fromList [(a, 1)] True >>> fromList [(a, 2)] intersection fromList [(a, 2)] == fromList [(a, 2)] True >>> fromList [(a, 1)] intersection fromList [(b, 2)] == fromList [] True

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

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

Restrict the domain to that of the provided set

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

Restrict the range to that of the provided set

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

Restrict the domain to exclude elements of the provided set

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

Restrict the range to exclude elements of the provided set

(<-<) :: (Ord a, Ord b, Ord c) => Relation b c -> Relation a b -> Relation a c infixr 9

Compose two relations: right to left version.

(>->) :: (Ord a, Ord b, Ord c) => Relation a b -> Relation b c -> Relation a c infixl 9

Compose two relations: left to right version.

Conversion

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

Builds a List from a Relation. >>> toList (fromList [(a, 1)]) == [(a, 1)] True >>> toList (fromList [(a, 1), (b, 2)]) == [(a, 1), (b, 2)] True >>> toList (fromList [(a, 1), (a, 2)]) == [(a, 1), (a, 2)] True >>> toList (fromList [(a, 1), (a, 1)]) == [(a, 1)] True

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.

converse :: Relation a b -> Relation b a

Returns the converse of the relation.