Copyright	(c) Andrey Mokhov 2016-2022
License	MIT (see the file LICENSE)
Maintainer	andrey.mokhov@gmail.com
Stability	experimental
Safe Haskell	None
Language	Haskell2010

Algebra.Graph.Relation.Preorder

Contents

Data structure

Description

An abstract implementation of preorder relations. Use Algebra.Graph.Class for polymorphic construction and manipulation.

Synopsis

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 that is both reflexive and transitive . Preorders satisfy all laws of the Preorder type class and, in particular, the self-loop axiom:

vertex x == vertex x * vertex x

and the closure axiom:

y /= empty ==> x * y + x * z + y * z == x * y + y * z

For example, the following holds:

path xs == (clique xs :: PreorderRelation Int)

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)]"

Instances

Instances details

Ord a => Eq ( PreorderRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Preorder Methods (==) :: PreorderRelation a -> PreorderRelation a -> Bool Source # (/=) :: PreorderRelation a -> PreorderRelation a -> Bool Source #
( Ord a, Num a) => Num ( PreorderRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Preorder Methods (+) :: PreorderRelation a -> PreorderRelation a -> PreorderRelation a Source # (-) :: PreorderRelation a -> PreorderRelation a -> PreorderRelation a Source # (*) :: PreorderRelation a -> PreorderRelation a -> PreorderRelation a Source # negate :: PreorderRelation a -> PreorderRelation a Source # abs :: PreorderRelation a -> PreorderRelation a Source # signum :: PreorderRelation a -> PreorderRelation a Source # fromInteger :: Integer -> PreorderRelation a Source #
Ord a => Ord ( PreorderRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Preorder Methods compare :: PreorderRelation a -> PreorderRelation a -> Ordering Source # (<) :: PreorderRelation a -> PreorderRelation a -> Bool Source # (<=) :: PreorderRelation a -> PreorderRelation a -> Bool Source # (>) :: PreorderRelation a -> PreorderRelation a -> Bool Source # (>=) :: PreorderRelation a -> PreorderRelation a -> Bool Source # max :: PreorderRelation a -> PreorderRelation a -> PreorderRelation a Source # min :: PreorderRelation a -> PreorderRelation a -> PreorderRelation a Source #
( Ord a, Show a) => Show ( PreorderRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Preorder Methods showsPrec :: Int -> PreorderRelation a -> ShowS Source # show :: PreorderRelation a -> String Source # showList :: [ PreorderRelation a] -> ShowS Source #
IsString a => IsString ( PreorderRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Preorder Methods fromString :: String -> PreorderRelation a Source #
NFData a => NFData ( PreorderRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Preorder Methods rnf :: PreorderRelation a -> () Source #
Ord a => Preorder ( PreorderRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Preorder
Ord a => Transitive ( PreorderRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Preorder
Ord a => Reflexive ( PreorderRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Preorder
Ord a => Graph ( PreorderRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Preorder Associated Types type Vertex ( PreorderRelation a) Source # Methods empty :: PreorderRelation a Source # vertex :: Vertex ( PreorderRelation a) -> PreorderRelation a Source # overlay :: PreorderRelation a -> PreorderRelation a -> PreorderRelation a Source # connect :: PreorderRelation a -> PreorderRelation a -> PreorderRelation a Source #
type Vertex ( PreorderRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Preorder type Vertex ( PreorderRelation a) = a

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.