Algebra.Graph.Relation.InternalDerived

This module exposes the implementation of derived binary relation data types. The API is unstable and unsafe, and is exposed only for documentation. You should use the non-internal modules Algebra.Graph.Relation.Reflexive, Algebra.Graph.Relation.Symmetric, Algebra.Graph.Relation.Transitive and Algebra.Graph.Relation.Preorder instead.

Implementation of derived binary relations

newtype ReflexiveRelation a

The ReflexiveRelation data type represents a reflexive binary relation over a set of elements. Reflexive relations satisfy all laws of the Reflexive type class and, in particular, the self-loop axiom:

vertex x == vertex x * vertex x

The Show instance produces reflexively closed expressions:

show (1     :: ReflexiveRelation Int) == "edge 1 1"
show (1 * 2 :: ReflexiveRelation Int) == "edges [(1,1),(1,2),(2,2)]"

Constructors

ReflexiveRelation

Fields

• fromReflexive :: Relation a

Instances

Ord a => Eq (ReflexiveRelation a)

Methods

(==) :: ReflexiveRelation a -> ReflexiveRelation a -> Bool

(/=) :: ReflexiveRelation a -> ReflexiveRelation a -> Bool

(Num a, Ord a) => Num (ReflexiveRelation a)

Methods

(+) :: ReflexiveRelation a -> ReflexiveRelation a -> ReflexiveRelation a

(-) :: ReflexiveRelation a -> ReflexiveRelation a -> ReflexiveRelation a

(*) :: ReflexiveRelation a -> ReflexiveRelation a -> ReflexiveRelation a

negate :: ReflexiveRelation a -> ReflexiveRelation a

abs :: ReflexiveRelation a -> ReflexiveRelation a

signum :: ReflexiveRelation a -> ReflexiveRelation a

fromInteger :: Integer -> ReflexiveRelation a

(Ord a, Show a) => Show (ReflexiveRelation a)

Methods

showsPrec :: Int -> ReflexiveRelation a -> ShowS

show :: ReflexiveRelation a -> String

showList :: [ReflexiveRelation a] -> ShowS

Ord a => Reflexive (ReflexiveRelation a)

Ord a => Graph (ReflexiveRelation a)

Associated Types

type Vertex (ReflexiveRelation a) :: *

Methods

empty :: ReflexiveRelation a

vertex :: Vertex (ReflexiveRelation a) -> ReflexiveRelation a

overlay :: ReflexiveRelation a -> ReflexiveRelation a -> ReflexiveRelation a

connect :: ReflexiveRelation a -> ReflexiveRelation a -> ReflexiveRelation a

type Vertex (ReflexiveRelation a)

type Vertex (ReflexiveRelation a) = a

newtype SymmetricRelation a

The SymmetricRelation data type represents a symmetric binary relation over a set of elements. Symmetric relations satisfy all laws of the Undirected type class and, in particular, the commutativity of connect:

connect x y == connect y x

The Show instance produces symmetrically closed expressions:

show (1     :: SymmetricRelation Int) == "vertex 1"
show (1 * 2 :: SymmetricRelation Int) == "edges [(1,2),(2,1)]"

Constructors

SymmetricRelation

Fields

• fromSymmetric :: Relation a

Instances

Ord a => Eq (SymmetricRelation a)

Methods

(==) :: SymmetricRelation a -> SymmetricRelation a -> Bool

(/=) :: SymmetricRelation a -> SymmetricRelation a -> Bool

(Num a, Ord a) => Num (SymmetricRelation a)

Methods

(+) :: SymmetricRelation a -> SymmetricRelation a -> SymmetricRelation a

(-) :: SymmetricRelation a -> SymmetricRelation a -> SymmetricRelation a

(*) :: SymmetricRelation a -> SymmetricRelation a -> SymmetricRelation a

negate :: SymmetricRelation a -> SymmetricRelation a

abs :: SymmetricRelation a -> SymmetricRelation a

signum :: SymmetricRelation a -> SymmetricRelation a

fromInteger :: Integer -> SymmetricRelation a

(Ord a, Show a) => Show (SymmetricRelation a)

Methods

showsPrec :: Int -> SymmetricRelation a -> ShowS

show :: SymmetricRelation a -> String

showList :: [SymmetricRelation a] -> ShowS

Ord a => Undirected (SymmetricRelation a)

Ord a => Graph (SymmetricRelation a)

