Why Haskell need Data.Sequence when we already have list?

Question

List is a default data type of Haskell, why we still need Data.Sequence? Does Data.Seq mean something like a C style array that could be accessed randomly?

If yes, I would suppose this means Data.Sequence is stored with fixed memory buffer and thus, eager evaluated type. Just a guess, would you help to correct? Thanks.

Mahogany

Answer 1

The list type is a single-linked list. As such, prepend, head and tail are all O(1). However, ++ is O(n) in the size of the left-hand list.

By contrast, Data.Sequence is a balanced tree, so most operations on it are O(log n). That's not as fast as O(1), but it's potentially much faster O(n). In other words, you can join sequences faster than lists, but prepend is slightly slower.

Other than that, both data structures have quite similar properties; they're both lazy, they're both referentially transparent. (Sequence has to be finite though.)

See also the opening remarks from the documentation for Data.Sequence:

General purpose finite sequences. Apart from being finite and having strict operations, sequences also differ from lists in supporting a wider variety of operations efficiently.

The underlying algorithm is apparently described here. (In particular, includes a nice diagram.)

If you want arrays, you need to look at Data.Array and/or Data.Vector.

Allanadale

cons, snoc, head and last counterparts are all amortized O(1) for Data.Sequence. – Edea

Also, isn't Data.Sequence.Seq a finger tree? – Saucedo

"has to be finite" means that Seq is lazy in the elements but strict in the spine, right? – Scad

@Scad Yeah. Presumably to keep the tree branches balanced. – Allanadale

@chi: Also, Seq keeps the number of current elements in an Int. I guess that many Seq functions use that Int to automatically balance the tree. An infinite Seq would lead to interesting behaviour. – Saucedo

@chi, it's semantically strict in the spine, but the spine is lazy to achieve amortization and fast fmap, traverse, <*>, etc. – Parochial