small-steps-0.1.0.0: Small step semantics
Safe HaskellNone
LanguageHaskell2010

Control.Iterate.SetAlgebra

Synopsis

Documentation

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

Minimal complete definition

addkv, removekey, domain, range

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 #

range :: Ord v => f k v -> Set v Source #

emptyc :: Ord k => f k v Source #

Instances

Instances details
Basic Map Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

addpair :: Ord k => k -> v -> Map k v -> Map k v Source #

addkv :: Ord k => (k, v) -> Map k v -> (v -> v -> v) -> Map k v Source #

removekey :: Ord k => k -> Map k v -> Map k v Source #

domain :: Ord k => Map k v -> Set k Source #

range :: Ord v => Map k v -> Set v Source #

emptyc :: Ord k => Map k v Source #

Basic List Source #

The constructor for List is hidden, since it requires some invariants. Use fromPairs to build an initial List.

Instance details

Defined in Control.Iterate.SetAlgebra

Methods

addpair :: Ord k => k -> v -> List k v -> List k v Source #

addkv :: Ord k => (k, v) -> List k v -> (v -> v -> v) -> List k v Source #

removekey :: Ord k => k -> List k v -> List k v Source #

domain :: Ord k => List k v -> Set k Source #

range :: Ord v => List k v -> Set v Source #

emptyc :: Ord k => List k v Source #

Basic Sett Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

addpair :: Ord k => k -> v -> Sett k v -> Sett k v Source #

addkv :: Ord k => (k, v) -> Sett k v -> (v -> v -> v) -> Sett k v Source #

removekey :: Ord k => k -> Sett k v -> Sett k v Source #

domain :: Ord k => Sett k v -> Set k Source #

range :: Ord v => Sett k v -> Set v Source #

emptyc :: Ord k => Sett k v Source #

Basic Single Source # 
Instance details

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 #

range :: Ord v => Single k v -> Set v Source #

emptyc :: Ord k => Single k v Source #

Ord v => Basic (BiMap v) Source # 
Instance details

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 #

range :: Ord v0 => BiMap v k v0 -> Set v0 Source #

emptyc :: Ord k => BiMap v k v0 Source #

fromPairs :: Ord k => (v -> v -> v) -> [(k, v)] -> List k v Source #

normalize :: Ord k => (v -> v -> v) -> [(k, v)] -> [(k, v)] Source #

data Single k v where Source #

Constructors

Single :: k -> v -> Single k v 
Fail :: Single k v 
SetSingle :: k -> Single k () 

Instances

Instances details
Iter Single Source # 
Instance details

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 #

element :: Ord k => k -> Single k v -> Collect () Source #

Basic Single Source # 
Instance details

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 #

range :: Ord v => Single k v -> Set v Source #

emptyc :: Ord k => Single k v Source #

(Eq k, Eq v) => Eq (Single k v) Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

(==) :: Single k v -> Single k v -> Bool #

(/=) :: Single k v -> Single k v -> Bool #

(Show k, Show v) => Show (Single k v) Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

showsPrec :: Int -> Single k v -> ShowS #

show :: Single k v -> String #

showList :: [Single k v] -> ShowS #

Ord k => HasQuery (Single k v) k v Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

query :: Single k v -> Query k v Source #

Ord k => HasExp (Single k v) (Single k v) Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

toExp :: Single k v -> Exp (Single k v) Source #

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

Defined in Control.Iterate.SetAlgebra

Methods

toBase :: Single k v -> Single k v Source #

fromBase :: Single k v -> Single k v Source #

mapflip :: (v -> v -> v) -> v -> v -> v Source #

data BiMap v a b where Source #

Constructors

MkBiMap :: v ~ b => !(Map a b) -> !(Map b (Set a)) -> BiMap v a b 

Instances

Instances details
Ord v => Iter (BiMap v) Source # 
Instance details

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 # 
Instance details

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 #

range :: Ord v0 => BiMap v k v0 -> Set v0 Source #

emptyc :: Ord k => BiMap v k v0 Source #

(Ord k, Ord v) => HasExp (Bimap k v) (Bimap k v) Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

toExp :: Bimap k v -> Exp (Bimap k v) Source #

