| Copyright | (C) 2010-2015 Maximilian Bolingbroke 2015-2019 Oleg Grenrus |
|---|---|
| License | BSD-3-Clause (see the file LICENSE) |
| Maintainer | Oleg Grenrus <oleg.grenrus@iki.fi> |
| Safe Haskell | Safe |
| Language | Haskell2010 |
Algebra.PartialOrd
Description
Synopsis
-
class
Eq
a =>
PartialOrd
a
where
- leq :: a -> a -> Bool
- comparable :: a -> a -> Bool
- partialOrdEq :: PartialOrd a => a -> a -> Bool
- lfpFrom :: PartialOrd a => a -> (a -> a) -> a
- unsafeLfpFrom :: Eq a => a -> (a -> a) -> a
- gfpFrom :: PartialOrd a => a -> (a -> a) -> a
- unsafeGfpFrom :: Eq a => a -> (a -> a) -> a
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
comparablea 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
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
comparablex y =leqx y||leqy x
Instances
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.