Copyright	(c) Erich Gut
License	BSD3
Maintainer	zerich.gut@gmail.com
Safe Haskell	None
Language	Haskell2010

OAlg.Entity.Sequence.PSequence

Contents

Sequence
Tree
X
Proposition

Description

partially defined sequences of items in x with a totally ordered index type i.

Synopsis

newtype PSequence i x = PSequence [(x, i)]
psqxs :: PSequence i x -> [(x, i)]
iProxy :: s i x -> Proxy i
psqSpan :: Ord i => PSequence i x -> Span i
psqEmpty :: PSequence i x
psqIsEmpty :: PSequence i x -> Bool
psequence :: Ord i => (x -> x -> x) -> [(x, i)] -> PSequence i x
psqHead :: PSequence i x -> (x, i)
psqTail :: PSequence i x -> PSequence i x
psqMap :: (x -> y) -> PSequence i x -> PSequence i y
psqMapShift :: Number i => i -> ((x, i) -> y) -> PSequence i x -> PSequence i y
psqMapWithIndex :: Monotone i j -> ((x, i) -> y) -> PSequence i x -> PSequence j y
newtype Monotone i j = Monotone (i -> j)
psqFilter :: (x -> Bool) -> PSequence i x -> PSequence i x
psqSplitWhile :: ((x, i) -> Bool) -> PSequence i x -> (PSequence i x, PSequence i x)
psqInterlace :: Ord i => (x -> y -> z) -> (x -> z) -> (y -> z) -> PSequence i x -> PSequence i y -> PSequence i z
psqCompose :: (Ord i, Ord j) => PSequence i x -> PSequence j i -> PSequence j x
psqAppend :: PSequence i x -> PSequence i x -> PSequence i x
psqShear :: Ord i => (Maybe a -> Maybe a -> Maybe a, i) -> (Maybe a -> Maybe a -> Maybe a, i) -> PSequence i a -> PSequence i a
psqSwap :: Ord i => i -> i -> PSequence i a -> PSequence i a
psqTree :: PSequence i x -> PTree i x
psqFromTree :: PTree i x -> PSequence i x
newtype PTree i x = PTree (Maybe (Tree i (x, i)))
ptrxs :: PTree i x -> [(x, i)]
ptrx :: Ord i => PTree i x -> i -> Maybe x
ptrEmpty :: PTree i x
ptrMax :: PTree i x -> Closure i
ptrMin :: PTree i x -> Closure i
ptrSpan :: PTree i x -> Span i
ptrFilter :: (x -> Bool) -> PTree i x -> PTree i x
ptrFilterWithIndex :: ((x, i) -> Bool) -> PTree i x -> PTree i x
ptrMap :: (x -> y) -> PTree i x -> PTree i y
ptrMapShift :: Number i => i -> ((x, i) -> y) -> PTree i x -> PTree i y
ptrMapWithIndex :: Monotone i j -> ((x, i) -> y) -> PTree i x -> PTree j y
xPSequence :: Ord i => N -> N -> X x -> X i -> X (PSequence i x)
prpPSequence :: Statement
prpPTreeFilter :: N -> Statement

Sequence

newtype PSequence i x Source #

partially defined sequences (x0,i0),(x1,i1).. of index items in x with a totally ordered index type i.

Property Let PSequence xis be in PSequence i x then holds: i < j for all ..(_,i):(_,j).. in xis.

Examples

>>> PSequence [('a',3),('b',7),('c',12)] :: PSequence N Char
PSequence [('a',3),('b',7),('c',12)]

and

>>> validate (valid (PSequence [('a',3),('b',7),('c',12)] :: PSequence N Char))
Valid

but

>>> validate (valid (PSequence [('a',3),('b',15),('c',12)] :: PSequence N Char))
Invalid

as Char is a totally ordered type it can serve as index type

>>> validate (valid (PSequence [(12,'c'),(3,'e'),(8,'x')] :: PSequence Char Z))
Valid

