| 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 |
Algebra.Lattice
Description
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.
- 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
| Lattice Bool Source # | |
| Lattice () Source # | |
| Lattice Void Source # | |
| Lattice All Source # | |
| Lattice Any Source # | |
| Lattice IntSet Source # | |
| Lattice a => Lattice (Identity a) Source # | |
| Lattice a => Lattice (Endo a) Source # | |
| Lattice v => Lattice (IntMap v) Source # | |
| Ord a => Lattice (Set a) Source # | |
| (Eq a, Hashable a) => Lattice (HashSet a) Source # | |
| Integral a => Lattice (Divisibility a) Source # | |
| Lattice a => Lattice (Dropped a) Source # | |
| Lattice (FreeLattice a) Source # | |
| Lattice a => Lattice (Levitated a) Source # | |
| Lattice a => Lattice (Lifted a) Source # | |
| Lattice a => Lattice (Op a) Source # | |
| Ord a => Lattice (Ordered a) Source # | |
| Lattice v => Lattice (k -> v) Source # | |
| (Lattice a, Lattice b) => Lattice (a, b) Source # | |
| Lattice (Proxy * a) Source # | |
| (Ord k, Lattice v) => Lattice (Map k v) Source # | |
| (PartialOrd k, Lattice k, BoundedLattice v) => Lattice (Lexicographic k v) Source # | |
| Lattice a => Lattice (Const * a b) Source # | |
| Lattice a => Lattice (Tagged * t a) Source # | |
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 #
A join-semilattice with some element |bottom| that / approaches.
Identity: x \/ bottom == x
Minimal complete definition
Instances
class MeetSemiLattice a => BoundedMeetSemiLattice a where Source #
A meet-semilattice with some element |top| that / approaches.
Identity: x /\ top == x
Minimal complete definition
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 # | |
| 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 # | |
| Finite a => Finite (Meet a) Source # | |
| type Rep (Meet a) Source # | |
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 # | |
| 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 # | |
| Finite a => Finite (Join a) Source # | |
| type Rep (Join a) Source # | |
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.