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 |

In mathematics, a lattice is a partially ordered set in which every
two elements have a unique supremum (also called a least upper bound
or `join`

) and a unique infimum (also called a greatest lower bound or
`meet`

).

In this module lattices are defined using `meet`

and `join`

operators,
as it's constructive one.

## Synopsis

- class JoinSemiLattice a where
- class MeetSemiLattice a where
- class (JoinSemiLattice a, MeetSemiLattice a) => Lattice a
- joinLeq :: (Eq a, JoinSemiLattice a) => a -> a -> Bool
- joins1 :: (JoinSemiLattice a, Foldable1 f) => f a -> a
- meetLeq :: (Eq a, MeetSemiLattice a) => a -> a -> Bool
- meets1 :: (MeetSemiLattice a, Foldable1 f) => f a -> a
- class JoinSemiLattice a => BoundedJoinSemiLattice a where
- class MeetSemiLattice a => BoundedMeetSemiLattice a where
- class (Lattice a, BoundedJoinSemiLattice a, BoundedMeetSemiLattice a) => BoundedLattice a
- joins :: (BoundedJoinSemiLattice a, Foldable f) => f a -> a
- meets :: (BoundedMeetSemiLattice a, Foldable f) => f a -> a
- fromBool :: BoundedLattice a => Bool -> a
- newtype Meet a = Meet {
- getMeet :: a

- newtype Join a = Join {
- getJoin :: a

- lfp :: (Eq a, BoundedJoinSemiLattice a) => (a -> a) -> a
- lfpFrom :: (Eq a, BoundedJoinSemiLattice a) => a -> (a -> a) -> a
- unsafeLfp :: (Eq a, BoundedJoinSemiLattice a) => (a -> a) -> a
- gfp :: (Eq a, BoundedMeetSemiLattice a) => (a -> a) -> a
- gfpFrom :: (Eq a, BoundedMeetSemiLattice a) => a -> (a -> a) -> a
- unsafeGfp :: (Eq a, BoundedMeetSemiLattice a) => (a -> a) -> a

# Unbounded lattices

class JoinSemiLattice a where Source #

A algebraic structure with element joins: http://en.wikipedia.org/wiki/Semilattice

Associativity: x \/ (y \/ z) == (x \/ y) \/ z Commutativity: x \/ y == y \/ x Idempotency: x \/ x == x

## Instances

class MeetSemiLattice a where Source #

A algebraic structure with element meets: http://en.wikipedia.org/wiki/Semilattice

Associativity: x /\ (y /\ z) == (x /\ y) /\ z Commutativity: x /\ y == y /\ x Idempotency: x /\ x == x

## Instances

class (JoinSemiLattice a, MeetSemiLattice a) => Lattice a Source #

The combination of two semi lattices makes a lattice if the absorption law holds: see http://en.wikipedia.org/wiki/Absorption_law and http://en.wikipedia.org/wiki/Lattice_(order)

Absorption: a \/ (a /\ b) == a /\ (a \/ b) == a

## Instances

joinLeq :: (Eq a, JoinSemiLattice a) => a -> a -> Bool Source #

The partial ordering induced by the join-semilattice structure

joins1 :: (JoinSemiLattice a, Foldable1 f) => f a -> a Source #

The join of at a list of join-semilattice elements (of length at least one)

meetLeq :: (Eq a, MeetSemiLattice a) => a -> a -> Bool Source #

The partial ordering induced by the meet-semilattice structure

meets1 :: (MeetSemiLattice a, Foldable1 f) => f a -> a Source #

The meet of at a list of meet-semilattice elements (of length at least one)

# Bounded lattices

class JoinSemiLattice a => BoundedJoinSemiLattice a where Source #

## Instances

class MeetSemiLattice a => BoundedMeetSemiLattice a where Source #

## Instances

class (Lattice a, BoundedJoinSemiLattice a, BoundedMeetSemiLattice a) => BoundedLattice a Source #

Lattices with both bounds

## Instances

joins :: (BoundedJoinSemiLattice a, Foldable f) => f a -> a Source #

The join of a list of join-semilattice elements

meets :: (BoundedMeetSemiLattice a, Foldable f) => f a -> a Source #

The meet of a list of meet-semilattice elements

# Monoid wrappers

Monoid wrapper for MeetSemiLattice

## Instances

Monad Meet Source # | |

Functor Meet Source # | |

Applicative Meet Source # | |

MonadZip Meet Source # | |

Bounded a => Bounded (Meet a) Source # | |

Eq a => Eq (Meet a) Source # | |

Data a => Data (Meet a) Source # | |

Defined in Algebra.Lattice gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Meet a -> c (Meet a) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Meet a) # toConstr :: Meet a -> Constr # dataTypeOf :: Meet a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Meet a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Meet a)) # gmapT :: (forall b. Data b => b -> b) -> Meet a -> Meet a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Meet a -> r # gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Meet a -> r # gmapQ :: (forall d. Data d => d -> u) -> Meet a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> Meet a -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> Meet a -> m (Meet a) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Meet a -> m (Meet a) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Meet a -> m (Meet a) # | |

Ord a => Ord (Meet a) Source # | |

Read a => Read (Meet a) Source # | |

Show a => Show (Meet a) Source # | |

Generic (Meet a) Source # | |

MeetSemiLattice a => Semigroup (Meet a) Source # | |

BoundedMeetSemiLattice a => Monoid (Meet a) Source # | |

Universe a => Universe (Meet a) Source # | |

Defined in Algebra.Lattice | |

Finite a => Finite (Meet a) Source # | |

Defined in Algebra.Lattice | |

(Eq a, MeetSemiLattice a) => PartialOrd (Meet a) Source # | |

type Rep (Meet a) Source # | |

Defined in Algebra.Lattice |

Monoid wrapper for JoinSemiLattice

## Instances

Monad Join Source # | |

Functor Join Source # | |

Applicative Join Source # | |

MonadZip Join Source # | |

Bounded a => Bounded (Join a) Source # | |

Eq a => Eq (Join a) Source # | |

Data a => Data (Join a) Source # | |

Defined in Algebra.Lattice gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Join a -> c (Join a) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Join a) # toConstr :: Join a -> Constr # dataTypeOf :: Join a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Join a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Join a)) # gmapT :: (forall b. Data b => b -> b) -> Join a -> Join a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Join a -> r # gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Join a -> r # gmapQ :: (forall d. Data d => d -> u) -> Join a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> Join a -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> Join a -> m (Join a) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Join a -> m (Join a) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Join a -> m (Join a) # | |

