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

Control.SetAlgebra

Description

Operations for manipulating sets and maps using mathematicial operators. Concrete types that can be interpreted as sets and maps are made instances of the Basic class. In order to make sets and maps behave uniformly, an instance (Basic f) implies f is a binary type constructor. For types interpreted as maps, the type (f k v) means that k is the type of the map's key, and v is the type of map's value. For types interpreted as sets, the value is always the unit type: (). The binary GADT Sett links to the usual Set type. Its constructor has the following type Sett :: Set k -> Sett k (), programmers can use similar strategies to interpret other types as sets. Predefined instances of Basic include Map, Set, List, and Single. Programmers can add Basic instances for their own types as well.

A typical set algebra expression (involving range restriction, (), here) looks like (eval (x ▷ y)). Where x and y are program variables or expressions, the operator () builds an Exp tree, and eval simplifys the tree, and then evaluates the simplfied tree to get the result. Here is the actual type of the range restrict operator.

(▷) :: (Ord k, Iter g, Ord v, HasExp s1 (f k v), HasExp s2 (g v ())) => s1 -> s2 -> Exp (f k v)

As the type indicates, in order to support simplifcation and evaluation the types of the operands to () must be instances of several classes. Possible classes include Basic, HasExp, Iter, and Embed.

  1. (Basic f) meaning (f k v) must be interpreted as a map or set, with two type parameters k and v.
  2. (HasExp t (f k v)) meaning a value of type t can be lifted to an expression of type (Exp (f k v)), where (Basic f).
  3. (Iter f) meaning the Basic type constructor f supports certain (usually fast) operations, that can be combined.
  4. (Embed concrete f) meaning the types concrete and (f k v) form an isomorphism.

Available operands to create set algebra expressions are dom, rng, dexclude, (⋪), drestrict, (◁), rexclude, (⋫), rrestrict, (▷), unionright, (⨃), unionleft,(∪), unionplus, (∪+),singleton, setSingleton, intersect, (∩), subset, (⊆), keyeq, (≍), (∈), (∉), setdiff, (➖) .

The key abstraction that makes set algebra work is the self typed GADT: (Exp t), that defines a tree that represents a deep embedding of all set algebra expressions representing maps or sets of type t. 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.

Basically, if the compiler can infer concrete type for the operands of operators then all the class instances are automatically solved. If you get an error involving a class, then it is most probably the case that the type of the operands cannot be properly inferred.

Synopsis

In addition to Map and Set, types interpretable as maps and sets.

data List k v Source #

Maps stored as lists. Sorted [(key,value)] pairs, with no duplicate keys. The constructor for List is hidden, since it requires some invariants. Use fromPairs to build an initial List.

Instances

Instances details
Basic List Source # 
Instance details

Defined in Control.Iterate.BaseTypes

Methods

addpairOrd k ⇒ k → v → List k v → List k v Source #

addkvOrd k ⇒ (k, v) → List k v → (v → v → v) → List k v Source #

removekeyOrd k ⇒ k → List k v → List k v Source #

domainOrd k ⇒ List k v → Set k Source #

rangeOrd v ⇒ List k v → Set v Source #

Iter List Source # 
Instance details

Defined in Control.Iterate.BaseTypes

Methods

nxtList a b → Collect (a, b, List a b) Source #

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

hasNxtList a b → Maybe (a, b, List a b) Source #

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

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

isnullList k v → Bool Source #

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

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

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

Defined in Control.Iterate.BaseTypes

Methods

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

fromBaseList k v → [(k, v)] 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 #

(Show k, Show v) ⇒ Show (List k v) Source # 
Instance details

Defined in Control.Iterate.BaseTypes

Methods

showsPrecIntList k v → ShowS Source #

showList k v → String Source #

showList ∷ [List k v] → ShowS Source #

(Eq k, Eq v) ⇒ Eq (List k v) Source # 
Instance details

Defined in Control.Iterate.BaseTypes

Methods

(==)List k v → List k v → Bool Source #

(/=)List k v → List k v → Bool Source #

data Single k v where Source #

Maps and sets with zero or a single pair. Iteration is trivial. Succeeds at most once.

Constructors

Single ∷ k → v → Single k v 
FailSingle k v 
SetSingle ∷ k → Single k () 

Instances

Instances details
Basic Single Source # 
Instance details

Defined in Control.Iterate.BaseTypes

Methods

addpairOrd k ⇒ k → v → Single k v → Single k v Source #

addkvOrd k ⇒ (k, v) → Single k v → (v → v → v) → Single k v Source #

removekeyOrd k ⇒ k → Single k v → Single k v Source #

