Algebra.Lattice

Unbounded lattices

class JoinSemiLattice a where

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

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 where

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

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

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

(JoinSemiLattice (Set (Enumerated a)), MeetSemiLattice (Set (Enumerated a)), Ord a, Enumerable a) => Lattice (Set (Enumerated a))

(JoinSemiLattice (Dropped a), MeetSemiLattice (Dropped a), Lattice a) => Lattice (Dropped a)

(JoinSemiLattice (Levitated a), MeetSemiLattice (Levitated a), Lattice a) => Lattice (Levitated a)

(JoinSemiLattice (Lifted a), MeetSemiLattice (Lifted a), Lattice a) => Lattice (Lifted a)

(JoinSemiLattice (k -> v), MeetSemiLattice (k -> v), Lattice v) => Lattice (k -> v)

(JoinSemiLattice (a, b), MeetSemiLattice (a, b), Lattice a, Lattice b) => Lattice (a, b)

(JoinSemiLattice (Map (Enumerated k) v), MeetSemiLattice (Map (Enumerated k) v), Ord k, Enumerable k, Lattice v) => Lattice (Map (Enumerated k) v)

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

The partial ordering induced by the join-semilattice structure

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

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

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

The partial ordering induced by the meet-semilattice structure

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

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

Bounded lattices

class JoinSemiLattice a => BoundedJoinSemiLattice a where

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

Identity: x join bottom == x

Methods

bottom :: a

Instances

BoundedJoinSemiLattice Bool

BoundedJoinSemiLattice IntSet

(JoinSemiLattice (IntMap v), JoinSemiLattice v) => BoundedJoinSemiLattice (IntMap v)

(JoinSemiLattice (Set a), Ord a) => BoundedJoinSemiLattice (Set a)

(JoinSemiLattice (Dropped a), BoundedJoinSemiLattice a) => BoundedJoinSemiLattice (Dropped a)

(JoinSemiLattice (Levitated a), JoinSemiLattice a) => BoundedJoinSemiLattice (Levitated a)

(JoinSemiLattice (Lifted a), JoinSemiLattice a) => BoundedJoinSemiLattice (Lifted a)

(JoinSemiLattice (k -> v), BoundedJoinSemiLattice v) => BoundedJoinSemiLattice (k -> v)

(JoinSemiLattice (a, b), BoundedJoinSemiLattice a, BoundedJoinSemiLattice b) => BoundedJoinSemiLattice (a, b)

(JoinSemiLattice (Map k v), Ord k, JoinSemiLattice v) => BoundedJoinSemiLattice (Map k v)

class MeetSemiLattice a => BoundedMeetSemiLattice a where

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

Identity: x meet top == x

Methods

top :: a

Instances

BoundedMeetSemiLattice Bool

(MeetSemiLattice (Set (Enumerated a)), Ord a, Enumerable a) => BoundedMeetSemiLattice (Set (Enumerated a))

(MeetSemiLattice (Dropped a), MeetSemiLattice a) => BoundedMeetSemiLattice (Dropped a)

(MeetSemiLattice (Levitated a), MeetSemiLattice a) => BoundedMeetSemiLattice (Levitated a)

(MeetSemiLattice (Lifted a), BoundedMeetSemiLattice a) => BoundedMeetSemiLattice (Lifted a)

(MeetSemiLattice (k -> v), BoundedMeetSemiLattice v) => BoundedMeetSemiLattice (k -> v)

(MeetSemiLattice (a, b), BoundedMeetSemiLattice a, BoundedMeetSemiLattice b) => BoundedMeetSemiLattice (a, b)

(MeetSemiLattice (Map (Enumerated k) v), Ord k, Enumerable k, BoundedMeetSemiLattice v) => BoundedMeetSemiLattice (Map (Enumerated k) v)

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

Lattices with both bounds

Instances

BoundedLattice Bool

(Lattice (Set (Enumerated a)), BoundedJoinSemiLattice (Set (Enumerated a)), BoundedMeetSemiLattice (Set (Enumerated a)), Ord a, Enumerable a) => BoundedLattice (Set (Enumerated a))

(Lattice (Dropped a), BoundedJoinSemiLattice (Dropped a), BoundedMeetSemiLattice (Dropped a), BoundedLattice a) => BoundedLattice (Dropped a)

(Lattice (Levitated a), BoundedJoinSemiLattice (Levitated a), BoundedMeetSemiLattice (Levitated a), BoundedLattice a) => BoundedLattice (Levitated a)

(Lattice (Lifted a), BoundedJoinSemiLattice (Lifted a), BoundedMeetSemiLattice (Lifted a), BoundedLattice a) => BoundedLattice (Lifted a)

(Lattice (k -> v), BoundedJoinSemiLattice (k -> v), BoundedMeetSemiLattice (k -> v), BoundedLattice v) => BoundedLattice (k -> v)

(Lattice (a, b), BoundedJoinSemiLattice (a, b), BoundedMeetSemiLattice (a, b), BoundedLattice a, BoundedLattice b) => BoundedLattice (a, b)

(Lattice (Map (Enumerated k) v), BoundedJoinSemiLattice (Map (Enumerated k) v), BoundedMeetSemiLattice (Map (Enumerated k) v), Ord k, Enumerable k, BoundedLattice v) => BoundedLattice (Map (Enumerated k) v)

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

The join of a list of join-semilattice elements

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

The meet of a list of meet-semilattice elements

Fixed points of chains in lattices

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

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

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

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

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

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

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.