Ord a => Ord (Join a) Source # | |

Read a => Read (Join a) Source # | |

Show a => Show (Join a) Source # | |

Generic (Join a) Source # | |

JoinSemiLattice a => Semigroup (Join a) Source # | |

BoundedJoinSemiLattice a => Monoid (Join a) Source # | |

Universe a => Universe (Join a) Source # | |

Defined in Algebra.Lattice | |

Finite a => Finite (Join a) Source # | |

Defined in Algebra.Lattice | |

(Eq a, JoinSemiLattice a) => PartialOrd (Join a) Source # | |

type Rep (Join a) Source # | |

Defined in Algebra.Lattice |

# Fixed points of chains in lattices

lfp :: (Eq a, BoundedJoinSemiLattice a) => (a -> a) -> a Source #

Implementation of Kleene fixed-point theorem http://en.wikipedia.org/wiki/Kleene_fixed-point_theorem. Forces the function to be monotone.

lfpFrom :: (Eq a, BoundedJoinSemiLattice a) => a -> (a -> a) -> a Source #

Implementation of Kleene fixed-point theorem http://en.wikipedia.org/wiki/Kleene_fixed-point_theorem. Forces the function to be monotone.

unsafeLfp :: (Eq a, BoundedJoinSemiLattice a) => (a -> a) -> a Source #

Implementation of Kleene fixed-point theorem http://en.wikipedia.org/wiki/Kleene_fixed-point_theorem. Assumes that the function is monotone and does not check if that is correct.

gfp :: (Eq a, BoundedMeetSemiLattice a) => (a -> a) -> a Source #

Implementation of Kleene fixed-point theorem http://en.wikipedia.org/wiki/Kleene_fixed-point_theorem. Forces the function to be antinone.

gfpFrom :: (Eq a, BoundedMeetSemiLattice a) => a -> (a -> a) -> a Source #

Implementation of Kleene fixed-point theorem http://en.wikipedia.org/wiki/Kleene_fixed-point_theorem. Forces the function to be antinone.

unsafeGfp :: (Eq a, BoundedMeetSemiLattice a) => (a -> a) -> a Source #

Implementation of Kleene fixed-point theorem http://en.wikipedia.org/wiki/Kleene_fixed-point_theorem. Assumes that the function is antinone and does not check if that is correct.