set-algebra-1.1.0.3: Set Algebra
Safe HaskellSafe-Inferred
LanguageHaskell2010

Control.Iterate.Exp

Description

This module provides deep embeddings of three things 1) Exp is a deep embedding of expressions over Sets and Maps as a typed data structure. 2) Fun is a deep embedding of symbolic functions 3) Query is a deep embedding of queries over Sets and Maps. It can be thought of as a low-level compiled form of Exp

Synopsis

Documentation

embedding

data Exp t where 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.

Constructors

Base ∷ (Ord k, Basic f, Iter f) ⇒ BaseRep f k v → f k v → Exp (f k v) 
DomOrd k ⇒ Exp (f k v) → Exp (Sett k ()) 
Rng ∷ (Ord k, Ord v) ⇒ Exp (f k v) → Exp (Sett v ()) 
DRestrict ∷ (Ord k, Iter g) ⇒ Exp (g k ()) → Exp (f k v) → Exp (f k v) 
DExclude ∷ (Ord k, Iter g) ⇒ Exp (g k ()) → Exp (f k v) → Exp (f k v) 
RRestrict ∷ (Ord k, Iter g, Ord v) ⇒ Exp (f k v) → Exp (g v ()) → Exp (f k v) 
RExclude ∷ (Ord k, Iter g, Ord v) ⇒ Exp (f k v) → Exp (g v ()) → Exp (f k v) 
Elem ∷ (Ord k, Iter g, Show k) ⇒ k → Exp (g k ()) → Exp Bool 
NotElem ∷ (Ord k, Iter g, Show k) ⇒ k → Exp (g k ()) → Exp Bool 
Intersect ∷ (Ord k, Iter f, Iter g) ⇒ Exp (f k v) → Exp (g k u) → Exp (Sett k ()) 
Subset ∷ (Ord k, Iter f, Iter g) ⇒ Exp (f k v) → Exp (g k u) → Exp Bool 
SetDiff ∷ (Ord k, Iter f, Iter g) ⇒ Exp (f k v) → Exp (g k u) → Exp (f k v) 
UnionOverrideLeft ∷ (Show k, Show v, Ord k) ⇒ Exp (f k v) → Exp (g k v) → Exp (f k v) 
UnionPlus ∷ (Ord k, Monoid n) ⇒ Exp (f k n) → Exp (g k n) → Exp (f k n) 
UnionOverrideRightOrd k ⇒ Exp (f k v) → Exp (g k v) → Exp (f k v) 
SingletonOrd k ⇒ k → v → Exp (Single k v) 
SetSingletonOrd k ⇒ k → Exp (Single k ()) 
KeyEqual ∷ (Ord k, Iter f, Iter g) ⇒ Exp (f k v) → Exp (g k u) → Exp Bool 

Instances

Instances details
Show (Exp t) Source # 
Instance details

Defined in Control.Iterate.Exp

Methods

showsPrecIntExp t → ShowS Source #

showExp t → String Source #

showList ∷ [Exp t] → ShowS Source #

HasExp (Exp t) t Source #

The simplest Base type is one that is already an Exp

Instance details

Defined in Control.Iterate.Exp

Methods

toExpExp t → Exp t Source #

class HasExp s t | s → t where Source #

Basic types are those that can be tranformed 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.

Methods

toExp ∷ s → Exp t Source #

Instances

Instances details
HasExp (Exp t) t Source #

The simplest Base type is one that is already an Exp

Instance details

Defined in Control.Iterate.Exp

Methods

toExpExp t → Exp t Source #

Ord k ⇒ HasExp (Set k) (Sett k ()) Source # 
Instance details

Defined in Control.Iterate.Exp

Methods

toExpSet k → Exp (Sett k ()) Source #

Ord k ⇒ HasExp [(k, v)] (List k v) Source # 
Instance details

Defined in Control.Iterate.Exp

Methods

toExp ∷ [(k, v)] → Exp (List k v) Source #

Ord k ⇒ HasExp (Map k v) (Map k v) Source # 
Instance details

Defined in Control.Iterate.Exp

Methods

toExpMap k v → Exp (Map k v) Source #

Ord k ⇒ HasExp (Single k v) (Single k v) Source # 
Instance details

Defined in Control.Iterate.Exp

Methods

toExpSingle k v → Exp (Single k v) Source #

type OrdAll coin cred pool ptr k = (Ord k, Ord coin, Ord cred, Ord ptr, Ord pool) Source #

