| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Control.Iterate.BaseTypes
Description
Defines what types can be used in the SetAlgebra, and what operations those types must support (Iter, Basic, Embed)
Synopsis
- class Iter f where
- nxt ∷ f a b → Collect (a, b, f a b)
- lub ∷ Ord k ⇒ k → f k b → Collect (k, b, f k b)
- hasNxt ∷ f a b → Maybe (a, b, f a b)
- hasLub ∷ Ord k ⇒ k → f k b → Maybe (k, b, f k b)
- haskey ∷ Ord key ⇒ key → f key b → Bool
- isnull ∷ f k v → Bool
- lookup ∷ Ord key ⇒ key → f key rng → Maybe rng
- element ∷ Ord k ⇒ k → f k v → Collect ()
- class Basic f where
- data BaseRep f k v where
- data List k v where
- UnSafeList ∷ Ord k ⇒ [(k, v)] → List k v
- unList ∷ List k v → [(k, v)]
- fromPairs ∷ Ord k ⇒ (v → v → v) → [(k, v)] → List k v
- normalize ∷ Ord k ⇒ (v → v → v) → [(k, v)] → [(k, v)]
- data Single k v where
- data Sett k v where
- class Embed concrete base | concrete → base where
Documentation
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.
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 #
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.
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 #
Instances
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.
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 #
remove the pair with key k, if it is there.
domain ∷ Ord k ⇒ f k v → Set k Source #
the set of keys
range ∷ Ord v ⇒ f k v → Set v Source #
the set of values.
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
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
| UnSafeList ∷ Ord k ⇒ [(k, v)] → List k v |
Instances
| Basic List Source # | |
Defined in Control.Iterate.BaseTypes | |
| Iter List Source # | |
Defined in Control.Iterate.BaseTypes 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 # | |
| Ord k ⇒ Embed [(k, v)] (List k v) Source # | |
| Ord k ⇒ HasExp [(k, v)] (List k v) Source # | |
| (Show k, Show v) ⇒ Show (List k v) Source # | |
| (Eq k, Eq v) ⇒ Eq (List 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.
Instances
| Basic Single Source # | |
Defined in Control.Iterate.BaseTypes | |
| Iter Single Source # | |
Defined in Control.Iterate.BaseTypes 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 # | |
| (Show k, Show v) ⇒ Show (Single k v) Source # | |
| (Eq k, Eq v) ⇒ Eq (Single k v) Source # | |
| Ord k ⇒ HasQuery (Single k v) k v Source # | |
| Embed (Single k v) (Single k v) Source # | |
| Ord k ⇒ HasExp (Single k v) (Single k v) Source # | |
Instances
| Basic Sett Source # | |
Defined in Control.Iterate.BaseTypes | |
| Iter Sett Source # | |
Defined in Control.Iterate.BaseTypes 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 # | |
| Embed (Set k) (Sett k ()) Source # | |
| Ord k ⇒ HasExp (Set k) (Sett k ()) Source # | |
| Show key ⇒ Show (Sett key ()) Source # | |
| Eq k ⇒ Eq (Sett k ()) 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.