and they admit a total right operation <* of Permutation i

>>> (PSequence [(12,'c'),(3,'e'),(8,'x')] :: PSequence Char Z) <* pmtSwap 'e' 'x'
PSequence [(12,'c'),(8,'e'),(3,'x')]

Note As we keep the constructor public, it is crucial for there further use to ensure that they are valid!

Constructors

PSequence [(x, i)]

Instances

Instances details

Foldable (PSequence i) Source #
Instance details Defined in OAlg.Entity.Sequence.PSequence Methods fold :: Monoid m => PSequence i m -> m # foldMap :: Monoid m => (a -> m) -> PSequence i a -> m # foldMap' :: Monoid m => (a -> m) -> PSequence i a -> m # foldr :: (a -> b -> b) -> b -> PSequence i a -> b # foldr' :: (a -> b -> b) -> b -> PSequence i a -> b # foldl :: (b -> a -> b) -> b -> PSequence i a -> b # foldl' :: (b -> a -> b) -> b -> PSequence i a -> b # foldr1 :: (a -> a -> a) -> PSequence i a -> a # foldl1 :: (a -> a -> a) -> PSequence i a -> a # toList :: PSequence i a -> [a] # null :: PSequence i a -> Bool # length :: PSequence i a -> Int # elem :: Eq a => a -> PSequence i a -> Bool # maximum :: Ord a => PSequence i a -> a # minimum :: Ord a => PSequence i a -> a # sum :: Num a => PSequence i a -> a # product :: Num a => PSequence i a -> a #
Functor (PSequence i) Source #
Instance details Defined in OAlg.Entity.Sequence.PSequence Methods fmap :: (a -> b) -> PSequence i a -> PSequence i b # (<$) :: a -> PSequence i b -> PSequence i a #
(Entity x, Entity i, Ord i) => ConstructableSequence (PSequence i) i x Source #
Instance details Defined in OAlg.Entity.Sequence.PSequence Methods sequence :: (i -> Maybe x) -> Set i -> PSequence i x Source # (<&) :: PSequence i x -> Set i -> PSequence i x Source #
Ord i => Sequence (PSequence i) i x Source #
Instance details Defined in OAlg.Entity.Sequence.PSequence Methods graph :: p i -> PSequence i x -> Graph i x Source # list :: p i -> PSequence i x -> [(x, i)] Source # (??) :: PSequence i x -> i -> Maybe x Source #
(Entity x, Entity i, Ord i) => PermutableSequence (PSequence i) i x Source #
Instance details Defined in OAlg.Entity.Sequence.Permutation Methods permuteBy :: p i -> (w -> w -> Ordering) -> (x -> w) -> PSequence i x -> (PSequence i x, Permutation i) Source #
Embeddable [x] (PSequence N x) Source #
Instance details Defined in OAlg.Entity.Sequence.PSequence Methods inj :: [x] -> PSequence N x Source #
Projectible [x] (PSequence N x) Source #
Instance details Defined in OAlg.Entity.Sequence.PSequence Methods prj :: PSequence N x -> [x] Source #
Ord i => Opr (Permutation i) (PSequence i x) Source #
Instance details Defined in OAlg.Entity.Sequence.Permutation Methods (<*) :: PSequence i x -> Permutation i -> PSequence i x Source #
(Entity i, Ord i, Entity x) => TotalOpr (Permutation i) (PSequence i x) Source #
Instance details Defined in OAlg.Entity.Sequence.Permutation
ApplicativeG (PSequence i) (->) (->) Source #
Instance details Defined in OAlg.Entity.Sequence.PSequence Methods amapG :: (x -> y) -> PSequence i x -> PSequence i y Source #
(Show x, Show i) => Show (PSequence i x) Source #
Instance details Defined in OAlg.Entity.Sequence.PSequence Methods showsPrec :: Int -> PSequence i x -> ShowS # show :: PSequence i x -> String # showList :: [PSequence i x] -> ShowS #
(Eq x, Eq i) => Eq (PSequence i x) Source #
Instance details Defined in OAlg.Entity.Sequence.PSequence Methods (==) :: PSequence i x -> PSequence i x -> Bool # (/=) :: PSequence i x -> PSequence i x -> Bool #
(Ord x, Ord i) => Ord (PSequence i x) Source #
Instance details Defined in OAlg.Entity.Sequence.PSequence Methods compare :: PSequence i x -> PSequence i x -> Ordering # (<) :: PSequence i x -> PSequence i x -> Bool # (<=) :: PSequence i x -> PSequence i x -> Bool # (>) :: PSequence i x -> PSequence i x -> Bool # (>=) :: PSequence i x -> PSequence i x -> Bool # max :: PSequence i x -> PSequence i x -> PSequence i x # min :: PSequence i x -> PSequence i x -> PSequence i x #
LengthN (PSequence i x) Source #
Instance details Defined in OAlg.Entity.Sequence.PSequence Methods lengthN :: PSequence i x -> N Source #
(Entity x, Entity i, Ord i) => Validable (PSequence i x) Source #
Instance details Defined in OAlg.Entity.Sequence.PSequence Methods valid :: PSequence i x -> Statement Source #

