Data.SequenceClass

A type class for sequences.

See the package type-aligned for a generalization of this type class sequences.

Documentation

class (Functor s, Foldable s) => Sequence s where

A type class for (finite) sequences

Minimal complete defention: empty and singleton and (viewl or viewr) and (>< or |> or <|)

Instances should satisfy the following laws:

Monoid laws:

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

Observation laws:

viewl (singleton e >< s) == e :< s
viewl empty == EmptyL

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

Minimal complete definition

empty, singleton

Methods

empty :: s c

singleton :: c -> s c

(><) :: s c -> s c -> s c infix 5

Append two sequences

viewl :: s c -> ViewL s c

View a sequence from the left

viewr :: s c -> ViewR s c

View a sequence from the right

Default definition:

viewr q = case viewl q of 
   EmptyL -> EmptyR
   h :< t -> case viewr t of
       EmptyR -> empty   :> h
       p :> l   -> (h <| p) :> l

(|>) :: s c -> c -> s c infixl 5

Append a single element to the right

Default definition:

l |> r = l >< singleton r

(<|) :: c -> s c -> s c infixr 5

Append a single element to the left

Default definition:

l <| r = singleton l >< r

Instances

Sequence []

Sequence Seq

Sequence BSeq

Sequence Queue

Sequence FastQueue

Sequence q => Sequence (ToCatQueue q)

data ViewL s c where

Constructors

EmptyL :: ViewL s c

(:<) :: c -> s c -> ViewL s c

data ViewR s c where

Constructors

EmptyR :: ViewR s c

(:>) :: s c -> c -> ViewR s c