Data.SequenceClass

A type class for sequences.

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

Documentation

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

A type class for (finite) sequences

Instances should be free monoids (ignoring issues with infinite and partially defined structures), just like lists, with singleton as the canonical injection and foldMap factoring functions. In particular, they should satisfy the following laws:

Semigroup and Monoid laws:

(><) == (Data.Semigroup.<>)
empty == mempty

In particular, this requires that

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

FoldMap/singleton laws:

For any Monoid m and any function f :: c -> m,

1. foldMap f is a monoid morphism:

   • foldMap f mempty = mempty

   • foldMap f (m <> n) = foldMap f m <> foldMap f n

2. foldMap undoes singleton:

   foldMap f . singleton = f

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.

Warning: the default definitions are typically awful. Check them carefully before relying on them. In particular, they may well work in O(n^2) time (or worse?) when even definitions that convert to and from lists would work in O(n) time. Exceptions: for sequences with constant time concatenation, the defaults for <| and |> are okay. For sequences with constant time |>, the default for fromList is okay.

Minimal complete definition

empty, singleton, (viewl | viewr), ((><) | (|>) | (<|))

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

fromList :: [c] -> s c

Convert a list to a sequence

Default definition:

fromList = foldl' (|>) empty

Instances

Sequence []

Defined in Data.SequenceClass

Methods

empty :: [c]

singleton :: c -> [c]

(><) :: [c] -> [c] -> [c]

viewl :: [c] -> ViewL [] c

viewr :: [c] -> ViewR [] c

(|>) :: [c] -> c -> [c]

(<|) :: c -> [c] -> [c]

fromList :: [c] -> [c]

Sequence Seq

Defined in Data.SequenceClass

Methods

empty :: Seq c

singleton :: c -> Seq c

(><) :: Seq c -> Seq c -> Seq c

viewl :: Seq c -> ViewL Seq c

viewr :: Seq c -> ViewR Seq c

(|>) :: Seq c -> c -> Seq c

(<|) :: c -> Seq c -> Seq c

fromList :: [c] -> Seq c

Sequence Queue

Defined in Data.Sequence.Queue.Internal

Methods

empty :: Queue c

singleton :: c -> Queue c

(><) :: Queue c -> Queue c -> Queue c

viewl :: Queue c -> ViewL Queue c

viewr :: Queue c -> ViewR Queue c

(|>) :: Queue c -> c -> Queue c

(<|) :: c -> Queue c -> Queue c

fromList :: [c] -> Queue c

Sequence FastQueue

Defined in Data.Sequence.FastQueue.Internal

Methods

empty :: FastQueue c

singleton :: c -> FastQueue c

(><) :: FastQueue c -> FastQueue c -> FastQueue c

viewl :: FastQueue c -> ViewL FastQueue c

viewr :: FastQueue c -> ViewR FastQueue c

(|>) :: FastQueue c -> c -> FastQueue c

(<|) :: c -> FastQueue c -> FastQueue c

fromList :: [c] -> FastQueue c

Sequence BSeq

Defined in Data.Sequence.BSeq.Internal

Methods

empty :: BSeq c

singleton :: c -> BSeq c

(><) :: BSeq c -> BSeq c -> BSeq c

viewl :: BSeq c -> ViewL BSeq c

viewr :: BSeq c -> ViewR BSeq c

(|>) :: BSeq c -> c -> BSeq c

(<|) :: c -> BSeq c -> BSeq c

fromList :: [c] -> BSeq c

Sequence q => Sequence (ToCatQueue q)

Defined in Data.Sequence.ToCatQueue.Internal

Methods

empty :: ToCatQueue q c

singleton :: c -> ToCatQueue q c

(><) :: ToCatQueue q c -> ToCatQueue q c -> ToCatQueue q c

viewl :: ToCatQueue q c -> ViewL (ToCatQueue q) c

viewr :: ToCatQueue q c -> ViewR (ToCatQueue q) c

(|>) :: ToCatQueue q c -> c -> ToCatQueue q c

(<|) :: c -> ToCatQueue q c -> ToCatQueue q c

fromList :: [c] -> ToCatQueue q c

data ViewL s c where

A view of the left end of a Sequence.

Constructors

EmptyL :: ViewL s c

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

Instances

(Show c, Show (s c)) => Show (ViewL s c)

Defined in Data.SequenceClass

Methods

showsPrec :: Int -> ViewL s c -> ShowS

show :: ViewL s c -> String

showList :: [ViewL s c] -> ShowS

data ViewR s c where

A view of the right end of a Sequence.

Constructors

EmptyR :: ViewR s c

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

Instances

(Show c, Show (s c)) => Show (ViewR s c)

Defined in Data.SequenceClass

Methods

showsPrec :: Int -> ViewR s c -> ShowS

show :: ViewR s c -> String

showList :: [ViewR s c] -> ShowS