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.