Copyright | (C) 2010-2015 Maximilian Bolingbroke |
---|---|
License | BSD-3-Clause (see the file LICENSE) |
Maintainer | Oleg Grenrus <oleg.grenrus@iki.fi> |
Safe Haskell | Safe |
Language | Haskell2010 |
- class Eq a => PartialOrd a where
- 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
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
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
PartialOrd IntSet Source # | |
PartialOrd v => PartialOrd (IntMap v) Source # | |
Ord a => PartialOrd (Set a) Source # | |
(Eq a, Integral a) => PartialOrd (Divisibility a) Source # | |
PartialOrd a => PartialOrd (Op a) Source # | |
Ord a => PartialOrd (Ordered a) Source # | |
(PartialOrd a, PartialOrd b) => PartialOrd (a, b) Source # | |
(Ord k, PartialOrd v) => PartialOrd (Map k v) Source # | |
(PartialOrd k, PartialOrd v) => PartialOrd (Lexicographic k v) Source # | |
partialOrdEq :: PartialOrd a => a -> a -> Bool Source #
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 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.