Copyright | (c) JK. 2019 (c) DD. 2012 (c) LFL. 2009 |
---|---|
License | BSD-style |
Maintainer | Drew Day<drewday@gmail.com> |
Stability | experimental |
Portability | portable |
Safe Haskell | Safe |
Language | Haskell2010 |
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
- (<-<) :: (Ord a, Ord b, Ord c) => Relation b c -> Relation a b -> Relation a c
- (>->) :: (Ord a, Ord b, Ord c) => Relation a b -> Relation b c -> Relation a c
- 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
Representation of a relation on ordered (Ord
) values
Instances
(Eq a, Eq b) => Eq (Relation a b) Source # | |
(Ord a, Ord b) => Ord (Relation a b) Source # | |
Defined in Data.Relation.Internal | |
(Show a, Show b) => Show (Relation a b) Source # | |
Provided functionality:
Questions
size :: Relation a b -> Int Source #
size r
returns the number of tuples in the relation.
>>> size (fromList []) == 0
True
>>> size (fromList [(a
, 1)]) == 1
True
Construction
empty :: Relation a b Source #
Construct a relation with no elements. >>> toList (fromList []) == [] True
fromList :: (Ord a, Ord b) => [(a, b)] -> Relation a b Source #
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 Source #
Builds a Relation
consiting of an association between: x
and y
.
>>> singleton a
1 == fromList [(a
, 1)]
True
Operations
unions :: (Ord a, Ord b) => [Relation a b] -> Relation a b Source #
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 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
.
>>> 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 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
.
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
(<-<) :: (Ord a, Ord b, Ord c) => Relation b c -> Relation a b -> Relation a c infixr 9 Source #
Compose two relations: right to left version.
(>->) :: (Ord a, Ord b, Ord c) => Relation a b -> Relation b c -> Relation a c infixl 9 Source #
Compose two relations: left to right version.
Conversion
toList :: Relation a b -> [(a, b)] Source #
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