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 |

## 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

`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

## 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.