lattices-2.0.2: Fine-grained library for constructing and manipulating lattices

Copyright (C) 2010-2015 Maximilian Bolingbroke 2015-2019 Oleg Grenrus BSD-3-Clause (see the file LICENSE) Oleg Grenrus Safe Haskell2010

Algebra.PartialOrd

Description

Synopsis

Partial orderings

class Eq a => PartialOrd a where Source #

A partial ordering on sets (http://en.wikipedia.org/wiki/Partially_ordered_set) is a set equipped with a binary relation, leq, that obeys the following laws

Reflexive:     a leq a
Antisymmetric: a leq b && b leq a ==> a == b
Transitive:    a leq b && b leq c ==> a leq c

Two elements of the set are said to be comparable when they are are ordered with respect to the leq relation. So

comparable a b ==> a leq b || b leq a

If comparable always returns true then the relation leq defines a total ordering (and an Ord instance may be defined). Any Ord instance is trivially an instance of PartialOrd. Ordered provides a convenient wrapper to satisfy PartialOrd given Ord.

As an example consider the partial ordering on sets induced by set inclusion. Then for sets a and b,

a leq b

is true when a is a subset of b. Two sets are comparable if one is a subset of the other. Concretely

a = {1, 2, 3}
b = {1, 3, 4}
c = {1, 2}

a leq a = True
a leq b = False
a leq c = False
b leq a = False
b leq b = True
b leq c = False
c leq a = True
c leq b = False
c leq c = True

comparable a b = False
comparable a c = True
comparable b c = False

Minimal complete definition

leq

Methods

leq :: a -> a -> Bool Source #

The relation that induces the partial ordering

comparable :: a -> a -> Bool Source #

Whether two elements are ordered with respect to the relation. A default implementation is given by

comparable x y = leq x y || leq y x
Instances
 Source # Since: 2 Instance detailsDefined in Algebra.PartialOrd Methodsleq :: Bool -> Bool -> Bool Source # Source # Instance detailsDefined in Algebra.PartialOrd Methodsleq :: () -> () -> Bool Source #comparable :: () -> () -> Bool Source # Source # Instance detailsDefined in Algebra.PartialOrd Methodsleq :: Void -> Void -> Bool Source # Source # Instance detailsDefined in Algebra.PartialOrd Methodsleq :: All -> All -> Bool Source # Source # Instance detailsDefined in Algebra.PartialOrd Methodsleq :: Any -> Any -> Bool Source # Source # Instance detailsDefined in Algebra.PartialOrd Methods Source # Instance detailsDefined in Algebra.Lattice.N5 Methodsleq :: N5 -> N5 -> Bool Source # Source # Instance detailsDefined in Algebra.Lattice.M3 Methodsleq :: M3 -> M3 -> Bool Source # Source # Instance detailsDefined in Algebra.Lattice.ZeroHalfOne Methods Source # Instance detailsDefined in Algebra.Lattice.M2 Methodsleq :: M2 -> M2 -> Bool Source # Eq a => PartialOrd [a] Source # leq = isSequenceOf. Instance detailsDefined in Algebra.PartialOrd Methodsleq :: [a] -> [a] -> Bool Source #comparable :: [a] -> [a] -> Bool Source # (PartialOrd v, Finite v) => PartialOrd (Endo v) Source # Instance detailsDefined in Algebra.PartialOrd.Instances Methodsleq :: Endo v -> Endo v -> Bool Source #comparable :: Endo v -> Endo v -> Bool Source # PartialOrd v => PartialOrd (IntMap v) Source # Instance detailsDefined in Algebra.PartialOrd Methodsleq :: IntMap v -> IntMap v -> Bool Source #comparable :: IntMap v -> IntMap v -> Bool Source # Ord a => PartialOrd (Set a) Source # Instance detailsDefined in Algebra.PartialOrd Methodsleq :: Set a -> Set a -> Bool Source #comparable :: Set a -> Set a -> Bool Source # (Eq k, Hashable k) => PartialOrd (HashSet k) Source # Instance detailsDefined in Algebra.PartialOrd Methodsleq :: HashSet k -> HashSet k -> Bool Source #comparable :: HashSet k -> HashSet k -> Bool Source # (Eq a, Lattice a) => PartialOrd (Meet a) Source # Instance detailsDefined in Algebra.Lattice Methodsleq :: Meet a -> Meet a -> Bool Source #comparable :: Meet a -> Meet a -> Bool Source # (Eq a, Lattice a) => PartialOrd (Join a) Source # Instance detailsDefined in Algebra.Lattice Methodsleq :: Join a -> Join a -> Bool Source #comparable :: Join a -> Join a -> Bool Source # Eq a => PartialOrd (Wide a) Source # Instance detailsDefined in Algebra.Lattice.Wide Methodsleq :: Wide a -> Wide a -> Bool Source #comparable :: Wide a -> Wide a -> Bool Source # PartialOrd a => PartialOrd (Op a) Source # Instance detailsDefined in Algebra.Lattice.Op Methodsleq :: Op a -> Op a -> Bool Source #comparable :: Op a -> Op a -> Bool Source # PartialOrd a => PartialOrd (Lifted a) Source # Instance detailsDefined in Algebra.Lattice.Lifted Methodsleq :: Lifted a -> Lifted a -> Bool Source #comparable :: Lifted a -> Lifted a -> Bool Source # Source # Instance detailsDefined in Algebra.Lattice.Levitated Methodsleq :: Levitated a -> Levitated a -> Bool Source #comparable :: Levitated a -> Levitated a -> Bool Source # Ord a => PartialOrd (Free a) Source # Instance detailsDefined in Algebra.Lattice.Free Methodsleq :: Free a -> Free a -> Bool Source #comparable :: Free a -> Free a -> Bool Source # PartialOrd a => PartialOrd (Dropped a) Source # Instance detailsDefined in Algebra.Lattice.Dropped Methodsleq :: Dropped a -> Dropped a -> Bool Source #comparable :: Dropped a -> Dropped a -> Bool Source # (Eq a, Integral a) => PartialOrd (Divisibility a) Source # Instance detailsDefined in Algebra.Lattice.Divisibility Methodsleq :: Divisibility a -> Divisibility a -> Bool Source # Ord a => PartialOrd (Ordered a) Source # Instance detailsDefined in Algebra.Lattice.Ordered Methodsleq :: Ordered a -> Ordered a -> Bool Source #comparable :: Ordered a -> Ordered a -> Bool Source # Ord a => PartialOrd (Free a) Source # Instance detailsDefined in Algebra.Heyting.Free Methodsleq :: Free a -> Free a -> Bool Source #comparable :: Free a -> Free a -> Bool Source # (PartialOrd v, Finite k) => PartialOrd (k -> v) Source # Eq (k -> v) is from Eq Instance detailsDefined in Algebra.PartialOrd.Instances Methodsleq :: (k -> v) -> (k -> v) -> Bool Source #comparable :: (k -> v) -> (k -> v) -> Bool Source # (PartialOrd a, PartialOrd b) => PartialOrd (Either a b) Source # Since: 2.0.1 Instance detailsDefined in Algebra.PartialOrd Methodsleq :: Either a b -> Either a b -> Bool Source #comparable :: Either a b -> Either a b -> Bool Source # (PartialOrd a, PartialOrd b) => PartialOrd (a, b) Source # Instance detailsDefined in Algebra.PartialOrd Methodsleq :: (a, b) -> (a, b) -> Bool Source #comparable :: (a, b) -> (a, b) -> Bool Source # (Ord k, PartialOrd v) => PartialOrd (Map k v) Source # Instance detailsDefined in Algebra.PartialOrd Methodsleq :: Map k v -> Map k v -> Bool Source #comparable :: Map k v -> Map k v -> Bool Source # (Eq k, Hashable k, PartialOrd v) => PartialOrd (HashMap k v) Source # Instance detailsDefined in Algebra.PartialOrd Methodsleq :: HashMap k v -> HashMap k v -> Bool Source #comparable :: HashMap k v -> HashMap k v -> Bool Source # (PartialOrd a, PartialOrd b) => PartialOrd (Stacked a b) Source # Instance detailsDefined in Algebra.Lattice.Stacked Methodsleq :: Stacked a b -> Stacked a b -> Bool Source #comparable :: Stacked a b -> Stacked a b -> Bool Source # (PartialOrd k, PartialOrd v) => PartialOrd (Lexicographic k v) Source # Instance detailsDefined in Algebra.Lattice.Lexicographic Methodsleq :: Lexicographic k v -> Lexicographic k v -> Bool Source #comparable :: Lexicographic k v -> Lexicographic k v -> Bool Source #

partialOrdEq :: PartialOrd a => a -> a -> Bool Source #

The equality relation induced by the partial-order structure. It satisfies the laws of an equivalence relation: Reflexive: a == a Symmetric: a == b ==> b == a Transitive: a == b && b == c ==> a == c

Fixed points of chains in partial orders

lfpFrom :: PartialOrd a => a -> (a -> a) -> a Source #

Least point of a partially ordered monotone function. Checks that the function is monotone.

unsafeLfpFrom :: Eq a => a -> (a -> a) -> a Source #

Least point of a partially ordered monotone function. Does not checks that the function is monotone.

gfpFrom :: PartialOrd a => a -> (a -> a) -> a Source #

Greatest fixed point of a partially ordered antinone function. Checks that the function is antinone.

unsafeGfpFrom :: Eq a => a -> (a -> a) -> a Source #

Greatest fixed point of a partially ordered antinone function. Does not check that the function is antinone.