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

Copyright	(c) JK. 2019 (c) DD. 2012 (c) LFL. 2009
License	BSD-style
Maintainer	Drew Day<[email protected]>
Stability	experimental
Portability	portable
Safe Haskell	Safe
Language	Haskell2010

Data.Relation

Contents

The Relation Type
Provided functionality:

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:

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.

Synopsis

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
intersection :: (Ord a, Ord b) => Relation a 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 -> Set b
lookupRan :: Ord b => b -> Relation a b -> 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
restrictDom :: (Ord a, Ord b) => Set a -> Relation a b -> Relation a b
restrictRan :: (Ord a, Ord b) => Set b -> Relation a b -> Relation a b
withoutDom :: (Ord a, Ord b) => Set a -> Relation a b -> Relation a b
withoutRan :: (Ord a, Ord b) => Set b -> Relation a b -> Relation a b
toList :: Relation a b -> [(a, b)]
dom :: Relation a b -> Set a
ran :: Relation a b -> Set b
converse :: Relation a b -> Relation b a

The `Relation` Type

data Relation a b Source #

Representation of a relation on ordered (Ord) values

Instances

(Eq a, Eq b) => Eq (Relation a b) Source #
Instance details 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) Source #
Instance details 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) Source #
Instance details 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 Source #

size r returns the number of tuples in the relation.

null :: Relation a b -> Bool Source #

True if the relation r is the empty relation.

Construction

empty :: Relation a b Source #

Construct a relation with no elements.

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

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

singleton :: a -> b -> Relation a b Source #

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 Source #

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

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

Union a list of relations using the empty relation.

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

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 Source #

Insert a relation x and y in the relation r

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

Delete an association in the relation.

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

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

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

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

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

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

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

True if the element exists in the range.

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

True if the relation contains the association x and y

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

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 Source #

Restrict the domain to that of the provided set

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

Restrict the range to that of the provided set

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

Restrict the domain to exclude elements of the provided set

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

Restrict the range to exclude elements of the provided set

Conversion

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

Builds a List from a Relation.

dom :: Relation a b -> Set a Source #

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

ran :: Relation a b -> Set b Source #

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

converse :: Relation a b -> Relation b a Source #

Returns the converse of the relation.