# Sequences¶

Sequences allow you to store a finite number of sequential elements, providing
fast access to both ends of the sequence as well as efficient concatenation. The
`containers`

package provides the Data.Sequence module which
defines the `Seq`

data type.

## Short Example¶

The following GHCi session shows some of the basic sequence functionality:

```
-- Import the Seq type and operators for combining sequences unqualified.
-- Import the rest of the Sequence module qualified.
import Data.Sequence (Seq(..), (<|), (|>), (><))
import qualified Data.Sequence as Seq
let nums = Seq.fromList [1, 2, 3]
-- Put numbers on the front and back.
0 <| nums
> fromList [0,1,2,3]
nums |> 4
> fromList [1,2,3,4]
-- Reverse a sequence
Seq.reverse (Seq.fromList [0, 1, 2])
> fromList [2,1,0]
-- Put two sequences together.
(Seq.fromList [-2, -1]) >< nums
> fromList [-2,-1,0,1,2]
-- Check if a sequence is empty and check the length.
Seq.null nums
> False
Seq.length nums
> 3
-- Lookup an element at a certain index (since version 0.4.8).
Seq.lookup 2 nums
> Just 3
-- Or the unsafe version, you MUST check length beforehand.
Seq.index 2 nums
> 3
-- Map a function over a sequence (can use fmap or the infix function <$>).
fmap show nums
> fromList ["0","1","2"]
show <$> nums
> fromList ["0","1","2"]
-- Fold a sequence into a summary value.
foldr (+) 0 (Seq.fromList [0, 1, 2])
> 3
```

Tip

You can use the OverloadedLists
extension so you don’t need to write `fromList [1, 2, 3]`

everywhere.
Instead you can just write `[1, 2, 3]`

and if the function is
expecting a sequence it will be converted automatically! The code here
will continue to use `fromList`

for clarity.

## Importing Sequence¶

When using `Sequence`

in a Haskell source file you should always use a
`qualified`

import becasue it exports names that clash with the standard
Prelude (you can import the type constructor and some operators on their own
though!).

```
import Data.Sequence (Seq, (<|), (|>), (><))
import qualified Data.Sequence as Seq
```

## Common API Functions¶

Note

`fromList [some,sequence,elements]`

is how a `Seq`

is printed.

### Construction and Conversion¶

#### Create an empty sequence¶

```
Seq.empty :: Seq a
Seq.empty = ...
```

empty creates a sequence with zero elements.

```
Seq.empty
> fromList []
```

#### Create a sequence with one element (singleton)¶

```
Seq.singleton :: a -> Seq a
Seq.singleton x = ...
```

singleton creates a sequence with the single
element `x`

in it.

```
Seq.singleton "containers"
> fromList ["containers"]
Seq.singleton 1
> fromList [1]
```

#### Create a sequence with the same element repeated¶

```
Seq.replicate :: Int -> a -> Seq a
Seq.replicate n x = ...
```

replicate creates a sequence with same element
`x`

repeated `n`

times.

```
Seq.replicate 0 "hi"
> fromList []
Seq.replicate 3 "hi"
> fromList ["hi","hi","hi"]
```

#### Create a sequence from a list¶

```
Seq.fromList :: [a] -> Seq a
Seq.FromList xs = ...
```

fromList creates a sequence containing the
elements of the list `xs`

. Sequences allow duplicate so all elements will be
included in the order given.

```
Seq.fromList ["base", "containers", "QuickCheck"]
> fromList ["base","containers","QuickCheck"]
Seq.fromList [0, 1, 1, 2, 3, 1]
> fromList [0,1,1,2,3,1]
```

#### Adding to an existing sequence¶

```
(<|) :: a -> Seq a -> Seq a
x <| xs = ...
(|>) :: Seq a -> a -> Seq a
xs |> x = ...
(><) :: Seq a -> Seq a -> Seq a
l >< r = ...
```

`x <| xs`

places the element`x`

at the beginning of the sequence`xs`

.`xs |> x`

places the element`x`

at the end of the sequence`xs`

.`l >< r`

combines the two sequences`l`

and`r`

together.

#### Create a list from a sequence¶

```
import qualified Data.Foldable as Foldable
Foldable.toList :: Seq a -> [a]
```

There is no `toList`

function in the Sequence module since it can be
easily implemented with a
fold using `Seq`

’s Foldable instance.

```
import qualified Data.Foldable as Foldable
Foldable.toList (Seq.fromList ["base", "containers", "QuickCheck"])
> ["base","containers","QuickCheck"]
```

### Pattern Matching¶

*Since 0.5.10*

Just like you can pattern match (aka. destructure) a list `[a]`

, you can do
the same with sequences. Let’s first look at how we do this with lists:

```
case [1, 2, 3] of
[] -> "empty list"
(x:xs) -> "first:" ++ show x ++ " rest:" ++ show xs
> "first:1 rest:[2,3]"
```

Let’s do the same thing with sequences!