dRestrict ∷ (Ord k, Iter g) ⇒ Exp (g k ()) → Exp (f k v) → Exp (f k v) Source #

rRestrict ∷ (Ord k, Iter g, Ord v) ⇒ Exp (f k v) → Exp (g v ()) → Exp (f k v) Source #

dExclude ∷ (Ord k, Iter g) ⇒ Exp (g k ()) → Exp (f k v) → Exp (f k v) Source #

rExclude ∷ (Ord k, Iter g, Ord v) ⇒ Exp (f k v) → Exp (g v ()) → Exp (f k v) Source #

dom ∷ (Ord k, HasExp s (f k v)) ⇒ s → Exp (Sett k ()) Source #

domain of a map or element type of a set.

rng ∷ (Ord k, Ord v) ⇒ HasExp s (f k v) ⇒ s → Exp (Sett v ()) Source #

range of a map or () for a set.

(◁) ∷ (Ord k, HasExp s1 (Sett k ()), HasExp s2 (f k v)) ⇒ s1 → s2 → Exp (f k v) Source #

domain restrict.

(<|) ∷ (Ord k, HasExp s1 (Sett k ()), HasExp s2 (f k v)) ⇒ s1 → s2 → Exp (f k v) Source #

domain restrict.

drestrict ∷ (Ord k, HasExp s1 (Sett k ()), HasExp s2 (f k v)) ⇒ s1 → s2 → Exp (f k v) Source #

domain restrict.

(⋪) ∷ (Ord k, Iter g, HasExp s1 (g k ()), HasExp s2 (f k v)) ⇒ s1 → s2 → Exp (f k v) Source #

domain exclude

dexclude ∷ (Ord k, Iter g, HasExp s1 (g k ()), HasExp s2 (f k v)) ⇒ s1 → s2 → Exp (f k v) Source #

domain exclude

(▷) ∷ (Ord k, Iter g, Ord v, HasExp s1 (f k v), HasExp s2 (g v ())) ⇒ s1 → s2 → Exp (f k v) Source #

range restrict

(|>) ∷ (Ord k, Iter g, Ord v, HasExp s1 (f k v), HasExp s2 (g v ())) ⇒ s1 → s2 → Exp (f k v) Source #

range restrict

rrestrict ∷ (Ord k, Iter g, Ord v, HasExp s1 (f k v), HasExp s2 (g v ())) ⇒ s1 → s2 → Exp (f k v) Source #

range restrict

(⋫) ∷ (Ord k, Iter g, Ord v, HasExp s1 (f k v), HasExp s2 (g v ())) ⇒ s1 → s2 → Exp (f k v) Source #

range exclude

rexclude ∷ (Ord k, Iter g, Ord v, HasExp s1 (f k v), HasExp s2 (g v ())) ⇒ s1 → s2 → Exp (f k v) Source #

range exclude

(∈) ∷ (Show k, Ord k, Iter g, HasExp s (g k ())) ⇒ k → s → Exp Bool Source #

element of the domain

(∉) ∷ (Show k, Ord k, Iter g, HasExp s (g k ())) ⇒ k → s → Exp Bool Source #

not an element of the domain

notelem ∷ (Show k, Ord k, Iter g, HasExp s (g k ())) ⇒ k → s → Exp Bool Source #

not an element of the domain

(∪) ∷ (Show k, Show v, Ord k, HasExp s1 (f k v), HasExp s2 (g k v)) ⇒ s1 → s2 → Exp (f k v) Source #

union two maps or sets. In the case of a map, keep the pair from the left, if the two have common keys.

unionleft ∷ (Show k, Show v, Ord k, HasExp s1 (f k v), HasExp s2 (g k v)) ⇒ s1 → s2 → Exp (f k v) Source #

union two maps or sets. In the case of a map, keep the pair from the left, if the two have common keys.

(⨃) ∷ (Ord k, HasExp s1 (f k v), HasExp s2 (g k v)) ⇒ s1 → s2 → Exp (f k v) Source #

union two maps or sets. In the case of a map, keep the pair from the right, if the two have common keys.

unionright ∷ (Ord k, HasExp s1 (f k v), HasExp s2 (g k v)) ⇒ s1 → s2 → Exp (f k v) Source #

union two maps or sets. In the case of a map, keep the pair from the right, if the two have common keys.

(∪+) ∷ (Ord k, Monoid n, HasExp s1 (f k n), HasExp s2 (g k n)) ⇒ s1 → s2 → Exp (f k n) Source #

