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

Algebra.Lattice

Contents

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

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

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

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.

lfpFrom :: (Eq a, BoundedJoinSemiLattice a) => 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.

gfpFrom :: (Eq a, BoundedMeetSemiLattice a) => 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.