- newtype Poset t = Poset ([t], t -> t -> Bool)
- chainN :: Int -> Poset Int
- antichainN :: Int -> Poset Int
- posetD :: Int -> Poset Int
- posetB :: Int -> Poset [Int]
- posetP :: Int -> Poset [[Int]]
- posetL :: FiniteField fq => Int -> [fq] -> Poset [[fq]]
- subposet :: Poset a -> (a -> Bool) -> Poset a
- dsum :: Poset a -> Poset b -> Poset (Either a b)
- dprod :: Poset a -> Poset b -> Poset (a, b)
- dual :: Poset a -> Poset a
- hasseDigraph :: Eq a => Poset a -> Digraph a
- reachabilityPoset :: Ord a => Digraph a -> Poset a
- isOrderPreserving :: (a -> b) -> Poset a -> Poset b -> Bool
- isOrderIso :: (Eq a, Eq b) => Poset a -> Poset b -> Bool
Documentation
A poset is represented as a pair (set,po), where set is the underlying set of the poset, and po is the partial order relation
chainN :: Int -> Poset IntSource
A chain is a poset in which every pair of elements is comparable (ie either x <= y or y <= x). It is therefore a linear or total order. chainN n is the poset consisting of the numbers [1..n] ordered by (<=)
antichainN :: Int -> Poset IntSource
An antichain is a poset in which distinct elements are incomparable. antichainN n is the poset consisting of [1..n], with x <= y only when x == y.
posetP :: Int -> Poset [[Int]]Source
posetP n is the lattice of partitions of [1..n] ordered by refinement
posetL :: FiniteField fq => Int -> [fq] -> Poset [[fq]]Source
posetL n fq is the lattice of subspaces of the vector space Fq^n, ordered by inclusion. Subspaces are represented by their reduced row echelon form.
hasseDigraph :: Eq a => Poset a -> Digraph aSource
Given a poset (X,<=), we say that y covers x, written x -< y, if x < y and there is no z in X with x < z < y. The Hasse digraph of a poset is the digraph whose vertices are the elements of the poset, with an edge between every pair (x,y) with x -< y. The Hasse digraph can be represented diagrammatically as a Hasse diagram, by drawing x below y whenever x -< y.
reachabilityPoset :: Ord a => Digraph a -> Poset aSource
Given a DAG (directed acyclic graph), return the poset consisting of the vertices of the DAG, ordered by reachability. This can be used to recover a poset from its Hasse digraph.
isOrderPreserving :: (a -> b) -> Poset a -> Poset b -> BoolSource