Safe Haskell | Safe |
---|---|

Language | Haskell2010 |

## Synopsis

- class Prd a => Lattice a where
- (\/) :: a -> a -> a
- (/\) :: a -> a -> a
- fromSubset :: Min a => Set a -> a

- joinLeq :: Lattice a => a -> a -> Bool
- meetLeq :: Lattice a => a -> a -> Bool
- join :: (Min a, Lattice a, Foldable f) => f a -> a
- meet :: (Max a, Lattice a, Foldable f) => f a -> a
- join1 :: (Lattice a, Foldable1 f) => f a -> a
- meet1 :: (Lattice a, Foldable1 f) => f a -> a
- median :: Lattice a => a -> a -> a -> a
- newtype Join a = Join {
- unJoin :: a

- newtype Meet a = Meet {
- unMeet :: a

# Documentation

class Prd a => Lattice a where Source #

Lattices.

A lattice is a partially ordered set in which every two elements have a unique join (least upper bound or supremum) and a unique meet (greatest lower bound or infimum).

See http://en.wikipedia.org/wiki/Lattice_(order) and http://en.wikipedia.org/wiki/Absorption_law.

*Laws*

x`\/`

`maximal`

≡ x

*Corollary*

x`\/`

`maximal`

≡⟨ identity ⟩ (x`\/`

`maximal`

)`/\`

`maximal`

≡⟨ absorption ⟩`maximal`

x`\/`

`minimal`

≡ x

*Corollary*

x`/\`

`minimal`

≡⟨ identity ⟩ (x`/\`

`minimal`

)`\/`

`minimal`

≡⟨ absorption ⟩`minimal`

*Associativity*

x`\/`

(y`\/`

z) ≡ (x`\/`

y)`\/`

z x`/\`

(y`/\`

z) ≡ (x`/\`

y)`/\`

z

*Commutativity*

x`\/`

y ≡ y`\/`

x x`/\`

y ≡ y`/\`

x

*Idempotency*

x`\/`

x ≡ x x`/\`

x ≡ x

*Absorption*

(x`\/`

y)`/\`

y ≡ y (x`/\`

y)`\/`

y ≡ y

(\/) :: a -> a -> a infixr 5 Source #

(/\) :: a -> a -> a infixr 6 Source #

fromSubset :: Min a => Set a -> a Source #

Lattice morphism.

## Instances

Lattice Bool Source # | |

Lattice () Source # | |

Lattice All Source # | |

Lattice Any Source # | |

Lattice IntSet Source # | |

Lattice Unsigned Source # | |

Lattice a => Lattice (Maybe a) Source # | |

Lattice a => Lattice (Down a) Source # | |

Lattice a => Lattice (IntMap a) Source # | |

Ord a => Lattice (Set a) Source # | |

Ord a => Lattice (Ordered a) Source # | |

(Lattice a, Lattice b) => Lattice (Either a b) Source # | |

(Lattice a, Lattice b) => Lattice (a, b) Source # | |

(Ord k, Lattice a) => Lattice (Map k a) Source # | |

joinLeq :: Lattice a => a -> a -> Bool Source #

The partial ordering induced by the join-semilattice structure

join1 :: (Lattice a, Foldable1 f) => f a -> a Source #

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

meet1 :: (Lattice a, Foldable1 f) => f a -> a Source #

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

median :: Lattice a => a -> a -> a -> a Source #

Birkhoff's self-dual ternary median operation.

TODO: require a *Dioid* instance.

median x x y ≡ x

median x y z ≡ median z x y

median x y z ≡ median x z y

median (median x w y) w z ≡ median x w (median y w z)

## Instances

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

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

Defined in Data.Prd.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 # | |

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

Generic (Join a) Source # | |

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

(Lattice a, Min a) => Monoid (Join a) Source # | |

(Eq a, Lattice a) => Prd (Join a) Source # | |

type Rep (Join a) Source # | |

Defined in Data.Prd.Lattice |

## Instances

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

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

Defined in Data.Prd.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 # | |

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

Generic (Meet a) Source # | |

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

(Lattice a, Max a) => Monoid (Meet a) Source # | |

type Rep (Meet a) Source # | |

Defined in Data.Prd.Lattice |