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!