lattices-1.1: Fine-grained library for constructing and manipulating lattices

Algebra.Lattice

Synopsis

Unbounded lattices

class JoinSemiLattice a whereSource

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

Associativity: x `join` (y `join` z) == (x `join` y) `join` z Commutativity: x `join` y == y `join` x Idempotency: x `join` x == x

Methods

join :: a -> a -> aSource

Instances

 JoinSemiLattice Bool JoinSemiLattice IntSet JoinSemiLattice v => JoinSemiLattice (IntMap v) Ord a => JoinSemiLattice (Set a) JoinSemiLattice a => JoinSemiLattice (Dropped a) JoinSemiLattice a => JoinSemiLattice (Levitated a) JoinSemiLattice a => JoinSemiLattice (Lifted a) JoinSemiLattice v => JoinSemiLattice (k -> v) (JoinSemiLattice a, JoinSemiLattice b) => JoinSemiLattice (a, b) (Ord k, JoinSemiLattice v) => JoinSemiLattice (Map k v)

class MeetSemiLattice a whereSource

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

Associativity: x `meet` (y `meet` z) == (x `meet` y) `meet` z Commutativity: x `meet` y == y `meet` x Idempotency: x `meet` x == x

Methods

meet :: a -> a -> aSource

Instances

 MeetSemiLattice Bool (Ord a, Enumerable a) => MeetSemiLattice (Set (Enumerated a)) MeetSemiLattice a => MeetSemiLattice (Dropped a) MeetSemiLattice a => MeetSemiLattice (Levitated a) MeetSemiLattice a => MeetSemiLattice (Lifted a) MeetSemiLattice v => MeetSemiLattice (k -> v) (MeetSemiLattice a, MeetSemiLattice b) => MeetSemiLattice (a, b) (Ord k, Enumerable k, MeetSemiLattice v) => MeetSemiLattice (Map (Enumerated k) v)

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 `join` (a `meet` b) == a `meet` (a `join` b) == a

Instances

 Lattice Bool (Ord a, Enumerable a) => Lattice (Set (Enumerated a)) Lattice a => Lattice (Dropped a) Lattice a => Lattice (Levitated a) Lattice a => Lattice (Lifted a) Lattice v => Lattice (k -> v) (Lattice a, Lattice b) => Lattice (a, b) (Ord k, Enumerable k, Lattice v) => Lattice (Map (Enumerated k) v)

joinLeq :: (Eq a, JoinSemiLattice a) => a -> a -> BoolSource

The partial ordering induced by the join-semilattice structure

joins1 :: JoinSemiLattice a => [a] -> aSource

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

meetLeq :: (Eq a, MeetSemiLattice a) => a -> a -> BoolSource

The partial ordering induced by the meet-semilattice structure

meets1 :: MeetSemiLattice a => [a] -> aSource

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

Bounded lattices

class JoinSemiLattice a => BoundedJoinSemiLattice a whereSource

A join-semilattice with some element |bottom| that `join` approaches.

Identity: x `join` bottom == x

Methods

bottom :: aSource

Instances

 BoundedJoinSemiLattice Bool BoundedJoinSemiLattice IntSet JoinSemiLattice v => BoundedJoinSemiLattice (IntMap v) Ord a => BoundedJoinSemiLattice (Set a) BoundedJoinSemiLattice a => BoundedJoinSemiLattice (Dropped a) JoinSemiLattice a => BoundedJoinSemiLattice (Levitated a) JoinSemiLattice a => BoundedJoinSemiLattice (Lifted a) BoundedJoinSemiLattice v => BoundedJoinSemiLattice (k -> v) (BoundedJoinSemiLattice a, BoundedJoinSemiLattice b) => BoundedJoinSemiLattice (a, b) (Ord k, JoinSemiLattice v) => BoundedJoinSemiLattice (Map k v)

class MeetSemiLattice a => BoundedMeetSemiLattice a whereSource

A meet-semilattice with some element |top| that `meet` approaches.

Identity: x `meet` top == x

Methods

top :: aSource

Instances

 BoundedMeetSemiLattice Bool (Ord a, Enumerable a) => BoundedMeetSemiLattice (Set (Enumerated a)) MeetSemiLattice a => BoundedMeetSemiLattice (Dropped a) MeetSemiLattice a => BoundedMeetSemiLattice (Levitated a) BoundedMeetSemiLattice a => BoundedMeetSemiLattice (Lifted a) BoundedMeetSemiLattice v => BoundedMeetSemiLattice (k -> v) (BoundedMeetSemiLattice a, BoundedMeetSemiLattice b) => BoundedMeetSemiLattice (a, b) (Ord k, Enumerable k, BoundedMeetSemiLattice v) => BoundedMeetSemiLattice (Map (Enumerated k) v)

Lattices with both bounds

Instances

 BoundedLattice Bool (Ord a, Enumerable a) => BoundedLattice (Set (Enumerated a)) BoundedLattice a => BoundedLattice (Dropped a) BoundedLattice a => BoundedLattice (Levitated a) BoundedLattice a => BoundedLattice (Lifted a) BoundedLattice v => BoundedLattice (k -> v) (BoundedLattice a, BoundedLattice b) => BoundedLattice (a, b) (Ord k, Enumerable k, BoundedLattice v) => BoundedLattice (Map (Enumerated k) v)

joins :: BoundedJoinSemiLattice a => [a] -> aSource

The join of a list of join-semilattice elements

meets :: BoundedMeetSemiLattice a => [a] -> aSource

The meet of a list of meet-semilattice elements

Fixed points of chains in lattices

lfp :: (Eq a, BoundedJoinSemiLattice a) => (a -> a) -> aSource

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) -> aSource

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) -> aSource

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) -> aSource

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.