```
-- Imports the patterns to match on.
import Data.Sequence (Seq (Empty, (:<|), (:|>)))
case Seq.fromList [1, 2, 3] of
Empty -> "empty sequence"
x :<| xs -> "first:" ++ x ++ " rest:" ++ show xs
> "first:1 rest:fromList [2,3]"
```

Note

You can’t copy/paste this into GHCi because it’s multiple lines.

You can also take an element off the end:

```
-- Imports the patterns to match on.
import Data.Sequence (Seq (Empty, (:<|), (:|>)))
case Seq.fromList [1, 2, 3] of
Empty -> "empty sequence"
xs :|> x -> "last element:" ++ show x
> "last element:3"
```

### Querying¶

#### Check if a sequence is empty¶

```
Seq.null :: Seq a -> Bool
Seq.null xs = ...
```

null returns `True`

if the sequence `xs`

is
empty, and `False`

otherwise.

```
Seq.null Seq.empty
> True
Seq.null (Seq.fromList [1, 2, 3])
> False
```

#### The length/size of a sequence¶

```
Seq.length :: Seq a -> Int
Seq.length xs = ...
```

length returns the length of the sequence `xs`

.

```
Seq.length Seq.empty
> 0
Seq.length (Seq.fromList [1, 2, 3])
> 3
```

#### The element at a given index¶

```
Seq.lookup :: Int -> Seq a -> Maybe a
Seq.lookup n xs = ...
Seq.!? :: Seq a -> Int -> Maybe a
xs !? n = ...
```

lookup returns the element at the position `n`

,
or `Nothing`

if the index is out of bounds. !?
is simply a flipped version of `lookup`

.

Note

You may need to import `!?`

qualified if you’re using a `Map`

,
`IntMap`

, or `Vector`

in the same file because they all export the
same operator.

```
Seq.index :: Seq a -> Int -> a
Seq.index xs n = ...
```

index returns the element at the given position. It throws a runtime error if the index is out of bounds.

Tip

Use `lookup`

/`!?`

whenever you can and explicitly deal with the
`Nothing`

case.

```
(Seq.fromList ["base", "containers"]) Seq.!? 0
> Just "base"
Seq.index 0 (Seq.fromList ["base", "containers"])
> "base"
(Seq.fromList ["base", "containers"]) Seq.!? 2
> Nothing
Seq.index (Seq.fromList ["base", "containers"]) 2
> "*** Exception: index out of bounds
```

When working with functions that return a `Maybe v`

, use a case expression to
deal with the `Just`

or `Nothing`

value:

```
do
let firstDependency = Seq.fromList ["base", "containers"] !? 0
case firstDependency of
Nothing -> print "Whoops! No dependencies!"
Just dep -> print "The first dependency is " ++ dep
```

### Modification¶

#### Inserting an element¶

```
Seq.insertAt :: Int -> a -> Seq a -> Seq a
Seq.insertAt i x xs = ...
```

insertAt inserts `x`

into `xs`

at the index
`i`

, shifting the rest of the sequence over. If `i`

is out of range then
`x`

will be inserted at the beginning or the end of the sequence as
appropriate.

```
Seq.insertAt 0 "idris" (Seq.fromList ["haskell", "rust"])
> fromList ["idris","haskell","rust"]
Seq.insertAt (-10) "idris" (Seq.fromList ["haskell", "rust"])
> fromList ["idris","haskell","rust"]
Seq.insertAt 10 "idris" (Seq.fromList ["haskell", "rust"])
> fromList ["haskell","rust","idris"]
```

See also Adding to an existing sequence.

#### Delete an element¶

```
Seq.deleteAt :: Int -> Seq a -> Seq a
Seq.deleteAt i xs = ...
```

deleteAt removes the element of the sequence at
index `i`

. If the index is out of bounds then the original sequence is
returned.

```
Seq.deleteAt 0 (Seq.fromList [0, 1, 2])
> fromList [1,2]
Seq.deleteAt 10 (Seq.fromList [0, 1, 2])
> fromList [0,1,2]
```

#### Replace an element¶

```
Seq.update :: Int -> a -> Seq a -> Seq a
Seq.update i x xs = ...
```

update replaces the element at position `i`

in
the sequence with `x`

. If the index is out of bounds then the original
sequence is returned.

```
Seq.update 0 "hello" (Seq.fromList ["hi", "world", "!"])
> fromList ["hello","world","!"]
Seq.update 3 "OUTOFBOUNDS" (Seq.fromList ["hi", "world", "!"])
> fromList ["hi","world","!"]
```

#### Adjust/modify an element¶

*Since version 0.5.8*

```
adjust' :: forall a. (a -> a) -> Int -> Seq a -> Seq a
adjust' f i xs = ...
```

adjust’ updates the element at position `i`

in
the sequence by applying the function `f`

to the existing element. If the
index is out of bounds then the original sequence is returned.

