Safe Haskell | None |
---|---|
Language | Haskell2010 |
Control.SetAlgebra
Synopsis
- data List k v
- data BiMap v a b
- type Bimap k v = BiMap v k v
- data Single k v where
- class Iter f => Basic f where
- class Iter f where
- nxt :: f a b -> Collect (a, b, f a b)
- lub :: Ord k => k -> f k b -> Collect (k, b, f k b)
- hasNxt :: f a b -> Maybe (a, b, f a b)
- hasLub :: Ord k => k -> f k b -> Maybe (k, b, f k b)
- haskey :: Ord key => key -> f key b -> Bool
- isnull :: f k v -> Bool
- lookup :: Ord key => key -> f key rng -> Maybe rng
- element :: Ord k => k -> f k v -> Collect ()
- class Embed concrete base | concrete -> base where
- class HasExp s t | s -> t where
- data BaseRep f k v where
- dom :: (Ord k, HasExp s (f k v)) => s -> Exp (Sett k ())
- rng :: (Ord k, Ord v) => HasExp s (f k v) => s -> Exp (Sett v ())
- dexclude :: (Ord k, Iter g, HasExp s1 (g k ()), HasExp s2 (f k v)) => s1 -> s2 -> Exp (f k v)
- drestrict :: (Ord k, HasExp s1 (Sett k ()), HasExp s2 (f k v)) => s1 -> s2 -> Exp (f k v)
- rexclude :: (Ord k, Iter g, Ord v, HasExp s1 (f k v), HasExp s2 (g v ())) => s1 -> s2 -> Exp (f k v)
- rrestrict :: (Ord k, Iter g, Ord v, HasExp s1 (f k v), HasExp s2 (g v ())) => s1 -> s2 -> Exp (f k v)
- unionleft :: (Show k, Show v, Ord k, HasExp s1 (f k v), HasExp s2 (g k v)) => s1 -> s2 -> Exp (f k v)
- unionright :: (Ord k, HasExp s1 (f k v), HasExp s2 (g k v)) => s1 -> s2 -> Exp (f k v)
- unionplus :: (Ord k, Monoid n, HasExp s1 (f k n), HasExp s2 (f k n)) => s1 -> s2 -> Exp (f k n)
- singleton :: Ord k => k -> v -> Exp (Single k v)
- setSingleton :: Ord k => k -> Exp (Single k ())
- intersect :: (Ord k, Iter f, Iter g, HasExp s1 (f k v), HasExp s2 (g k u)) => s1 -> s2 -> Exp (Sett k ())
- subset :: (Ord k, Iter f, Iter g, HasExp s1 (f k v), HasExp s2 (g k u)) => s1 -> s2 -> Exp Bool
- keyeq :: (Ord k, Iter f, Iter g, HasExp s1 (f k v), HasExp s2 (g k u)) => s1 -> s2 -> Exp Bool
- (◁) :: (Ord k, HasExp s1 (Sett k ()), HasExp s2 (f k v)) => s1 -> s2 -> Exp (f k v)
- (⋪) :: (Ord k, Iter g, HasExp s1 (g k ()), HasExp s2 (f k v)) => s1 -> s2 -> Exp (f k v)
- (▷) :: (Ord k, Iter g, Ord v, HasExp s1 (f k v), HasExp s2 (g v ())) => s1 -> s2 -> Exp (f k v)
- (⋫) :: (Ord k, Iter g, Ord v, HasExp s1 (f k v), HasExp s2 (g v ())) => s1 -> s2 -> Exp (f k v)
- (∈) :: (Show k, Ord k, Iter g, HasExp s (g k ())) => k -> s -> Exp Bool
- (∉) :: (Show k, Ord k, Iter g, HasExp s (g k ())) => k -> s -> Exp Bool
- (∪) :: (Show k, Show v, Ord k, HasExp s1 (f k v), HasExp s2 (g k v)) => s1 -> s2 -> Exp (f k v)
- (⨃) :: (Ord k, HasExp s1 (f k v), HasExp s2 (g k v)) => s1 -> s2 -> Exp (f k v)
- (∪+) :: (Ord k, Monoid n, HasExp s1 (f k n), HasExp s2 (f k n)) => s1 -> s2 -> Exp (f k n)
- (∩) :: (Ord k, Iter f, Iter g, HasExp s1 (f k v), HasExp s2 (g k u)) => s1 -> s2 -> Exp (Sett k ())
- (⊆) :: (Ord k, Iter f, Iter g, HasExp s1 (f k v), HasExp s2 (g k u)) => s1 -> s2 -> Exp Bool
- (≍) :: (Ord k, Iter f, Iter g, HasExp s1 (f k v), HasExp s2 (g k u)) => s1 -> s2 -> Exp Bool
- (<|) :: (Ord k, HasExp s1 (Sett k ()), HasExp s2 (f k v)) => s1 -> s2 -> Exp (f k v)
- (|>) :: (Ord k, Iter g, Ord v, HasExp s1 (f k v), HasExp s2 (g v ())) => s1 -> s2 -> Exp (f k v)
- (➖) :: (Ord k, Iter f, Iter g, HasExp s1 (f k v), HasExp s2 (g k u)) => s1 -> s2 -> Exp (f k v)
- data Exp t where
- eval :: Embed s t => Exp t -> s
- materialize :: Ord k => BaseRep f k v -> Collect (k, v) -> f k v
- biMapFromList :: (Ord k, Ord v) => (v -> v -> v) -> [(k, v)] -> BiMap v k v
- biMapEmpty :: BiMap v k v
- fromList :: Ord k => BaseRep f k v -> (v -> v -> v) -> [(k, v)] -> f k v
- keysEqual :: Ord k => Map k v1 -> Map k v2 -> Bool
- forwards :: BiMap v k v -> Map k v
- backwards :: BiMap v k v -> Map v (Set k)
Documentation
Instances
Iter List Source # | |
Defined in Control.Iterate.SetAlgebra Methods nxt :: List a b -> Collect (a, b, List a b) Source # lub :: Ord k => k -> List k b -> Collect (k, b, List k b) Source # hasNxt :: List a b -> Maybe (a, b, List a b) Source # hasLub :: Ord k => k -> List k b -> Maybe (k, b, List k b) Source # haskey :: Ord key => key -> List key b -> Bool Source # isnull :: List k v -> Bool Source # lookup :: Ord key => key -> List key rng -> Maybe rng Source # | |
Basic List Source # | The constructor for List is hidden, since it requires some invariants. Use fromPairs to build an initial List. |
Defined in Control.Iterate.SetAlgebra | |
Ord k => HasExp [(k, v)] (List k v) Source # | |
Ord k => Embed [(k, v)] (List k v) Source # | |
(Eq k, Eq v) => Eq (List k v) Source # | |
(Show k, Show v) => Show (List k v) Source # | |
Instances
Ord v => Iter (BiMap v) Source # | |
Defined in Control.Iterate.SetAlgebra Methods nxt :: BiMap v a b -> Collect (a, b, BiMap v a b) Source # lub :: Ord k => k -> BiMap v k b -> Collect (k, b, BiMap v k b) Source # hasNxt :: BiMap v a b -> Maybe (a, b, BiMap v a b) Source # hasLub :: Ord k => k -> BiMap v k b -> Maybe (k, b, BiMap v k b) Source # haskey :: Ord key => key -> BiMap v key b -> Bool Source # isnull :: BiMap v k v0 -> Bool Source # lookup :: Ord key => key -> BiMap v key rng -> Maybe rng Source # element :: Ord k => k -> BiMap v k v0 -> Collect () Source # | |
Ord v => Basic (BiMap v) Source # | |
Defined in Control.Iterate.SetAlgebra Methods addpair :: Ord k => k -> v0 -> BiMap v k v0 -> BiMap v k v0 Source # addkv :: Ord k => (k, v0) -> BiMap v k v0 -> (v0 -> v0 -> v0) -> BiMap v k v0 Source # removekey :: Ord k => k -> BiMap v k v0 -> BiMap v k v0 Source # domain :: Ord k => BiMap v k v0 -> Set k Source # | |
(Ord k, Ord v) => HasExp (Bimap k v) (Bimap k v) Source # | |
(Eq k, Eq v) => Eq (BiMap u k v) Source # | |
(Show k, Show v) => Show (BiMap u k v) Source # | |
(Ord a, Ord b, ToCBOR a, ToCBOR b) => ToCBOR (BiMap b a b) Source # | |
(Ord a, Ord b, FromCBOR a, FromCBOR b) => FromCBOR (BiMap b a b) Source # | |
NFData (BiMap v a b) Source # | |
Defined in Control.Iterate.SetAlgebra | |
(NoThunks a, NoThunks b) => NoThunks (BiMap v a b) Source # | |
(Ord v, Ord k) => HasQuery (BiMap v k v) k v Source # | |
Embed (BiMap v k v) (BiMap v k v) Source # | |
data Single k v where Source #
Instances
class Iter f => Basic f where Source #
In order to build typed Exp (which are a typed deep embedding) of Set operations, we need to know what kind of basic types of Maps and Sets can be embedded. Every Basic type has a few operations for creating one from a list, for adding and removing key-value pairs, looking up a value given a key. Instances of this algebra are functional in that every key has exactly one value associated with it. ===================================================================================================
Methods
addpair :: Ord k => k -> v -> f k v -> f k v Source #
in addpair the new value always prevails, to make a choice use addkv
which has a combining function that allows choice.
addkv :: Ord k => (k, v) -> f k v -> (v -> v -> v) -> f k v Source #
use ( old new -> old) if you want the v in (f k v) to prevail, and use ( old new -> new) if you want the v in (k,v) to prevail
removekey :: Ord k => k -> f k v -> f k v Source #
domain :: Ord k => f k v -> Set k Source #
Instances
Basic Map Source # | |
Defined in Control.Iterate.SetAlgebra | |
Basic List Source # | The constructor for List is hidden, since it requires some invariants. Use fromPairs to build an initial List. |
Defined in Control.Iterate.SetAlgebra | |
Basic Sett Source # | |
Defined in Control.Iterate.SetAlgebra | |
Basic Single Source # | |
Defined in Control.Iterate.SetAlgebra Methods addpair :: Ord k => k -> v -> Single k v -> Single k v Source # addkv :: Ord k => (k, v) -> Single k v -> (v -> v -> v) -> Single k v Source # removekey :: Ord k => k -> Single k v -> Single k v Source # domain :: Ord k => Single k v -> Set k Source # | |
Ord v => Basic (BiMap v) Source # | |
Defined in Control.Iterate.SetAlgebra Methods addpair :: Ord k => k -> v0 -> BiMap v k v0 -> BiMap v k v0 Source # addkv :: Ord k => (k, v0) -> BiMap v k v0 -> (v0 -> v0 -> v0) -> BiMap v k v0 Source # removekey :: Ord k => k -> BiMap v k v0 -> BiMap v k v0 Source # domain :: Ord k => BiMap v k v0 -> Set k Source # |
Methods
nxt :: f a b -> Collect (a, b, f a b) Source #
lub :: Ord k => k -> f k b -> Collect (k, b, f k b) Source #
hasNxt :: f a b -> Maybe (a, b, f a b) Source #
hasLub :: Ord k => k -> f k b -> Maybe (k, b, f k b) Source #
haskey :: Ord key => key -> f key b -> Bool Source #
isnull :: f k v -> Bool Source #
Instances
Iter Map Source # | |
Defined in Control.Iterate.SetAlgebra Methods nxt :: Map a b -> Collect (a, b, Map a b) Source # lub :: Ord k => k -> Map k b -> Collect (k, b, Map k b) Source # hasNxt :: Map a b -> Maybe (a, b, Map a b) Source # hasLub :: Ord k => k -> Map k b -> Maybe (k, b, Map k b) Source # haskey :: Ord key => key -> Map key b -> Bool Source # isnull :: Map k v -> Bool Source # lookup :: Ord key => key -> Map key rng -> Maybe rng Source # | |
Iter Query Source # | |
Defined in Control.Iterate.SetAlgebra Methods nxt :: Query a b -> Collect (a, b, Query a b) Source # lub :: Ord k => k -> Query k b -> Collect (k, b, Query k b) Source # hasNxt :: Query a b -> Maybe (a, b, Query a b) Source # hasLub :: Ord k => k -> Query k b -> Maybe (k, b, Query k b) Source # haskey :: Ord key => key -> Query key b -> Bool Source # isnull :: Query k v -> Bool Source # lookup :: Ord key => key -> Query key rng -> Maybe rng Source # | |
Iter List Source # | |
Defined in Control.Iterate.SetAlgebra Methods nxt :: List a b -> Collect (a, b, List a b) Source # lub :: Ord k => k -> List k b -> Collect (k, b, List k b) Source # hasNxt :: List a b -> Maybe (a, b, List a b) Source # hasLub :: Ord k => k -> List k b -> Maybe (k, b, List k b) Source # haskey :: Ord key => key -> List key b -> Bool Source # isnull :: List k v -> Bool Source # lookup :: Ord key => key -> List key rng -> Maybe rng Source # | |
Iter Sett Source # | |
Defined in Control.Iterate.SetAlgebra Methods nxt :: Sett a b -> Collect (a, b, Sett a b) Source # lub :: Ord k => k -> Sett k b -> Collect (k, b, Sett k b) Source # hasNxt :: Sett a b -> Maybe (a, b, Sett a b) Source # hasLub :: Ord k => k -> Sett k b -> Maybe (k, b, Sett k b) Source # haskey :: Ord key => key -> Sett key b -> Bool Source # isnull :: Sett k v -> Bool Source # lookup :: Ord key => key -> Sett key rng -> Maybe rng Source # | |
Iter Single Source # | |
Defined in Control.Iterate.SetAlgebra Methods nxt :: Single a b -> Collect (a, b, Single a b) Source # lub :: Ord k => k -> Single k b -> Collect (k, b, Single k b) Source # hasNxt :: Single a b -> Maybe (a, b, Single a b) Source # hasLub :: Ord k => k -> Single k b -> Maybe (k, b, Single k b) Source # haskey :: Ord key => key -> Single key b -> Bool Source # isnull :: Single k v -> Bool Source # lookup :: Ord key => key -> Single key rng -> Maybe rng Source # | |
Ord v => Iter (BiMap v) Source # | |
Defined in Control.Iterate.SetAlgebra Methods nxt :: BiMap v a b -> Collect (a, b, BiMap v a b) Source # lub :: Ord k => k -> BiMap v k b -> Collect (k, b, BiMap v k b) Source # hasNxt :: BiMap v a b -> Maybe (a, b, BiMap v a b) Source # hasLub :: Ord k => k -> BiMap v k b -> Maybe (k, b, BiMap v k b) Source # haskey :: Ord key => key -> BiMap v key b -> Bool Source # isnull :: BiMap v k v0 -> Bool Source # lookup :: Ord key => key -> BiMap v key rng -> Maybe rng Source # element :: Ord k => k -> BiMap v k v0 -> Collect () Source # |
class HasExp s t | s -> t where Source #
Basic types are those that can be embedded into Exp.
The HasExp class, encodes how to lift a Basic type into an Exp.
The function toExp
will build a typed Exp for that Basic type.
This will be really usefull in the smart constructors.
==================================================================
Instances
HasExp (Exp t) t Source # | The simplest Base type is one that is already an Exp |
Ord k => HasExp [(k, v)] (List k v) Source # | |
Ord k => HasExp (Set k) (Sett k ()) Source # | |
Ord k => HasExp (Map k v) (Map k v) Source # | |
(Ord k, Ord v) => HasExp (Bimap k v) (Bimap k v) Source # | |
Ord k => HasExp (Single k v) (Single k v) Source # | |
dexclude :: (Ord k, Iter g, HasExp s1 (g k ()), HasExp s2 (f k v)) => s1 -> s2 -> Exp (f k v) Source #
rexclude :: (Ord k, Iter g, Ord v, HasExp s1 (f k v), HasExp s2 (g v ())) => s1 -> s2 -> Exp (f k v) Source #
rrestrict :: (Ord k, Iter g, Ord v, HasExp s1 (f k v), HasExp s2 (g v ())) => s1 -> s2 -> Exp (f k v) Source #
unionleft :: (Show k, Show v, Ord k, HasExp s1 (f k v), HasExp s2 (g k v)) => s1 -> s2 -> Exp (f k v) Source #
unionplus :: (Ord k, Monoid n, HasExp s1 (f k n), HasExp s2 (f k n)) => s1 -> s2 -> Exp (f k n) Source #
intersect :: (Ord k, Iter f, Iter g, HasExp s1 (f k v), HasExp s2 (g k u)) => s1 -> s2 -> Exp (Sett k ()) Source #
subset :: (Ord k, Iter f, Iter g, HasExp s1 (f k v), HasExp s2 (g k u)) => s1 -> s2 -> Exp Bool Source #
keyeq :: (Ord k, Iter f, Iter g, HasExp s1 (f k v), HasExp s2 (g k u)) => s1 -> s2 -> Exp Bool Source #
(▷) :: (Ord k, Iter g, Ord v, HasExp s1 (f k v), HasExp s2 (g v ())) => s1 -> s2 -> Exp (f k v) Source #
(⋫) :: (Ord k, Iter g, Ord v, HasExp s1 (f k v), HasExp s2 (g v ())) => s1 -> s2 -> Exp (f k v) Source #
(∪) :: (Show k, Show v, Ord k, HasExp s1 (f k v), HasExp s2 (g k v)) => s1 -> s2 -> Exp (f k v) Source #
(∩) :: (Ord k, Iter f, Iter g, HasExp s1 (f k v), HasExp s2 (g k u)) => s1 -> s2 -> Exp (Sett k ()) Source #
(⊆) :: (Ord k, Iter f, Iter g, HasExp s1 (f k v), HasExp s2 (g k u)) => s1 -> s2 -> Exp Bool Source #
(≍) :: (Ord k, Iter f, Iter g, HasExp s1 (f k v), HasExp s2 (g k u)) => s1 -> s2 -> Exp Bool Source #
(|>) :: (Ord k, Iter g, Ord v, HasExp s1 (f k v), HasExp s2 (g v ())) => s1 -> s2 -> Exp (f k v) Source #
(➖) :: (Ord k, Iter f, Iter g, HasExp s1 (f k v), HasExp s2 (g k u)) => s1 -> s2 -> Exp (f k v) Source #
The self typed GADT: Exp, that encodes the shape of Set expressions. A deep embedding. Exp is a typed Symbolic representation of queries we may ask. It allows us to introspect a query The strategy is to 1) Define Exp so all queries can be represented. 2) Define smart constructors that "parse" the surface syntax, and build a typed Exp 3) Write an evaluate function: eval:: Exp t -> t 4) "eval" can introspect the code and apply efficient domain and type specific translations 5) Use the (Iter f) class to evaluate some Exp that can benefit from its efficient nature. ===============================================================================================
materialize :: Ord k => BaseRep f k v -> Collect (k, v) -> f k v Source #
Given a BaseRep we can materialize a (Collect k v) into the type witnessed by the BaseRep. Recall a (Collect k v) has no intrinsic type (it is just an ABSTRACT sequence of tuples), so the witness describes how to turn them into the chosen datatype. Note that materialize is meant to be applied to a collection built by iterating over a Query. This produces the keys in ascending order, with no duplicate keys. So we do not need to specify how to merge values. =============================================================================================
biMapEmpty :: BiMap v k v Source #