Sequences
Haskell lists fill the role of singly linked-lists in Haskell. But what if we want doubly linked lists? Sequences fill this role quite well, and even give you better performance than what you'd expect for certain operations!
If you want to try some practice problems with sequences, take a look at our Data Structures In-Depth eBook!
What are Sequences good for?
Haskell's Sequence type is your go-to for double-ended queue operations. They are comparable to linked lists in other languages, with a few performance differences. In Haskell, they are similar to basic lists and vectors in many respects. With sequences, accessing either the front or back element is O(1)
time, similar to vectors. However unlike vectors, adding an element on either side is only O(log n)
, so sequences are much more easily mutable. The price of this is that arbitrary index accesses are logarithmic, rather than constant.
Breadth-first-search (BFS) is an example of a common algorithm where you should think about using a sequence.
What are Sequences not as good for?
Sequences have few major weaknesses. If O(1)
access to arbitrary elements is needed, then you'll want a hash set, hash map, array, or vector. But sequences even have reasonable logarithmic complexity for accessing items in the middle of the sequence (something traditional linked lists lack). Perhaps the other weakness to reckon with is that the syntax can be relatively complex compared to other data types.
Sequence Parameters and Constraints
Sequences have a single type parameter with no constraints.
How do I create a Sequence?
Like many types we've seen, sequences are initialized in three main ways.
empty :: Seq a
singleton :: a -> Seq a
fromList :: [a] -> Seq a
How do I get the size of a Sequence?
The Data.Sequence
module exposes a specific length
function that works in O(1)
time (separate from the slower Foldable
instance function).
length :: Seq a -> Int
How do I add elements to a Sequence?
There are two operators for adding elements to a sequence. The first operator (<|)
data-preserve-html-node="true" adds an element to the left (or "front") of the sequence. The second operator (|>)
adds the element to the right (or "back"). Both of these operators are O(log n)
.
(<|) :: a -> Seq a -> Seq a
(|>) :: Seq a -> a -> Seq a
Sequences are more flexible than lists in that you can also insert in the middle with reasonable efficiency. The insertAt
function will insert a new element at the given index in logarithmic time.
insertAt :: Int -> a -> Seq a -> Seq a
How do I access Sequence elements?
Accessing the elements of a sequence can actually be a little tricky at first. The most basic way would be to use the lookup function. This takes a numeric index and provides the element there, or else Nothing if it is out of range. This operation is logarithmic, but the implementation works out that you can actually use this to achieve constant time access to the front and back elements.
lookup :: Int -> Seq a -> Maybe a
However, the more canonical way to access the front and back elements is through patterns and views. With patterns, you can deconstruct a sequence in a similar way that the (:)
operator can deconstruct lists. The pattern operators look like the addition operators, except with colons in front:
>> let (a :<| seq2) = seq1
>> let (seq3 :|> b) = seq1
>> a
2
>> b
8
However, using patterns like this can throw an error if the sequence is empty. Thus you'll often use these patterns in function inputs or with case statements to account for the Empty
option.
Another way to get these elements is with view
functions. You can use viewl
to "view" the left side of the sequence. You'll again want to use a case statement, because you can either get EmptyL
, or the sequence destructured with the colon-carot operator.
doubleFirst :: Seq Int -> Int
doubleFirst seq = case viewL seq of
EmptyL -> 0
(a :< seq2) -> 2 * seq
Similarly, there is the viewr
function (view right), with the corresponding EmptyR
and (:>)
constructors.
addToLast :: Int -> Seq Int -> Int
addToLast x seq = case viewR seq of
EmptyR -> x
(seq2 :> y) -> x + y
Sequences can be confusing because of all the different access operators. So it's best to stick with one idea (like views) and go from there.
How do I delete items from a Sequence?
To remove elements from a sequence, you can, of course, use the remainder sequence left over after using the pattern or view function to destructure it. In this example, we can continue on if we like with seq2
as the original sequence with the first element removed.
doubleFirst :: Seq Int -> Int
doubleFirst seq = case viewL seq of
EmptyL -> 0
(a :< seq2) -> 2 * seq
However, there are also other functions we can use. As with lists, you can use drop
and take
to either remove elements from the front of a sequence or make a new sequence with only the first elements.
drop :: Int -> Seq a -> Seq a
take :: Int -> Seq a -> Seq a
How do I combine Sequences?
You can concatenate two sequences with the (><) data-preserve-html-node="true" operator.
(><) :: Seq a -> Seq a -> Seq a
This operator is a bit strange visually, since it is the reverse of the normal Semigroup
append operator. But it does the same thing!
Import Notes
Sequences have quite a few operators, and a couple are actually exposed through view
types. I also recommend using the qualifier as Seq
rather than as S
, since sets are more commonly used with as S
.
import Data.Sequence (Seq, ViewR(..), ViewL(..), (<|), (|>), (><))
import qualified Data.Sequence as Seq
Conclusion
If you want to learn about more data structures in Haskell, make sure to head back to the series page! If you've been reading these in order, you've only got one more remaining! Take a look at the last structure in our series: the Heap!