Associated Types

type Vertex (SymmetricRelation a) :: *

Methods

empty :: SymmetricRelation a

vertex :: Vertex (SymmetricRelation a) -> SymmetricRelation a

overlay :: SymmetricRelation a -> SymmetricRelation a -> SymmetricRelation a

connect :: SymmetricRelation a -> SymmetricRelation a -> SymmetricRelation a

type Vertex (SymmetricRelation a)

type Vertex (SymmetricRelation a) = a

newtype TransitiveRelation a

The TransitiveRelation data type represents a transitive binary relation over a set of elements. Transitive relations satisfy all laws of the Transitive type class and, in particular, the closure axiom:

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

For example, the following holds:

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

The Show instance produces transitively closed expressions:

show (1 * 2         :: TransitiveRelation Int) == "edge 1 2"
show (1 * 2 + 2 * 3 :: TransitiveRelation Int) == "edges [(1,2),(1,3),(2,3)]"

Constructors

TransitiveRelation

Fields

• fromTransitive :: Relation a

Instances

Ord a => Eq (TransitiveRelation a)

Methods

(==) :: TransitiveRelation a -> TransitiveRelation a -> Bool

(/=) :: TransitiveRelation a -> TransitiveRelation a -> Bool

(Num a, Ord a) => Num (TransitiveRelation a)

Methods

(+) :: TransitiveRelation a -> TransitiveRelation a -> TransitiveRelation a

(-) :: TransitiveRelation a -> TransitiveRelation a -> TransitiveRelation a

(*) :: TransitiveRelation a -> TransitiveRelation a -> TransitiveRelation a

negate :: TransitiveRelation a -> TransitiveRelation a

abs :: TransitiveRelation a -> TransitiveRelation a

signum :: TransitiveRelation a -> TransitiveRelation a

fromInteger :: Integer -> TransitiveRelation a

(Ord a, Show a) => Show (TransitiveRelation a)

Methods

showsPrec :: Int -> TransitiveRelation a -> ShowS

show :: TransitiveRelation a -> String

showList :: [TransitiveRelation a] -> ShowS

Ord a => Transitive (TransitiveRelation a)

Ord a => Graph (TransitiveRelation a)

Associated Types

type Vertex (TransitiveRelation a) :: *

Methods

empty :: TransitiveRelation a

vertex :: Vertex (TransitiveRelation a) -> TransitiveRelation a

overlay :: TransitiveRelation a -> TransitiveRelation a -> TransitiveRelation a

connect :: TransitiveRelation a -> TransitiveRelation a -> TransitiveRelation a

type Vertex (TransitiveRelation a)

type Vertex (TransitiveRelation a) = a

newtype PreorderRelation a

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

Constructors

PreorderRelation

Fields

• fromPreorder :: Relation a

Instances

Ord a => Eq (PreorderRelation a)

Methods

(==) :: PreorderRelation a -> PreorderRelation a -> Bool

(/=) :: PreorderRelation a -> PreorderRelation a -> Bool

(Num a, Ord a) => Num (PreorderRelation a)

Methods

(+) :: PreorderRelation a -> PreorderRelation a -> PreorderRelation a

(-) :: PreorderRelation a -> PreorderRelation a -> PreorderRelation a

(*) :: PreorderRelation a -> PreorderRelation a -> PreorderRelation a

negate :: PreorderRelation a -> PreorderRelation a

abs :: PreorderRelation a -> PreorderRelation a

signum :: PreorderRelation a -> PreorderRelation a

fromInteger :: Integer -> PreorderRelation a

(Ord a, Show a) => Show (PreorderRelation a)

Methods

showsPrec :: Int -> PreorderRelation a -> ShowS

show :: PreorderRelation a -> String

showList :: [PreorderRelation a] -> ShowS

Ord a => Preorder (PreorderRelation a)

Ord a => Transitive (PreorderRelation a)

Ord a => Reflexive (PreorderRelation a)

Ord a => Graph (PreorderRelation a)

Associated Types

type Vertex (PreorderRelation a) :: *

Methods

empty :: PreorderRelation a

vertex :: Vertex (PreorderRelation a) -> PreorderRelation a

overlay :: PreorderRelation a -> PreorderRelation a -> PreorderRelation a

connect :: PreorderRelation a -> PreorderRelation a -> PreorderRelation a

type Vertex (PreorderRelation a)

type Vertex (PreorderRelation a) = a