(Eq k, Eq v) => Eq (BiMap u k v) Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

(==) :: BiMap u k v -> BiMap u k v -> Bool #

(/=) :: BiMap u k v -> BiMap u k v -> Bool #

(Show k, Show v) => Show (BiMap u k v) Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

showsPrec :: Int -> BiMap u k v -> ShowS #

show :: BiMap u k v -> String #

showList :: [BiMap u k v] -> ShowS #

(Ord a, Ord b, ToCBOR a, ToCBOR b) => ToCBOR (BiMap b a b) Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

toCBOR :: BiMap b a b -> Encoding Source #

encodedSizeExpr :: (forall t. ToCBOR t => Proxy t -> Size) -> Proxy (BiMap b a b) -> Size Source #

encodedListSizeExpr :: (forall t. ToCBOR t => Proxy t -> Size) -> Proxy [BiMap b a b] -> Size Source #

(Ord a, Ord b, FromCBOR a, FromCBOR b) => FromCBOR (BiMap b a b) Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

fromCBOR :: Decoder s (BiMap b a b) Source #

label :: Proxy (BiMap b a b) -> Text Source #

NFData (BiMap v a b) Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

rnf :: BiMap v a b -> () #

(NoThunks a, NoThunks b) => NoThunks (BiMap v a b) Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

(Ord v, Ord k) => HasQuery (BiMap v k v) k v Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

query :: BiMap v k v -> Query k v Source #

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

Defined in Control.Iterate.SetAlgebra

Methods

toBase :: BiMap v k v -> BiMap v k v Source #

fromBase :: BiMap v k v -> BiMap v k v Source #

decodeMapAsBimap :: (FromCBOR a, FromCBOR b, Ord a, Ord b) => Decoder s (BiMap b a b) Source #

Decode a serialised CBOR Map as a Bimap

addBack :: (Ord v, Ord k) => v -> k -> Map v (Set k) -> Map v (Set k) Source #

retract :: (Ord v, Ord k) => v -> k -> Map v (Set k) -> Map v (Set k) Source #

insertBackwards :: (Ord k, Ord v) => v -> v -> k -> Map v (Set k) -> Map v (Set k) Source #

biMapFromList :: (Ord k, Ord v) => (v -> v -> v) -> [(k, v)] -> BiMap v k v Source #

biMapFromAscDistinctList :: (Ord k, Ord v) => [(k, v)] -> BiMap v k v Source #

type Bimap k v = BiMap v k v Source #

removeval :: (Ord k, Ord v) => v -> BiMap v k v -> BiMap v k v Source #

data Sett k v where Source #

Constructors

Sett :: Set k -> Sett k () 

Instances

Instances details
Iter Sett Source # 
Instance details

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 #

element :: Ord k => k -> Sett k v -> Collect () Source #

Basic Sett Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

addpair :: Ord k => k -> v -> Sett k v -> Sett k v Source #

addkv :: Ord k => (k, v) -> Sett k v -> (v -> v -> v) -> Sett k v Source #

removekey :: Ord k => k -> Sett k v -> Sett k v Source #

domain :: Ord k => Sett k v -> Set k Source #

range :: Ord v => Sett k v -> Set v Source #

emptyc :: Ord k => Sett k v Source #

Ord k => HasExp (Set k) (Sett k ()) Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

toExp :: Set k -> Exp (Sett k ()) Source #

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

Defined in Control.Iterate.SetAlgebra

Methods

toBase :: Set k -> Sett k () Source #

fromBase :: Sett k () -> Set k Source #

Eq k => Eq (Sett k ()) Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

(==) :: Sett k () -> Sett k () -> Bool #

(/=) :: Sett k () -> Sett k () -> Bool #

Show key => Show (Sett key ()) Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

showsPrec :: Int -> Sett key () -> ShowS #

show :: Sett key () -> String #

showList :: [Sett key ()] -> ShowS #

class Embed concrete base | concrete -> base where Source #

Methods

toBase :: concrete -> base Source #

fromBase :: base -> concrete Source #

Instances

Instances details
Embed Bool Bool Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

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

Defined in Control.Iterate.SetAlgebra

Methods

toBase :: [(k, v)] -> List k v Source #

