Portability | portable |
---|---|
Stability | experimental |
Maintainer | Drew Day<drewday@gmail.com> |
Safe Haskell | Safe-Infered |
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.
- 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
- 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 -> Maybe (Set b)
- lookupRan :: Ord b => b -> Relation a b -> Maybe (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
- toList :: Relation a b -> [(a, b)]
- dom :: Relation a b -> Set a
- ran :: Relation a b -> Set b
- compactSet :: Ord a => Set (Maybe (Set a)) -> Set a
- (|$>) :: (Ord a, Ord b) => Set a -> Set b -> Relation a b -> Set b
- (<$|) :: (Ord a, Ord b) => Set a -> Set b -> Relation a b -> Set a
- (<|) :: (Ord a, Ord b) => Set a -> Relation a b -> Relation a b
- (|>) :: (Ord a, Ord b) => Relation a b -> Set b -> Relation a b
The Relation
Type
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.
- Always be careful with the associated set of the key.
- If you union two relations, apply union to the set of values.
- 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.
Provided functionality:
Questions
Construction
fromList :: (Ord a, Ord b) => [(a, b)] -> Relation a bSource
The list must be formatted like: [(k1, v1), (k2, v2),..,(kn, vn)].
singleton :: a -> b -> Relation a bSource
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 bSource
The Relation
that results from the union of two relations: r
and s
.
unions :: (Ord a, Ord b) => [Relation a b] -> Relation a bSource
Union a list of relations using the empty
relation.
insert :: (Ord a, Ord b) => a -> b -> Relation a b -> Relation a bSource
Insert a relation x
and y
in the relation r
delete :: (Ord a, Ord b) => a -> b -> Relation a b -> Relation a bSource
Delete an association in the relation.
lookupDom :: Ord a => a -> Relation a b -> Maybe (Set b)Source
The Set of values associated with a value in the domain.
lookupRan :: Ord b => b -> Relation a b -> Maybe (Set a)Source
The Set of values associated with a value in the range.
memberDom :: Ord a => a -> Relation a b -> BoolSource
True if the element x
exists in the domain of r
.
member :: (Ord a, Ord b) => a -> b -> Relation a b -> BoolSource
True if the relation contains the association x
and y
notMember :: (Ord a, Ord b) => a -> b -> Relation a b -> BoolSource
True if the relation does not contain the association x
and y
Conversion
Utilities
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.