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

Control.Iterate.BaseTypes

Description

Defines what types can be used in the SetAlgebra, and what operations those types must support (Iter, Basic, Embed)

Synopsis

Documentation

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

embedding

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 List k v where 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.

Constructors

UnSafeListOrd k ⇒ [(k, v)] → List k v 

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 #

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

fromPairsOrd k ⇒ (v → v → v) → [(k, v)] → List k v Source #

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

data Sett k v where Source #

Constructors

SettSet k → Sett k () 

Instances

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

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 #

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 ⇒ HasExp (Set k) (Sett k ()) Source # 
Instance details

Defined in Control.Iterate.Exp

Methods

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

Show key ⇒ Show (Sett key ()) Source # 
Instance details

Defined in Control.Iterate.BaseTypes

Methods

showsPrecIntSett key () → ShowS Source #

showSett key () → String Source #

showList ∷ [Sett key ()] → ShowS Source #

Eq k ⇒ Eq (Sett k ()) Source # 
Instance details

Defined in Control.Iterate.BaseTypes

Methods

(==)Sett k () → Sett k () → Bool Source #

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