fromBase :: List k v -> [(k, v)] Source #

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

Defined in Control.Iterate.SetAlgebra

Methods

toBase :: Set k -> Sett k () Source #

fromBase :: Sett k () -> Set k Source #

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

Defined in Control.Iterate.SetAlgebra

Methods

toBase :: Map k v -> Map k v Source #

fromBase :: Map k v -> Map k v Source #

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

Defined in Control.Iterate.SetAlgebra

Methods

toBase :: Single k v -> Single k v Source #

fromBase :: Single k v -> Single k v Source #

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

Defined in Control.Iterate.SetAlgebra

Methods

toBase :: BiMap v k v -> BiMap v k v Source #

fromBase :: BiMap v k v -> BiMap v k v Source #

class Iter f where Source #

Minimal complete definition

nxt, lub

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 #

lookup :: Ord key => key -> f key rng -> Maybe rng Source #

element :: Ord k => k -> f k v -> Collect () Source #

Instances

Instances details
Iter Map Source # 
Instance details

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 #

element :: Ord k => k -> Map k v -> Collect () Source #

Iter Query Source # 
Instance details

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 #

element :: Ord k => k -> Query k v -> Collect () Source #

Iter List Source # 
Instance details

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 #

element :: Ord k => k -> List k v -> Collect () Source #

Iter Sett Source # 
Instance details

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 #

element :: Ord k => k -> Sett k v -> Collect () Source #

Iter Single Source # 
Instance details

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 #

element :: Ord k => k -> Single k v -> Collect () Source #

Ord v => Iter (BiMap v) Source # 
Instance details

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 #

data List k v where Source #

Constructors

UnSafeList :: Ord k => [(k, v)] -> List k v 

Instances

Instances details
Iter List Source # 
Instance details

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 #

element :: Ord k => k -> List k v -> Collect () Source #

Basic List Source #

The constructor for List is hidden, since it requires some invariants. Use fromPairs to build an initial List.

Instance details

Defined in Control.Iterate.SetAlgebra

Methods

addpair :: Ord k => k -> v -> List k v -> List k v Source #

addkv :: Ord k => (k, v) -> List k v -> (v -> v -> v) -> List k v Source #

removekey :: Ord k => k -> List k v -> List k v Source #

domain :: Ord k => List k v -> Set k Source #

range :: Ord v => List k v -> Set v Source #

emptyc :: Ord k => List k v Source #

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

Defined in Control.Iterate.SetAlgebra

Methods

toExp :: [(k, v)] -> Exp (List k v) Source #

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

Defined in Control.Iterate.SetAlgebra

Methods

toBase :: [(k, v)] -> List k v Source #

fromBase :: List k v -> [(k, v)] Source #

(Eq k, Eq v) => Eq (List k v) Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

(==) :: List k v -> List k v -> Bool #

(/=) :: List k v -> List k v -> Bool #

(Show k, Show v) => Show (List k v) Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

showsPrec :: Int -> List k v -> ShowS #

show :: List k v -> String #

showList :: [List k v] -> ShowS #

unList :: List k v -> [(k, v)] Source #

noKeys :: Ord k => Map k a -> Map k b -> Map k a Source #

keysEqual :: Ord k => Map k v1 -> Map k v2 -> Bool Source #

sameDomain :: (Ord k, Iter f, Iter g) => f k b -> g k c -> Bool Source #

splitMember :: Ord k => k -> Map k a -> (Map k a, Bool, Map k a) Source #

A variant of splitLookup that indicates only whether the key was present, rather than producing its value. This is used to implement keysEqual to avoid allocating unnecessary Just constructors.

data StrictTriple a b c Source #

Constructors

StrictTriple !a !b !c 

intersectDomP :: Ord k => (k -> v2 -> Bool) -> Map k v1 -> Map k v2 -> Map k v2 Source #

intersetDomP p m1 m2 == Keep the key and value from m2, iff (the key is in the dom of m1) && ((p key value) is true)

intersectDomPLeft :: Ord k => (k -> v2 -> Bool) -> Map k v1 -> Map k v2 -> Map k v1 Source #

  • Similar to intersectDomP, except the Map returned has the same key as the first input map, rather than the second input map.