domainOrd k ⇒ Single k v → Set k Source #

rangeOrd v ⇒ Single k v → Set v Source #

Iter Single Source # 
Instance details

Defined in Control.Iterate.BaseTypes

Methods

nxtSingle a b → Collect (a, b, Single a b) Source #

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

hasNxtSingle a b → Maybe (a, b, Single a b) Source #

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

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

isnullSingle k v → Bool Source #

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

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

(Show k, Show v) ⇒ Show (Single k v) Source # 
Instance details

Defined in Control.Iterate.BaseTypes

Methods

showsPrecIntSingle k v → ShowS Source #

showSingle k v → String Source #

showList ∷ [Single k v] → ShowS Source #

(Eq k, Eq v) ⇒ Eq (Single k v) Source # 
Instance details

Defined in Control.Iterate.BaseTypes

Methods

(==)Single k v → Single k v → Bool Source #

(/=)Single k v → Single k v → Bool 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 #

Embed (Single k v) (Single k v) Source # 
Instance details

Defined in Control.Iterate.BaseTypes

Methods

toBaseSingle k v → Single k v Source #

fromBaseSingle k v → Single 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 #

Classes supporting abstract constructors of Set Algebra Expressions. These show up in the types of overloaded functions.

class Basic f where Source #

In order to build typed Exp (which are a typed deep embedding) of map and set operations, we need to know what kind of basic types can be used this way. 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.

Minimal complete definition

addkv, removekey, domain, range

Methods

addpairOrd 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.

addkvOrd 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

removekeyOrd k ⇒ k → f k v → f k v Source #

remove the pair with key k, if it is there.

domainOrd k ⇒ f k v → Set k Source #

the set of keys

rangeOrd v ⇒ f k v → Set v Source #

the set of values.

Instances

Instances details
Basic Map Source # 
Instance details

Defined in Control.Iterate.BaseTypes

Methods

addpairOrd k ⇒ k → v → Map k v → Map k v Source #

addkvOrd k ⇒ (k, v) → Map k v → (v → v → v) → Map k v Source #

removekeyOrd k ⇒ k → Map k v → Map k v Source #

domainOrd k ⇒ Map k v → Set k Source #

rangeOrd v ⇒ Map k v → Set v Source #

Basic List Source # 
Instance details

Defined in Control.Iterate.BaseTypes

Methods

addpairOrd k ⇒ k → v → List k v → List k v Source #

addkvOrd k ⇒ (k, v) → List k v → (v → v → v) → List k v Source #

removekeyOrd k ⇒ k → List k v → List k v Source #

domainOrd k ⇒ List k v → Set k Source #

rangeOrd v ⇒ List k v → Set v Source #

Basic Sett Source # 
Instance details

Defined in Control.Iterate.BaseTypes

Methods

addpairOrd k ⇒ k → v → Sett k v → Sett k v Source #

addkvOrd k ⇒ (k, v) → Sett k v → (v → v → v) → Sett k v Source #

removekeyOrd k ⇒ k → Sett k v → Sett k v Source #

domainOrd k ⇒ Sett k v → Set k Source #

rangeOrd v ⇒ Sett k v → Set v Source #

Basic Single Source # 
Instance details

Defined in Control.Iterate.BaseTypes

Methods

addpairOrd k ⇒ k → v → Single k v → Single k v Source #

addkvOrd k ⇒ (k, v) → Single k v → (v → v → v) → Single k v Source #

removekeyOrd k ⇒ k → Single k v → Single k v Source #

domainOrd k ⇒ Single k v → Set k Source #

rangeOrd v ⇒ Single k v → Set v Source #

class Iter f where Source #

The Set algebra include types that encode finite sets and maps of some type. They have a finite domain, and for each domain element they pair a single range element (unit for sets). We are interested in those finite maps that can iterate their pairs in ascending domain order. The operations are: nxt and lub . lub can skip over many items in sub-linear time, it can make things really fast. Many finite maps can support a support lub operation in sub-linear time. Some examples: Balanced binary trees, Arrays (using binary search), Tries, etc. There are basic and compound Iter instances. Compound types include components with types that have Iter instances.

Minimal complete definition

nxt, lub

Methods

nxt ∷ f a b → Collect (a, b, f a b) Source #

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

hasNxt ∷ f a b → Maybe (a, b, f a b) Source #

The next few methods can all be defined via nxt and lub, but for base types there often exist much more efficent means, so the default definitions should be overwritten for such basic types. For compound types with Guards, these are often the only way to define them.

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

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

isnull ∷ f k v → Bool Source #

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

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

Instances

