Algebra.PartialOrd

Partial orderings

class Eq a => PartialOrd a where

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

The relation that induces the partial ordering

comparable :: a -> a -> Bool

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

PartialOrd ()

Methods

leq :: () -> () -> Bool

comparable :: () -> () -> Bool

PartialOrd Void

Methods

leq :: Void -> Void -> Bool

comparable :: Void -> Void -> Bool

PartialOrd IntSet

Methods

leq :: IntSet -> IntSet -> Bool

comparable :: IntSet -> IntSet -> Bool

Eq a => PartialOrd [a]

leq = isInfixOf.

Methods

leq :: [a] -> [a] -> Bool

comparable :: [a] -> [a] -> Bool

PartialOrd v => PartialOrd (IntMap v)

Methods

leq :: IntMap v -> IntMap v -> Bool

comparable :: IntMap v -> IntMap v -> Bool

Ord a => PartialOrd (Set a)

Methods

leq :: Set a -> Set a -> Bool

comparable :: Set a -> Set a -> Bool

(Eq k, Hashable k) => PartialOrd (HashSet k)

Methods

leq :: HashSet k -> HashSet k -> Bool

comparable :: HashSet k -> HashSet k -> Bool

(Eq a, MeetSemiLattice a) => PartialOrd (Meet a)

Methods

leq :: Meet a -> Meet a -> Bool

comparable :: Meet a -> Meet a -> Bool

(Eq a, JoinSemiLattice a) => PartialOrd (Join a)

Methods

leq :: Join a -> Join a -> Bool

comparable :: Join a -> Join a -> Bool

(Eq a, Integral a) => PartialOrd (Divisibility a)

Methods

leq :: Divisibility a -> Divisibility a -> Bool

comparable :: Divisibility a -> Divisibility a -> Bool

PartialOrd a => PartialOrd (Op a)

Methods

leq :: Op a -> Op a -> Bool

comparable :: Op a -> Op a -> Bool

Ord a => PartialOrd (Ordered a)

Methods

leq :: Ordered a -> Ordered a -> Bool

comparable :: Ordered a -> Ordered a -> Bool

(PartialOrd a, PartialOrd b) => PartialOrd (a, b)

Methods

leq :: (a, b) -> (a, b) -> Bool

comparable :: (a, b) -> (a, b) -> Bool

(Ord k, PartialOrd v) => PartialOrd (Map k v)

Methods

leq :: Map k v -> Map k v -> Bool

comparable :: Map k v -> Map k v -> Bool

(Eq k, Hashable k, PartialOrd v) => PartialOrd (HashMap k v)

Methods

leq :: HashMap k v -> HashMap k v -> Bool

comparable :: HashMap k v -> HashMap k v -> Bool

(PartialOrd k, PartialOrd v) => PartialOrd (Lexicographic k v)

Methods

leq :: Lexicographic k v -> Lexicographic k v -> Bool

comparable :: Lexicographic k v -> Lexicographic k v -> Bool

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

The equality relation induced by the partial-order structure. It must obey the laws Reflexive: a == a Transitive: a == b && b == c ==> a == c

Fixed points of chains in partial orders

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

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

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

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

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

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

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

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