Does Data.Vector replace Data.Sequence?

问题:

I've been quite a fan of Data.Sequence. But as I've been learning about Data.Vector, it seems that it can do everything Data.Sequence can, but better, plus it can do more stuff. Should we be deprecating Data.Sequence and preaching Data.Vector? Are there any good reasons for using Data.Sequence over Data.Vector?

回答1:

None of these data structures can replace the other; Data.Sequence and Data.Vector are actually at diametrically opposite ends of the data structures available for representing sequences.

• Data.Vector is a contiguous array of elements. This means small memory footprint and O(1) lookup but terrible mutation, concatenation and copying (O(n) each). (Mutation can be O(1) if you drop persistence.)
• Data.Sequence on the other hand is a purely functional tree. This means higher memory usage and less locality, but it supports fast access and mutation O(log n) and awesome concatenation O(log(min(n1,n2))) and copying.

The choice of data structure really depends on the task at hand here.

• Processing large streams of elements in linear fashion or with random lookup is best done with Data.Vector.
• If you need to split, concatenate and change your elements a lot, use Data.Sequence.

回答2:

Sharing a prefix seems like something Seq is better at than Vector. snoc on Vector is O(n).