psqxs :: PSequence i x -> [(x, i)] Source #

the underlying list of indexed values.

iProxy :: s i x -> Proxy i Source #

proxy of the second type valiable i.

psqSpan :: Ord i => PSequence i x -> Span i Source #

the span.

psqEmpty :: PSequence i x Source #

the empty partially defined sequence.

psqIsEmpty :: PSequence i x -> Bool Source #

checks of being empty.

psequence :: Ord i => (x -> x -> x) -> [(x, i)] -> PSequence i x Source #

the partial sequenc given by a aggregation function an a list of value index pairs, which will be sorted and accordingly aggregated by thegiven aggregation function.

psqHead :: PSequence i x -> (x, i) Source #

the head of a partial sequence.

psqTail :: PSequence i x -> PSequence i x Source #

the tail.

psqMap :: (x -> y) -> PSequence i x -> PSequence i y Source #

maps the entries, where the indices are preserved.

psqMapShift :: Number i => i -> ((x, i) -> y) -> PSequence i x -> PSequence i y Source #

shifts the indices of a partial sequence.

psqMapWithIndex :: Monotone i j -> ((x, i) -> y) -> PSequence i x -> PSequence j y Source #

maps of a PSequence according to the given strict monotone mapping and the given indexed mapping.

newtype Monotone i j Source #

predicate for strict monoton mappings.

Property Let _i__, j two Ord-types, and Monotone f in Monotone i j, then holds: For all x, y in i holds: compare (f x) (f y) == compare x y.

Constructors

Monotone (i -> j)

Instances

Instances details

(Ord i, Ord j, XStandard i, Show i) => Validable (Monotone i j) Source #
Instance details Defined in OAlg.Entity.Sequence.PSequence Methods valid :: Monotone i j -> Statement Source #

psqFilter :: (x -> Bool) -> PSequence i x -> PSequence i x Source #

filters the partially defiend sequence accordingly the given predicate.

psqSplitWhile :: ((x, i) -> Bool) -> PSequence i x -> (PSequence i x, PSequence i x) Source #

splits the sequence as long as the given predicate holds.

psqInterlace :: Ord i => (x -> y -> z) -> (x -> z) -> (y -> z) -> PSequence i x -> PSequence i y -> PSequence i z Source #

interlaces the tow partially defined sequences according to the given mappings.

psqCompose :: (Ord i, Ord j) => PSequence i x -> PSequence j i -> PSequence j x Source #

composition of the two partially defined sequences.

Property Let f be in PSequence i x and g be in PSequence j i then f `psqCompose` g is given by join . fmap ((??) f) . (??) g.

