type-aligned-0.9.6: Various type-aligned sequence data structures.

Copyright(c) Atze van der Ploeg 2014
LicenseBSD-style
Maintaineratzeus@gmail.org
Stabilityprovisional
Portabilityportable
Safe HaskellSafe
LanguageHaskell98

Data.TASequence

Contents

Description

A type class for type aligned sequences: heterogeneous sequences where the types enforce the element order.

Type aligned sequences are best explained by an example: a type aligned sequence of functions is a sequence f 1 , f 2 , f 3 ... f n such that the composition of these functions f 1 ◦ f 2 ◦ f 3 ◦ ... ◦ f n is well typed. In other words: the result type of each function in the sequence must be the same as the argument type of the next function (if any). In general, the elements of a type aligned sequence do not have to be functions, i.e. values of type a → b, but can be values of type (c a b), for some binary type constructor c. Hence, we define a type aligned sequence to be a sequence of elements of the type (c a_i b_i ) with the side-condition b_i−1 = a_i . If s is the type of a type aligned sequence data structure, then (s c a b) is the type of a type aligned sequence where the first element has type (c a x), for some x, and the last element has type (c y b), for some y.

The simplest type aligned sequence data structure is a list, see Data.TASequence.ConsList. The other modules give various other type aligned sequence data structures. The data structure Data.TASequence.FastCatQueue supports the most operations in worst case constant time.

See the paper Reflection without Remorse: Revealing a hidden sequence to speed up Monadic Reflection, Atze van der Ploeg and Oleg Kiselyov, Haskell Symposium 2014 for more details.

Paper: http://homepages.cwi.nl/~ploeg/zseq.pdf Talk : http://www.youtube.com/watch?v=_XoI65Rxmss

Synopsis

Documentation

class TASequence s where #

A type class for type aligned sequences

Minimal complete defention: tempty and tsingleton and (tviewl or tviewr) and (>< or |> or <|)

Instances should satisfy the following laws:

Category laws:

tempty >< x == x
x >< tempty == x
(x >< y) >< z = x >< (y >< z)

Observation laws:

tviewl (tsingleton e >< s) == e :< s
tviewl tempty == TAEmptyL

The behaviour of <|,|>, tmap and tviewr is implied by the above laws and their default definitions.

Minimal complete definition

tempty, tsingleton

Methods

tempty :: s c x x #

tsingleton :: c x y -> s c x y #

(><) :: s c x y -> s c y z -> s c x z infix 5 #

Append two type aligned sequences

tviewl :: s c x y -> TAViewL s c x y #

View a type aligned sequence from the left

tviewr :: s c x y -> TAViewR s c x y #

View a type aligned sequence from the right

Default definition:

tviewr q = case tviewl q of 
  TAEmptyL -> TAEmptyR
  h :< t -> case tviewr t of
       TAEmptyR -> tempty   :> h
       p :> l   -> (h <| p) :> l

(|>) :: s c x y -> c y z -> s c x z infixl 5 #

Append a single element to the right

Default definition:

l |> r = l >< tsingleton r

(<|) :: c x y -> s c y z -> s c x z infixr 5 #

Append a single element to the left

Default definition:

l <| r = tsingleton l >< r

tmap :: (forall x y. c x y -> d x y) -> s c x y -> s d x y #

Apply a function to all elements in a type aligned sequence

Default definition:

tmap f q = case tviewl q of
   TAEmptyL -> tempty
   h :< t -> f h <| tmap f t

Instances

TASequence BinaryTree # 

Methods

tempty :: BinaryTree c x x #

tsingleton :: c x y -> BinaryTree c x y #

(><) :: BinaryTree c x y -> BinaryTree c y z -> BinaryTree c x z #

tviewl :: BinaryTree c x y -> TAViewL BinaryTree c x y #

tviewr :: BinaryTree c x y -> TAViewR BinaryTree c x y #

(|>) :: BinaryTree c x y -> c y z -> BinaryTree c x z #

(<|) :: c x y -> BinaryTree c y z -> BinaryTree c x z #

tmap :: (forall x y. c x y -> d x y) -> BinaryTree c x y -> BinaryTree d x y #

TASequence ConsList # 

Methods

tempty :: ConsList c x x #

