Copyright	(c) Atze van der Ploeg 2014
License	BSD-style
Maintainer	atzeus@gmail.org
Stability	provisional
Portability	portable
Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.SequenceClass

Description

A type class for sequences.

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

Synopsis

class (Foldable s, Functor s) => Sequence s where
- empty :: s c
- singleton :: c -> s c
- (><) :: s c -> s c -> s c
- viewl :: s c -> ViewL s c
- viewr :: s c -> ViewR s c
- (|>) :: s c -> c -> s c
- (<|) :: c -> s c -> s c
- fromList :: [c] -> s c
data ViewL s c where
- EmptyL :: ViewL s c
- (:<) :: c -> s c -> ViewL s c
data ViewR s c where
- EmptyR :: ViewR s c
- (:>) :: s c -> c -> ViewR s c

Documentation

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

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,

foldMap f is a monoid morphism:

```
foldMap f mempty = mempty
```

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

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 Source #

singleton :: c -> s c Source #

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

Append two sequences

viewl :: s c -> ViewL s c Source #

View a sequence from the left

viewr :: s c -> ViewR s c Source #

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 Source #

Append a single element to the right

Default definition:

l |> r = l >< singleton r

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

Append a single element to the left

Default definition:

l <| r = singleton l >< r

fromList :: [c] -> s c Source #

Convert a list to a sequence

Default definition:

fromList = foldl' (|>) empty

Instances

Instances details

Sequence [] Source #
Instance details Defined in Data.SequenceClass Methods empty :: [c] Source # singleton :: c -> [c] Source # (><) :: [c] -> [c] -> [c] Source # viewl :: [c] -> ViewL [] c Source # viewr :: [c] -> ViewR [] c Source # (\|>) :: [c] -> c -> [c] Source # (<\|) :: c -> [c] -> [c] Source # fromList :: [c] -> [c] Source #
Sequence Seq Source #
Instance details Defined in Data.SequenceClass Methods empty :: Seq c Source # singleton :: c -> Seq c Source # (><) :: Seq c -> Seq c -> Seq c Source # viewl :: Seq c -> ViewL Seq c Source # viewr :: Seq c -> ViewR Seq c Source # (\|>) :: Seq c -> c -> Seq c Source # (<\|) :: c -> Seq c -> Seq c Source # fromList :: [c] -> Seq c Source #
Sequence Queue Source #
Instance details Defined in Data.Sequence.Queue.Internal Methods empty :: Queue c Source # singleton :: c -> Queue c Source # (><) :: Queue c -> Queue c -> Queue c Source # viewl :: Queue c -> ViewL Queue c Source # viewr :: Queue c -> ViewR Queue c Source # (\|>) :: Queue c -> c -> Queue c Source # (<\|) :: c -> Queue c -> Queue c Source # fromList :: [c] -> Queue c Source #
Sequence FastQueue Source #
Instance details Defined in Data.Sequence.FastQueue.Internal Methods empty :: FastQueue c Source # singleton :: c -> FastQueue c Source # (><) :: FastQueue c -> FastQueue c -> FastQueue c Source # viewl :: FastQueue c -> ViewL FastQueue c Source # viewr :: FastQueue c -> ViewR FastQueue c Source # (\|>) :: FastQueue c -> c -> FastQueue c Source # (<\|) :: c -> FastQueue c -> FastQueue c Source # fromList :: [c] -> FastQueue c Source #
Sequence BSeq Source #
Instance details Defined in Data.Sequence.BSeq.Internal Methods empty :: BSeq c Source # singleton :: c -> BSeq c Source # (><) :: BSeq c -> BSeq c -> BSeq c Source # viewl :: BSeq c -> ViewL BSeq c Source # viewr :: BSeq c -> ViewR BSeq c Source # (\|>) :: BSeq c -> c -> BSeq c Source # (<\|) :: c -> BSeq c -> BSeq c Source # fromList :: [c] -> BSeq c Source #
Sequence q => Sequence (ToCatQueue q) Source #
Instance details Defined in Data.Sequence.ToCatQueue.Internal Methods empty :: ToCatQueue q c Source # singleton :: c -> ToCatQueue q c Source # (><) :: ToCatQueue q c -> ToCatQueue q c -> ToCatQueue q c Source # viewl :: ToCatQueue q c -> ViewL (ToCatQueue q) c Source # viewr :: ToCatQueue q c -> ViewR (ToCatQueue q) c Source # (\|>) :: ToCatQueue q c -> c -> ToCatQueue q c Source # (<\|) :: c -> ToCatQueue q c -> ToCatQueue q c Source # fromList :: [c] -> ToCatQueue q c Source #

data ViewL s c where Source #

A view of the left end of a Sequence.

Constructors

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

Instances

Instances details

(Show c, Show (s c)) => Show (ViewL s c) Source #
Instance details 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 Source #

A view of the right end of a Sequence.

Constructors

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

Instances

Instances details

(Show c, Show (s c)) => Show (ViewR s c) Source #
Instance details Defined in Data.SequenceClass Methods showsPrec :: Int -> ViewR s c -> ShowS # show :: ViewR s c -> String # showList :: [ViewR s c] -> ShowS #