| |||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||
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 | |||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||
Documentation | |||||||||||||||||||||||||||||
data 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 |