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.

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.