psqAppend :: PSequence i x -> PSequence i x -> PSequence i x Source #

appends the second partially defined sequence to the first.

Property Let zs = psqAppend xs ys where ..(x,l) = xs and (y,f).. = ys then holds:

If: l < f
Then: zs is valid.

psqShear :: Ord i => (Maybe a -> Maybe a -> Maybe a, i) -> (Maybe a -> Maybe a -> Maybe a, i) -> PSequence i a -> PSequence i a Source #

shears the two entries at the given position and leafs the others untouched.

Property Let x' = psqShear (sk,k) (sl,l) x, then holds

If: k < l
Then

x' k == sk (x k) (x l) and x' l == sl (x k) (x l).
x' i == x i for all i /= k, l.

psqSwap :: Ord i => i -> i -> PSequence i a -> PSequence i a Source #

swaps the the k-th and the l-th entry.

Property Let x' = psqSwap k l x, then holds:

If: k < l
Then

x' k == x l and x' l == x k.
x' i == x i for all i /= k, l.

psqTree :: PSequence i x -> PTree i x Source #

the induced tree.

psqFromTree :: PTree i x -> PSequence i x Source #

the induced partially sequence.

Tree

newtype PTree i x Source #

binary tree for efficient retrieving elements of a partially defined sequence.

Constructors

PTree (Maybe (Tree i (x, i)))

Instances

Instances details

Foldable (PTree i) Source #
Instance details Defined in OAlg.Entity.Sequence.PSequence Methods fold :: Monoid m => PTree i m -> m # foldMap :: Monoid m => (a -> m) -> PTree i a -> m # foldMap' :: Monoid m => (a -> m) -> PTree i a -> m # foldr :: (a -> b -> b) -> b -> PTree i a -> b # foldr' :: (a -> b -> b) -> b -> PTree i a -> b # foldl :: (b -> a -> b) -> b -> PTree i a -> b # foldl' :: (b -> a -> b) -> b -> PTree i a -> b # foldr1 :: (a -> a -> a) -> PTree i a -> a # foldl1 :: (a -> a -> a) -> PTree i a -> a # toList :: PTree i a -> [a] # null :: PTree i a -> Bool # length :: PTree i a -> Int # elem :: Eq a => a -> PTree i a -> Bool # maximum :: Ord a => PTree i a -> a # minimum :: Ord a => PTree i a -> a # sum :: Num a => PTree i a -> a # product :: Num a => PTree i a -> a #
Functor (PTree i) Source #
Instance details Defined in OAlg.Entity.Sequence.PSequence Methods fmap :: (a -> b) -> PTree i a -> PTree i b # (<$) :: a -> PTree i b -> PTree i a #
(Show i, Show x) => Show (PTree i x) Source #
Instance details Defined in OAlg.Entity.Sequence.PSequence Methods showsPrec :: Int -> PTree i x -> ShowS # show :: PTree i x -> String # showList :: [PTree i x] -> ShowS #
(Eq i, Eq x) => Eq (PTree i x) Source #
Instance details Defined in OAlg.Entity.Sequence.PSequence Methods (==) :: PTree i x -> PTree i x -> Bool # (/=) :: PTree i x -> PTree i x -> Bool #
(Ord i, Ord x) => Ord (PTree i x) Source #
Instance details Defined in OAlg.Entity.Sequence.PSequence Methods compare :: PTree i x -> PTree i x -> Ordering # (<) :: PTree i x -> PTree i x -> Bool # (<=) :: PTree i x -> PTree i x -> Bool # (>) :: PTree i x -> PTree i x -> Bool # (>=) :: PTree i x -> PTree i x -> Bool # max :: PTree i x -> PTree i x -> PTree i x # min :: PTree i x -> PTree i x -> PTree i x #
(Entity x, Entity i, Ord i) => Validable (PTree i x) Source #
Instance details Defined in OAlg.Entity.Sequence.PSequence Methods valid :: PTree i x -> Statement Source #