set-algebra- Set Algebra
Safe HaskellSafe-Inferred



Supports writing 'Set algebra' expressions, using overloaded set operations, that can be applied to a variety of Basic types (Set, List, Map, etc). Also supports a mechanism to evaluate them efficiently, choosing datatype specific algorithms. This mechanism uses run-time rewrite rules to get the best algorithm. If there are no rewrite rules for a specific expression, falls back to a less efficient generic algorithm.



compileExp (f k v) → (Query k v, BaseRep f k v) Source #

Compile the (Exp (f k v)) to a Query iterator, and a BaseRep that indicates how to materialize the iterator to the correct type. Recall the iterator can be used to constuct many things using runCollect, but here we want to materialize it to the same type as the (Exp (f k v)), i.e. (f k v).

compileSubtermExp a → Exp (f k v) → Query k v Source #

runOrd k ⇒ (Query k v, BaseRep f k v) → f k v Source #

runSetExpOrd k ⇒ Exp (f k v) → f k v Source #

runSetOrd k ⇒ Exp (f k v) → f k v Source #

sameDomain ∷ (Ord k, Iter f, Iter g) ⇒ f k b → g k c → Bool Source #

cost O(min (size m) (size n) * log(max (size m) (size n))), BUT the constants are high, too slow except for small maps.

computeExp t → t Source #

evalEmbed s t ⇒ Exp t → s Source #

computeSlowExp t → t Source #

lifoIter f ⇒ f k v → Collect (k, v) Source #

fifoIter f ⇒ f k v → Collect (k, v) Source #

addp ∷ (Ord k, Basic f) ⇒ (v → v → v) → (k, v) → f k v → f k v Source #

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

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.

(⨝) ∷ (Ord k, Iter f, Iter g) ⇒ f k b → g k c → Collect (k, b, c) Source #

domEq ∷ (Ord k, Iter f, Iter g) ⇒ f k b → g k c → Collect (k, b, c) Source #

domEqSlow ∷ (Ord k, Iter f, Iter g) ⇒ f k b → g k c → Collect (k, b, c) Source #