union two maps or sets. In the case of a map, combine values with monoid (<>), if the two have common keys.

unionplus ∷ (Ord k, Monoid n, HasExp s1 (f k n), HasExp s2 (g k n)) ⇒ s1 → s2 → Exp (f k n) Source #

union two maps or sets. In the case of a map, combine values with monoid (<>), if the two have common keys.

singletonOrd k ⇒ k → v → Exp (Single k v) Source #

create a singleton map.

setSingletonOrd k ⇒ k → Exp (Single k ()) Source #

create a singleton set.

(∩) ∷ (Ord k, Iter f, Iter g, HasExp s1 (f k v), HasExp s2 (g k u)) ⇒ s1 → s2 → Exp (Sett k ()) Source #

intersect two sets, or the intersection of the domain of two maps.

intersect ∷ (Ord k, Iter f, Iter g, HasExp s1 (f k v), HasExp s2 (g k u)) ⇒ s1 → s2 → Exp (Sett k ()) Source #

intersect two sets, or the intersection of the domain of two maps.

(⊆) ∷ (Ord k, Iter f, Iter g, HasExp s1 (f k v), HasExp s2 (g k u)) ⇒ s1 → s2 → Exp Bool Source #

(subset x y). is the domain of x a subset of the domain of y.

subset ∷ (Ord k, Iter f, Iter g, HasExp s1 (f k v), HasExp s2 (g k u)) ⇒ s1 → s2 → Exp Bool Source #

(subset x y). is the domain of x a subset of the domain of y.

(➖) ∷ (Ord k, Iter f, Iter g, HasExp s1 (f k v), HasExp s2 (g k u)) ⇒ s1 → s2 → Exp (f k v) Source #

(x ➖ y) Everything in x except for those pairs in x where the domain of x is an element of the domain of y.

setdiff ∷ (Ord k, Iter f, Iter g, HasExp s1 (f k v), HasExp s2 (g k u)) ⇒ s1 → s2 → Exp (f k v) Source #

(x ➖ y) Everything in x except for those pairs in x where the domain of x is an element of the domain of y.

(≍) ∷ (Ord k, Iter f, Iter g, HasExp s1 (f k v), HasExp s2 (g k u)) ⇒ s1 → s2 → Exp Bool Source #

Do two maps (or sets) have exactly the same domain.

keyeq ∷ (Ord k, Iter f, Iter g, HasExp s1 (f k v), HasExp s2 (g k u)) ⇒ s1 → s2 → Exp Bool Source #

Do two maps (or sets) have exactly the same domain.

data Fun t Source #

An symbolic function Fun has two parts, a Lam that can be analyzed, and real function that can be applied

Constructors

Fun (Lam t) t 

Instances

Instances details
Show (Fun t) Source #

We can observe a Fun by showing the Lam part.

Instance details

Defined in Control.Iterate.Exp

Methods

showsPrecIntFun t → ShowS Source #

showFun t → String Source #

showList ∷ [Fun t] → ShowS Source #

data Pat env t where Source #

Symbolc functions (Fun) are data, that can be pattern matched over. They 1) Represent a wide class of binary functions that are used in translating the SetAlgebra 2) Turned into a String so they can be printed 3) Turned into the function they represent. 4) Composed into bigger functions 5) Symbolically symplified Here we implement Symbolic Binary functions with upto 4 variables, which is enough for this use =================================================================================================

Constructors

P1Pat (d, c, b, a) d 
P2Pat (d, c, b, a) c 
P3Pat (d, c, b, a) b 
P4Pat (d, c, b, a) a 
PPairPat (d, c, b, a) a → Pat (d, c, b, a) b → Pat (d, c, b, a) (a, b) 

data Expr env t where Source #

Constructors

X1Expr (d, c, b, a) d 
X2Expr (d, c, b, a) c 
X3Expr (d, c, b, a) b 
X4Expr (d, c, b, a) a 
HasKey ∷ (Iter f, Ord k) ⇒ Expr e k → f k v → Expr e Bool 
NegExpr e BoolExpr e Bool 
ApLam (a → b → c) → Expr e a → Expr e b → Expr e c 
EPairExpr e a → Expr e b → Expr e (a, b) 
FSTExpr e (a, b) → Expr e a 
SNDExpr e (a, b) → Expr e b 
LitShow t ⇒ t → Expr env t 

Instances

Instances details
Show (Expr (a, b, c, d) t) Source # 
Instance details

