Copyright | (c) Andrey Mokhov 2016-2017 |
---|---|
License | MIT (see the file LICENSE) |
Maintainer | andrey.mokhov@gmail.com |
Stability | experimental |
Safe Haskell | None |
Language | Haskell2010 |
An abstract implementation of preorder relations. Use Algebra.Graph.Class for polymorphic construction and manipulation.
- data PreorderRelation a
- fromRelation :: Relation a -> PreorderRelation a
- toRelation :: Ord a => PreorderRelation a -> Relation a
Data structure
data PreorderRelation a Source #
The PreorderRelation
data type represents a binary relation over a set of
elements that is both transitive and reflexive. Preorders satisfy all laws of the
Preorder
type class and, in particular, the closure
axiom:
y /= empty
==> x * y + x * z + y * z == x * y + y * z
and the self-loop axiom:
vertex
x ==vertex
x *vertex
x
For example, the following holds:
path
xs ==clique
xs
The Show
instance produces reflexively and transitively closed expressions:
show (1 :: PreorderRelation Int) == "edge 1 1" show (1 * 2 :: PreorderRelation Int) == "edges [(1,1),(1,2),(2,2)]" show (1 * 2 + 2 * 3 :: PreorderRelation Int) == "edges [(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]"
Ord a => Eq (PreorderRelation a) Source # | |
(Num a, Ord a) => Num (PreorderRelation a) Source # | |
(Ord a, Show a) => Show (PreorderRelation a) Source # | |
Ord a => Preorder (PreorderRelation a) Source # | |
Ord a => Transitive (PreorderRelation a) Source # | |
Ord a => Reflexive (PreorderRelation a) Source # | |
Ord a => Graph (PreorderRelation a) Source # | |
type Vertex (PreorderRelation a) Source # | |
fromRelation :: Relation a -> PreorderRelation a Source #
Construct a preorder relation from a Relation
.
Complexity: O(1) time.
toRelation :: Ord a => PreorderRelation a -> Relation a Source #
Extract the underlying relation. Complexity: O(n * m * log(m)) time.