Instances details
Iter Map Source # 
Instance details

Defined in Control.Iterate.BaseTypes

Methods

nxtMap a b → Collect (a, b, Map a b) Source #

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

hasNxtMap a b → Maybe (a, b, Map a b) Source #

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

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

isnullMap k v → Bool Source #

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

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

Iter List Source # 
Instance details

Defined in Control.Iterate.BaseTypes

Methods

nxtList a b → Collect (a, b, List a b) Source #

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

hasNxtList a b → Maybe (a, b, List a b) Source #

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

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

isnullList k v → Bool Source #

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

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

Iter Sett Source # 
Instance details

Defined in Control.Iterate.BaseTypes

Methods

nxtSett a b → Collect (a, b, Sett a b) Source #

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

hasNxtSett a b → Maybe (a, b, Sett a b) Source #

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

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

isnullSett k v → Bool Source #

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

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

Iter Single Source # 
Instance details

Defined in Control.Iterate.BaseTypes

Methods

nxtSingle a b → Collect (a, b, Single a b) Source #

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

hasNxtSingle a b → Maybe (a, b, Single a b) Source #

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

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

isnullSingle k v → Bool Source #

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

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

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 #

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 #

class Embed concrete base | concrete → base where Source #

Every iterable type type forms an isomorphism with some Base type. For most Base types the isomorphism is the identity in both directions, but for some, like List and Sett, the embeddings are not the trivial identities because the concrete types are not binary type constructors. The Embed class also allows us to add newtypes which encode some Base type to the system.

Methods

toBase ∷ concrete → base Source #

fromBase ∷ base → concrete Source #

Instances

Instances details
Embed Bool Bool Source # 
Instance details

Defined in Control.Iterate.BaseTypes

Methods

toBaseBoolBool Source #

fromBaseBoolBool Source #

Embed (Set k) (Sett k ()) Source # 
Instance details

Defined in Control.Iterate.BaseTypes

Methods

toBaseSet k → Sett k () Source #

fromBaseSett k () → Set k Source #

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

Defined in Control.Iterate.BaseTypes

Methods

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

fromBaseList k v → [(k, v)] Source #

Embed (Map k v) (Map k v) Source # 
Instance details

Defined in Control.Iterate.BaseTypes

Methods

toBaseMap k v → Map k v Source #

fromBaseMap k v → Map k v Source #

Embed (Single k v) (Single k v) Source # 
Instance details

Defined in Control.Iterate.BaseTypes

Methods

toBaseSingle k v → Single k v Source #

fromBaseSingle k v → Single k v Source #

Types implementing a deep embedding of set algebra expressions

data BaseRep f k v where Source #

BaseRep witnesses Basic types. I.e. those types that are instances of both Basic and Iter. Pattern matching against a constructor of type BaseRep, determines which base type. For example data Tag f k v = Tag (BaseRep f k v) (f k v) case Tag MapR x -> -- here we know x :: Map.Map k v

Constructors

MapRBasic MapBaseRep Map k v 
SetRBasic SettBaseRep Sett k () 
ListRBasic ListBaseRep List k v 
SingleRBasic SingleBaseRep Single k v 

Instances

Instances details
Show (BaseRep f k v) Source # 
Instance details

Defined in Control.Iterate.BaseTypes

Methods

showsPrecIntBaseRep f k v → ShowS Source #

showBaseRep f k v → String Source #

showList ∷ [BaseRep f k v] → ShowS Source #

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) 

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 #

evalEmbed s t ⇒ Exp t → s Source #

Operators to build maps and sets, useable as Set Algebra Expressions

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.

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

domain exclude

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

domain restrict.

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

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

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.

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.

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.

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.

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.

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.

(◁) ∷ (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

(▷) ∷ (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

(∈) ∷ (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

(∪) ∷ (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.

(∪+) ∷ (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.

(∩) ∷ (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.

(≍) ∷ (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.

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

domain 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

(➖) ∷ (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.

keysEqualOrd k ⇒ Map k v1 → Map k v2 → Bool Source #

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.

Miscellaneous operators, including smart constructors for List, whose constructors are hidden.

materializeOrd k ⇒ BaseRep f k v → Collect (k, v) → f k v Source #

A witness (BaseRep) can be used to 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 duplicate values.

fromListOrd k ⇒ BaseRep f k v → (v → v → v) → [(k, v)] → f k v Source #

Turn a list of pairs into any Basic type. The first argument is a BaseRep which chooses what Base type to construct. The combine function comb = (\ earlier later -> later) will let values later in the list override ones earlier in the list, and comb = (\ earlier later -> earlier) will keep the value that appears first in the list