Copyright | (c) Atze van der Ploeg 2014 |
---|---|
License | BSD-style |
Maintainer | atzeus@gmail.org |
Stability | provisional |
Portability | portable |
Safe Haskell | Safe |
Language | Haskell98 |
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
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
Methods
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
Orphan instances
TASequence s => Category * (s c) # | |