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 funcitonality:

-- 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.