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 elementx
at the beginning of the sequencexs
..xs |> x
places the elementx
at the end of the sequencexs
.l >< r
combines the two sequencesl
andr
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 sequneces. 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.