intersectMapSetFold :: Ord k => (k -> v -> ans -> ans) -> Map k v -> Set k -> ans -> ans Source #

  • fold over the intersection of a Map and a Set

disjointMapSetFold :: Ord k => (k -> v -> ans -> ans) -> Map k v -> Set k -> ans -> ans Source #

Fold with accum all those pairs in the map, not appearing in the set.

data BaseRep f k v where Source #

Constructors

MapR :: Basic Map => BaseRep Map k v 
SetR :: Basic Sett => BaseRep Sett k () 
ListR :: Basic List => BaseRep List k v 
SingleR :: Basic Single => BaseRep Single k v 
BiMapR :: (Basic (BiMap v), Ord v) => BaseRep (BiMap v) k v 

Instances

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

Defined in Control.Iterate.SetAlgebra

Methods

showsPrec :: Int -> BaseRep f k v -> ShowS #

show :: BaseRep f k v -> String #

showList :: [BaseRep f k v] -> ShowS #

lifo :: Iter f => f k v -> Collect (k, v) Source #

fifo :: Iter f => f k v -> Collect (k, v) 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) => BaseRep f k v -> f k v -> Exp (f k v) 
Dom :: Ord 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 (f k n) -> Exp (f k n) 
UnionOverrideRight :: Ord k => Exp (f k v) -> Exp (g k v) -> Exp (f k v) 
Singleton :: Ord k => k -> v -> Exp (Single k v) 
SetSingleton :: Ord 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.SetAlgebra

Methods

showsPrec :: Int -> Exp t -> ShowS #

show :: Exp t -> String #

showList :: [Exp t] -> ShowS #

HasExp (Exp t) t Source #

The simplest Base type is one that is already an Exp

Instance details

Defined in Control.Iterate.SetAlgebra

Methods

toExp :: Exp t -> Exp t 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 #

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

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

Methods

toExp :: Exp t -> Exp t Source #

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

Defined in Control.Iterate.SetAlgebra

Methods

toExp :: [(k, v)] -> Exp (List k v) Source #

Ord k => HasExp (Set k) (Sett k ()) Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

toExp :: Set k -> Exp (Sett k ()) Source #

Ord k => HasExp (Map k v) (Map k v) Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

toExp :: Map k v -> Exp (Map k v) Source #

(Ord k, Ord v) => HasExp (Bimap k v) (Bimap k v) Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

toExp :: Bimap k v -> Exp (Bimap k v) Source #

Ord k => HasExp (Single k v) (Single k v) Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

toExp :: Single k v -> Exp (Single k v) Source #

dom :: (Ord k, HasExp s (f k v)) => s -> Exp (Sett k ()) Source #

rng :: (Ord k, Ord v) => HasExp s (f k v) => s -> Exp (Sett v ()) Source #

(◁) :: (Ord k, HasExp s1 (Sett k ()), HasExp s2 (f k v)) => s1 -> s2 -> Exp (f k v) Source #

(<|) :: (Ord k, HasExp s1 (Sett k ()), HasExp s2 (f k v)) => s1 -> s2 -> Exp (f k v) Source #

drestrict :: (Ord k, HasExp s1 (Sett k ()), HasExp s2 (f k v)) => s1 -> s2 -> Exp (f k v) Source #

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