```
Seq.adjust' (*10) 0 (Seq.fromList [1, 2, 3])
> fromList [10,2,3]
Seq.adjust' (*10) 3 (Seq.fromList [1, 2, 3])
> fromList [1,2,3]
```

Note

If you’re using an older version of containers which only has `adjust`

, be
careful because it can lead to poor performance and space leaks (see
adjust docs).

#### Modifying all elements¶

```
fmap :: (a -> b) -> Seq a -> Seq b
fmap f xs = ...
Seq.mapWithIndex :: (Int -> a -> b) -> Seq a -> Seq b
Seq.mapWithIndex f xs = ...
```

fmap transform each element of the sequence with
the function `f`

. `fmap`

is provided by the Functor instance for sequences and
can also be written infix using the `<$>`

operator.

mapWithIndex allows you to do a similar transformation but gives you the index that each element is at.

```
fmap (*10) (Seq.fromList [1, 2, 3])
-- = fromList [1*10, 2*10, 3*10]
> fromList [10,20,30]
(*10) <$> Seq.fromList [1, 2, 3]
-- = fromList [1*10, 2*10, 3*10]
> fromList [10,20,30]
let myMapFunc index val = index * val
Seq.mapWithIndex myMapFunc (Seq.fromList [1, 2, 3])
-- = fromList [0*1, 1*2, 2*3]
> fromList [0,2,6]
```

### Sorting¶

```
Seq.sort :: Ord a => Seq a -> Seq a
Seq.sort xs = ...
```

sort the sequence `xs`

using the `Ord`

instance.

```
Seq.sort (Seq.fromList ["x", "a", "c", "b"])
> fromList ["a","b","c","x"]
```

### Subsequences¶

#### Take¶

```
Seq.take :: Int -> Seq a -> Seq a
Seq.take n xs = ...
```

take returns the first `n`

elements of the
sequence `xs`

. If the length of `xs`

is less than `n`

then all elements
are returned.

```
Seq.take 0 (Seq.fromList [1, 2, 3])
> fromList []
Seq.take 2 (Seq.fromList [1, 2, 3])
> fromList [1,2]
Seq.take 5 (Seq.fromList [1, 2, 3])
> fromList [1,2,3]
```

#### Drop¶

```
Seq.drop :: Int -> Seq a -> Seq a
Seq.drop n xs = ...
```

drop the first `n`

elements of the sequence
`xs`

. If the length of `xs`

is less than `n`

then an empty sequence is
returned.

```
Seq.drop 0 (Seq.fromList [1, 2, 3])
> fromList [1,2,3]
Seq.drop 2 (Seq.fromList [1, 2, 3])
> fromList [3]
Seq.drop 5 (Seq.fromList [1, 2, 3])
> fromList []
```

#### Chunks¶

```
Seq.chunksOf :: Int -> Seq a -> Seq (Seq a)
Seq.chunksOf k xs = ...
```

chunksOf splits the sequence `xs`

into chunks
of size `k`

. If the length of the sequence is not evenly divisible by `k`

then the last chunk will have less than `k`

elements.

Warning

`k`

can only be `0`

when the sequence is empty, otherwise a runtime
error is thrown.

```
-- A chunk size of 0 can ONLY be given for an empty sequence.
Seq.chunksOf 0 Seq.empty
> fromList []
Seq.chunksOf 1 (Seq.fromList [1, 2, 3])
> fromList [fromList [1],fromList [2],fromList [3]]
Seq.chunksOf 2 (Seq.fromList [1, 2, 3])
> fromList [fromList [1,2],fromList [3]]
Seq.chunksOf 5 (Seq.fromList [1, 2, 3])
> fromList [fromList [1,2,3]]
```

### Folding¶

```
foldr :: (a -> b -> b) -> b -> Seq a -> b
foldr f init xs = ...
Seq.foldrWithIndex :: (Int -> a -> b -> b) -> b -> Seq a -> b
Seq.foldrWithIndex f init xs = ...
```

foldr collapses the sequence into a summary
value by repeatedly applying `f`

. `foldr`

is provided by the Foldable instance for
sequences. foldWithIndex gives you access to the
position in the sequence when transforming each element.

```
foldr (+) 0 (Seq.fromList [1, 2, 3])
-- = (1 + (2 + (3 + 0)))
> 6
let myFoldFunction index val accum = (index * val) + accum
Seq.foldrWithIndex myFoldFunction 0 (Seq.fromList [1, 2, 3])
-- = ((0*1) + ((1*2) + ((2*3) + 0)))
> 8
```

## Serialization¶

The best way to serialize and deserialize sequences is to use one of the many libraries which already support serializing sequences. binary, cereal, and store are some common libraries that people use.

## Performance¶

The API docs are annotated with the Big-*O* complexities of each of the sequence
operations. For benchmarks see the haskell-perf/sequences page.

## Looking for more?¶

Didn’t find what you’re looking for? This tutorial only covered the most common sequence functions, for a full list of functions see the Data.Sequence API documentation.