Defined in Control.Iterate.Exp

Methods

showsPrecIntExpr (a, b, c, d) t → ShowS Source #

showExpr (a, b, c, d) t → String Source #

showList ∷ [Expr (a, b, c, d) t] → ShowS Source #

data Lam t where Source #

A typed deep embedding of Haskell functions with type t. Be carefull, no pattern P1, P2, P3, P4 should appear MORE THAN ONCE in a Lam.

Constructors

LamPat (d, c, b, a) t → Pat (d, c, b, a) s → Expr (d, c, b, a) v → Lam (t → s → v) 
AddNum n ⇒ Lam (n → n → n) 
CatMonoid m ⇒ Lam (m → m → m) 
EqlEq t ⇒ Lam (t → t → Bool) 
BothLam (BoolBoolBool) 
Lift ∷ (a → b → c) → Lam (a → b → c) 

Instances

Instances details
Show (Lam t) Source # 
Instance details

Defined in Control.Iterate.Exp

Methods

showsPrecIntLam t → ShowS Source #

showLam t → String Source #

showList ∷ [Lam t] → ShowS Source #

bindEPat (a, b, c, d) t → Expr (w, x, y, z) t → StringEnvStringEnv Source #

showEStringEnvExpr (a, b, c, d) t → String Source #

showPStringEnvPat any t → String Source #

applyFun t → t Source #

firstFun (v → s → v) Source #

secondFun (v → s → s) Source #

plusMonoid t ⇒ Fun (t → t → t) Source #

eqlEq t ⇒ Fun (t → t → Bool) Source #

constantShow c ⇒ c → Fun (a → b → c) Source #

rngElem ∷ (Ord rng, Iter f) ⇒ f rng v → Fun (dom → rng → Bool) Source #

domElem ∷ (Ord dom, Iter f) ⇒ f dom v → Fun (dom → rng → Bool) Source #

rngFstFun (x → (a, b) → a) Source #

rngSndFun (x → (a, b) → b) Source #

compose1Fun (t1 → t2 → t3) → Fun (t1 → t4 → t2) → Fun (t1 → t4 → t3) Source #

compSndLFun (k → (a, b) → c) → Fun (k → d → a) → Fun (k → (d, b) → c) Source #

compSndRFun (k → (a, b) → c) → Fun (k → d → b) → Fun (k → (a, d) → c) Source #

compCurryRFun (k → (a, b) → d) → Fun (a → c → b) → Fun (k → (a, c) → d) Source #

nEgateFun (k → v → Bool) → Fun (k → v → Bool) Source #

alwaysFun (a → b → Bool) Source #

bothFun (a → b → Bool) → Fun (a → b → Bool) → Fun (a → b → Bool) Source #

lift ∷ (a → b → c) → Fun (a → b → c) Source #

data Query k v where Source #

Query is a single datatype that describes a low-level language that can be used to build compound iterators, from other iterators.

Constructors

BaseD ∷ (Iter f, Ord k) ⇒ BaseRep f k v → f k v → Query k v 
ProjectDOrd k ⇒ Query k v → Fun (k → v → u) → Query k u 
AndDOrd k ⇒ Query k v → Query k w → Query k (v, w) 
ChainD ∷ (Ord k, Ord v) ⇒ Query k v → Query v w → Fun (k → (v, w) → u) → Query k u 
AndPDOrd k ⇒ Query k v → Query k u → Fun (k → (v, u) → w) → Query k w 
OrDOrd k ⇒ Query k v → Query k v → Fun (v → v → v) → Query k v 
GuardDOrd k ⇒ Query k v → Fun (k → v → Bool) → Query k v 
DiffDOrd k ⇒ Query k v → Query k u → Query k v 

Instances

Instances details
Iter Query Source # 
Instance details

Defined in Control.Iterate.Exp

Methods

nxtQuery a b → Collect (a, b, Query a b) Source #

lubOrd k ⇒ k → Query k b → Collect (k, b, Query k b) Source #

hasNxtQuery a b → Maybe (a, b, Query a b) Source #

hasLubOrd k ⇒ k → Query k b → Maybe (k, b, Query k b) Source #

haskeyOrd key ⇒ key → Query key b → Bool Source #

isnullQuery k v → Bool Source #

lookupOrd key ⇒ key → Query key rng → Maybe rng Source #

elementOrd k ⇒ k → Query k v → Collect () Source #

Show (Query k v) Source # 
Instance details

Defined in Control.Iterate.Exp