dexclude :: (Ord k, Iter g, HasExp s1 (g k ()), HasExp s2 (f k 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 #

(|>) :: (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 #

(⋫) :: (Ord k, Iter g, Ord v, HasExp s1 (f k v), HasExp s2 (g 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 #

(∈) :: (Show k, Ord k, Iter g, HasExp s (g k ())) => k -> s -> Exp Bool Source #

(∉) :: (Show k, Ord k, Iter g, HasExp s (g k ())) => k -> s -> Exp Bool Source #

notelem :: (Show k, Ord k, Iter g, HasExp s (g k ())) => k -> s -> Exp Bool Source #

(∪) :: (Show k, Show v, Ord k, HasExp s1 (f k v), HasExp s2 (g k 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 #

(⨃) :: (Ord k, HasExp s1 (f k v), HasExp s2 (g k v)) => s1 -> s2 -> Exp (f k v) Source #

unionright :: (Ord k, HasExp s1 (f k v), HasExp s2 (g k v)) => s1 -> s2 -> Exp (f k v) Source #

(∪+) :: (Ord k, Monoid n, HasExp s1 (f k n), HasExp s2 (f k n)) => s1 -> s2 -> Exp (f k n) Source #

unionplus :: (Ord k, Monoid n, HasExp s1 (f k n), HasExp s2 (f k n)) => s1 -> s2 -> Exp (f k n) Source #

singleton :: Ord k => k -> v -> Exp (Single k v) Source #

setSingleton :: Ord k => k -> Exp (Single k ()) Source #

(∩) :: (Ord k, Iter f, Iter g, HasExp s1 (f k v), HasExp s2 (g k u)) => s1 -> s2 -> Exp (Sett k ()) Source #

intersect :: (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 #

subset :: (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 (f k v) 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 #

(≍) :: (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 #

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

P1 :: Pat (d, c, b, a) d 
P2 :: Pat (d, c, b, a) c 
P3 :: Pat (d, c, b, a) b 
P4 :: Pat (d, c, b, a) a 
PPair :: Pat (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

X1 :: Expr (d, c, b, a) d 
X2 :: Expr (d, c, b, a) c 
X3 :: Expr (d, c, b, a) b 
X4 :: Expr (d, c, b, a) a 
HasKey :: (Iter f, Ord k) => Expr e k -> f k v -> Expr e Bool 
Neg :: Expr e Bool -> Expr e Bool 
Ap :: Lam (a -> b -> c) -> Expr e a -> Expr e b -> Expr e c 
EPair :: Expr e a -> Expr e b -> Expr e (a, b) 
FST :: Expr e (a, b) -> Expr e a 
SND :: Expr e (a, b) -> Expr e b 
Lit :: Show t => t -> Expr env t 

Instances

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

Defined in Control.Iterate.SetAlgebra

Methods

showsPrec :: Int -> Expr (a, b, c, d) t -> ShowS #

show :: Expr (a, b, c, d) t -> String #

showList :: [Expr (a, b, c, d) t] -> ShowS #

data Lam t where Source #

Constructors

Lam :: Pat (d, c, b, a) t -> Pat (d, c, b, a) s -> Expr (d, c, b, a) v -> Lam (t -> s -> v) 
Add :: Num n => Lam (n -> n -> n) 
Cat :: Monoid m => Lam (m -> m -> m) 
Eql :: Eq t => Lam (t -> t -> Bool) 
Both :: Lam (Bool -> Bool -> Bool) 
Lift :: (a -> b -> c) -> Lam (a -> b -> c) 

Instances

Instances details
Show (Lam t) Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

showsPrec :: Int -> Lam t -> ShowS #

show :: Lam t -> String #

showList :: [Lam t] -> ShowS #

bindE :: Pat (a, b, c, d) t -> Expr (w, x, y, z) t -> StringEnv -> StringEnv Source #

showE :: StringEnv -> Expr (a, b, c, d) t -> String Source #

showP :: StringEnv -> Pat any t -> String Source #

data Fun t Source #

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

Methods

showsPrec :: Int -> Fun t -> ShowS #

show :: Fun t -> String #

showList :: [Fun t] -> ShowS #

apply :: Fun t -> t Source #

first :: Fun (v -> s -> v) Source #

second :: Fun (v -> s -> s) Source #

plus :: Monoid t => Fun (t -> t -> t) Source #

eql :: Eq t => Fun (t -> t -> Bool) Source #

constant :: Show 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 #

rngFst :: Fun (x -> (a, b) -> a) Source #

rngSnd :: Fun (x -> (a, b) -> b) Source #

compose1 :: Fun (t1 -> t2 -> t3) -> Fun (t1 -> t4 -> t2) -> Fun (t1 -> t4 -> t3) Source #

compSndL :: Fun (k -> (a, b) -> c) -> Fun (k -> d -> a) -> Fun (k -> (d, b) -> c) Source #

compSndR :: Fun (k -> (a, b) -> c) -> Fun (k -> d -> b) -> Fun (k -> (a, d) -> c) Source #

compCurryR :: Fun (k -> (a, b) -> d) -> Fun (a -> c -> b) -> Fun (k -> (a, c) -> d) Source #

nEgate :: Fun (k -> v -> Bool) -> Fun (k -> v -> Bool) Source #

always :: Fun (a -> b -> Bool) Source #

both :: Fun (a -> b -> Bool) -> Fun (a -> b -> Bool) -> Fun (a -> b -> Bool) Source #

lift :: (a -> b -> c) -> Fun (a -> b -> c) Source #

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

addp :: (Ord k, Basic f) => (v -> v -> v) -> (k, v) -> f k v -> f k v Source #

fromList :: Ord k => BaseRep f k v -> (v -> v -> v) -> [(k, v)] -> f k v Source #

(⨝) :: (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 #

data Query k v where Source #

Constructors

BaseD :: (Iter f, Ord k) => BaseRep f k v -> f k v -> Query k v 
ProjectD :: Ord k => Query k v -> Fun (k -> v -> u) -> Query k u 
AndD :: Ord 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 
AndPD :: Ord k => Query k v -> Query k u -> Fun (k -> (v, u) -> w) -> Query k w 
OrD :: Ord k => Query k v -> Query k v -> Fun (v -> v -> v) -> Query k v 
GuardD :: Ord k => Query k v -> Fun (k -> v -> Bool) -> Query k v 
DiffD :: Ord k => Query k v -> Query k u -> Query k v 

Instances

Instances details
Iter Query Source # 
Instance details

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 #

element :: Ord k => k -> Query k v -> Collect () Source #

Show (Query k v) Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

showsPrec :: Int -> Query k v -> ShowS #

show :: Query k v -> String #

showList :: [Query k v] -> ShowS #

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

Defined in Control.Iterate.SetAlgebra

Methods

query :: Query k v -> Query k v Source #

projD :: Ord k => Query k v -> Fun (k -> v -> u) -> Query k u Source #

andD :: Ord k => Query k v1 -> Query k v2 -> Query k (v1, v2) Source #

andPD :: Ord 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 #

guardD :: Ord k => Query k v -> Fun (k -> v -> Bool) -> Query k v Source #

compileSubterm :: Exp a -> Exp (f k v) -> Query 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). ================================================================================

compile :: Exp (f k v) -> (Query k v, BaseRep f k v) Source #

runSetExp :: Ord k => Exp (f k v) -> f k v Source #

runSet :: Ord k => Exp (f k v) -> f k v Source #

run :: Ord k => (Query k v, BaseRep f k v) -> f k v Source #

compute :: Exp t -> t Source #

eval :: Embed s t => Exp t -> s Source #

projStep :: Ord k => (t -> Collect (k, v, Query k v)) -> Fun (k -> v -> u) -> t -> Collect (k, u, Query k u) Source #

andStep :: Ord 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 #

andPstep :: Ord 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 #

guardStep :: Ord a => (Query a b -> Collect (a, b, Query a b)) -> Fun (a -> b -> Bool) -> Query a b -> Collect (a, b, Query a b) Source #

diffStep :: Ord k => (k, v, Query k v) -> Query k u -> Collect (k, v, Query k v) Source #

rngStep :: Ord v => Query k v -> Sett v () Source #

nxtQuery :: Query a b -> Collect (a, b, Query a b) Source #

lubQuery :: Ord a => a -> Query a b -> Collect (a, b, Query a b) 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 #

class HasQuery concrete k v where Source #

Methods

query :: concrete -> Query k v Source #

Instances

Instances details
Ord k => HasQuery [(k, v)] k v Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

query :: [(k, v)] -> Query k v Source #

Ord k => HasQuery (Set k) k () Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

query :: Set k -> Query k () Source #

Ord k => HasQuery (Map k v) k v Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

query :: Map k v -> Query k v Source #

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

Defined in Control.Iterate.SetAlgebra

Methods

query :: Query k v -> Query k v Source #

Ord k => HasQuery (Single k v) k v Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

query :: Single k v -> Query k v Source #

(Ord v, Ord k) => HasQuery (BiMap v k v) k v Source # 
Instance details

Defined in Control.Iterate.SetAlgebra

Methods

query :: BiMap v k v -> Query k v Source #