tsingleton :: c x y -> ConsList c x y #

(><) :: ConsList c x y -> ConsList c y z -> ConsList c x z #

tviewl :: ConsList c x y -> TAViewL ConsList c x y #

tviewr :: ConsList c x y -> TAViewR ConsList c x y #

(|>) :: ConsList c x y -> c y z -> ConsList c x z #

(<|) :: c x y -> ConsList c y z -> ConsList c x z #

tmap :: (forall x y. c x y -> d x y) -> ConsList c x y -> ConsList d x y #

TASequence FingerTree # 

Methods

tempty :: FingerTree c x x #

tsingleton :: c x y -> FingerTree c x y #

(><) :: FingerTree c x y -> FingerTree c y z -> FingerTree c x z #

tviewl :: FingerTree c x y -> TAViewL FingerTree c x y #

tviewr :: FingerTree c x y -> TAViewR FingerTree c x y #

(|>) :: FingerTree c x y -> c y z -> FingerTree c x z #

(<|) :: c x y -> FingerTree c y z -> FingerTree c x z #

tmap :: (forall x y. c x y -> d x y) -> FingerTree c x y -> FingerTree d x y #

TASequence Queue # 

Methods

tempty :: Queue c x x #

tsingleton :: c x y -> Queue c x y #

(><) :: Queue c x y -> Queue c y z -> Queue c x z #

tviewl :: Queue c x y -> TAViewL Queue c x y #

tviewr :: Queue c x y -> TAViewR Queue c x y #

(|>) :: Queue c x y -> c y z -> Queue c x z #

(<|) :: c x y -> Queue c y z -> Queue c x z #

tmap :: (forall x y. c x y -> d x y) -> Queue c x y -> Queue d x y #

TASequence SnocList # 

Methods

tempty :: SnocList c x x #

tsingleton :: c x y -> SnocList c x y #

(><) :: SnocList c x y -> SnocList c y z -> SnocList c x z #

tviewl :: SnocList c x y -> TAViewL SnocList c x y #

tviewr :: SnocList c x y -> TAViewR SnocList c x y #

(|>) :: SnocList c x y -> c y z -> SnocList c x z #

(<|) :: c x y -> SnocList c y z -> SnocList c x z #

tmap :: (forall x y. c x y -> d x y) -> SnocList c x y -> SnocList d x y #

TASequence FastQueue # 

Methods

tempty :: FastQueue c x x #

tsingleton :: c x y -> FastQueue c x y #

(><) :: FastQueue c x y -> FastQueue c y z -> FastQueue c x z #

tviewl :: FastQueue c x y -> TAViewL FastQueue c x y #

tviewr :: FastQueue c x y -> TAViewR FastQueue c x y #

(|>) :: FastQueue c x y -> c y z -> FastQueue c x z #

(<|) :: c x y -> FastQueue c y z -> FastQueue c x z #

tmap :: (forall x y. c x y -> d x y) -> FastQueue c x y -> FastQueue d x y #

TASequence q => TASequence (ToCatQueue q) # 

Methods

tempty :: ToCatQueue q c x x #

tsingleton :: c x y -> ToCatQueue q c x y #

(><) :: ToCatQueue q c x y -> ToCatQueue q c y z -> ToCatQueue q c x z #

tviewl :: ToCatQueue q c x y -> TAViewL (ToCatQueue q) c x y #

tviewr :: ToCatQueue q c x y -> TAViewR (ToCatQueue q) c x y #

(|>) :: ToCatQueue q c x y -> c y z -> ToCatQueue q c x z #

(<|) :: c x y -> ToCatQueue q c y z -> ToCatQueue q c x z #

tmap :: (forall x y. c x y -> d x y) -> ToCatQueue q c x y -> ToCatQueue q d x y #

data TAViewL s c x y where #

Constructors

TAEmptyL :: TAViewL s c x x 
(:<) :: c x y -> s c y z -> TAViewL s c x z 

data TAViewR s c x y where #

Constructors

TAEmptyR :: TAViewR s c x x 
(:>) :: s c x y -> c y z -> TAViewR s c x z 

Orphan instances

TASequence s => Category * (s c) # 

Methods

id :: cat a a #

(.) :: cat b c -> cat a b -> cat a c #