hets -- a heterogenous Specification (CASL) tool setContentsIndex
Common.Lib.Rel
Portability portable
Stability provisional
Maintainer maeder@tzi.de
Description

supply a simple data type for (precedence or subsort) relations. A relation is conceptually a set of (ordered) pairs. But the hidden implementation is based on a map of sets.

Rel replaces a directed graph with unique node labels (Ord a) and unlabelled edges (without multiplicity higher than one).

Usage: start with an empty relation, insert edges, and test for an edge member (before or after calling transClosure).

It is possible to insert self edges or bigger cycles.

A transitive path can be checked by transMember without computing the full transitive closure. A further insert, however, may destroy the closedness property of a relation.

Synopsis
data Rel a
empty :: Rel a
isEmpty :: Rel a -> Bool
insert :: Ord a => a -> a -> Rel a -> Rel a
member :: Ord a => a -> a -> Rel a -> Bool
toMap :: Rel a -> Map a (Set a)
transMember :: Ord a => a -> a -> Rel a -> Bool
transClosure :: Ord a => Rel a -> Rel a
fromList :: Ord a => [(a, a)] -> Rel a
toList :: Ord a => Rel a -> [(a, a)]
image :: Ord b => (a -> b) -> Rel a -> Rel b
restrict :: Ord a => Rel a -> Set a -> Rel a
toSet :: Ord a => Rel a -> Set (a, a)
fromSet :: Ord a => Set (a, a) -> Rel a
topSort :: Ord a => Rel a -> [Set a]
Documentation
data Rel a
Instances
(Ord a, ATermConvertible a) => ATermConvertible (Rel a)
(Show a, Ord a) => Show (Rel a)
??? a => Eq (Rel a)
empty :: Rel a
the empty relation
isEmpty :: Rel a -> Bool
test for empty
insert :: Ord a => a -> a -> Rel a -> Rel a
insert an ordered pair
member :: Ord a => a -> a -> Rel a -> Bool
test for an (previously inserted) ordered pair
toMap :: Rel a -> Map a (Set a)
transMember :: Ord a => a -> a -> Rel a -> Bool
test for member or transitive membership
transClosure :: Ord a => Rel a -> Rel a
compute transitive closure (make all transitive members direct members)
fromList :: Ord a => [(a, a)] -> Rel a
convert a list of ordered pairs to a relation
toList :: Ord a => Rel a -> [(a, a)]
convert a relation to a list of ordered pairs
image :: Ord b => (a -> b) -> Rel a -> Rel b
Image of a relation under a function
restrict :: Ord a => Rel a -> Set a -> Rel a
Restriction of a relation under a set
toSet :: Ord a => Rel a -> Set (a, a)
convert a relation to a set of ordered pairs
fromSet :: Ord a => Set (a, a) -> Rel a
convert a set of ordered pairs to a relation
topSort :: Ord a => Rel a -> [Set a]
topological sort a relation (more efficient for a closed relation)
Produced by Haddock version 0.6