Methods

showsPrecIntQuery k v → ShowS Source #

showQuery k v → String Source #

showList ∷ [Query k v] → ShowS Source #

HasQuery (Query k v) k v Source # 
Instance details

Defined in Control.Iterate.Exp

Methods

queryQuery k v → Query k v Source #

projDOrd k ⇒ Query k v → Fun (k → v → u) → Query k u Source #

andDOrd k ⇒ Query k v1 → Query k v2 → Query k (v1, v2) Source #

andPDOrd k ⇒ Query k v1 → Query k u → Fun (k → (v1, u) → v) → Query k v Source #

chainD ∷ (Ord k, Ord v) ⇒ Query k v → Query v w → Fun (k → (v, w) → u) → Query k u Source #

guardDOrd k ⇒ Query k v → Fun (k → v → Bool) → Query k v Source #

projectQ ∷ (Ord k, HasQuery c k v) ⇒ c → Fun (k → v → u) → Query k u Source #

andQ ∷ (Ord k, HasQuery concrete1 k v, HasQuery concrete2 k w) ⇒ concrete1 → concrete2 → Query k (v, w) Source #

orQ ∷ (Ord k, HasQuery concrete1 k v, HasQuery concrete2 k v) ⇒ concrete1 → concrete2 → Fun (v → v → v) → Query k v Source #

chainQ ∷ (Ord k, Ord v, HasQuery concrete1 k v, HasQuery concrete2 v w) ⇒ concrete1 → concrete2 → Fun (k → (v, w) → u) → Query k u Source #

andPQ ∷ (Ord k, HasQuery concrete1 k v, HasQuery concrete2 k u) ⇒ concrete1 → concrete2 → Fun (k → (v, u) → w) → Query k w Source #

guardQ ∷ (Ord k, HasQuery concrete k v) ⇒ concrete → Fun (k → v → Bool) → Query k v Source #

diffQ ∷ ∀ k v u concrete1 concrete2. (Ord k, HasQuery (concrete1 k v) k v, HasQuery (concrete2 k u) k u) ⇒ concrete1 k v → concrete2 k u → Query k v Source #

class HasQuery concrete k v where Source #

Methods

query ∷ concrete → Query k v Source #

Instances

Instances details
Ord k ⇒ HasQuery (Set k) k () Source # 
Instance details

Defined in Control.Iterate.Exp

Methods

querySet k → Query k () Source #

Ord k ⇒ HasQuery [(k, v)] k v Source # 
Instance details

Defined in Control.Iterate.Exp

Methods

query ∷ [(k, v)] → Query k v Source #

Ord k ⇒ HasQuery (Map k v) k v Source # 
Instance details

Defined in Control.Iterate.Exp

Methods

queryMap k v → Query k v Source #

Ord k ⇒ HasQuery (Single k v) k v Source # 
Instance details

Defined in Control.Iterate.Exp

Methods

querySingle k v → Query k v Source #

HasQuery (Query k v) k v Source # 
Instance details

Defined in Control.Iterate.Exp

Methods

queryQuery k v → Query k v Source #

ppQueryQuery k v → Doc a Source #

nxtQueryQuery a b → Collect (a, b, Query a b) Source #

lubQueryOrd a ⇒ a → Query a b → Collect (a, b, Query a b) Source #

projStepOrd k ⇒ (t → Collect (k, v, Query k v)) → Fun (k → v → u) → t → Collect (k, u, Query k u) Source #

andStepOrd a ⇒ (a, b1, Query a b1) → (a, b2, Query a b2) → Collect (a, (b1, b2), Query a (b1, b2)) Source #

chainStep ∷ (Ord b, Ord a) ⇒ (a, b, Query a b) → Query b w → Fun (a → (b, w) → u) → Collect (a, u, Query a u) Source #

andPstepOrd a ⇒ (a, b1, Query a b1) → (a, b2, Query a b2) → Fun (a → (b1, b2) → w) → Collect (a, w, Query a w) Source #

orStep ∷ (Ord k, Ord a) ⇒ (Query k v → Collect (a, v, Query k v)) → Query k v → Query k v → Fun (v → v → v) → Collect (a, v, Query k v) Source #

guardStepOrd a ⇒ (Query a b → Collect (a, b, Query a b)) → Fun (a → b → Bool) → Query a b → Collect (a, b, Query a b) Source #

diffStepOrd k ⇒ (k, v, Query k v) → Query k u → Collect (k, v, Query k v) Source #