why is Data.Sequence.reverse O(n)?

Question

The docs say Data.Sequence.reverse is O(n). Couldn't a finite sequence type be "reversed" by setting a flag? (Effectively, which end to "start counting" from.)

Answer 1

Yes, it could.

However, this adds a small price to every lookup (one must first check the flag!), and the payoff only comes to users that use reverse a lot. This latter group was probably judged to be small. Since throwing the appropriate flag onto the type can be done client-side, it makes sense not to pay this price in the library for every use of every function. Instead, the programmer that intends to call reverse a lot is forced to make this performance tradeoff choice if they want it, which seems perfectly sensible to me.

Answer 2

If you have just one flag, you will have problems. Suppose I want

xs <> reverse xs

How could I calculate that? With just one flag, I'd have to perform an expensive reverse before appending. To actually do this right, you need more flags, spread around the tree. All around the tree. Every node in the tree needs to carry reversal information. This is definitely possible, but it's somewhat expensive. Even worse, every step of every operation has to manage the reversal flags appropriately, which is a bit of a nightmare for whoever has to write and maintain the code. This idea has been worked out in a paper somewhere (I don't remember which one) but it's no fun in practice.

If you have an algorithm that relies essentially on reversing, then you should use a custom sequence type with lots of flags, and include just the operations you need (if you're basing your type on Data.Sequence, you should probably steal one bit from each size field). But I don't think such algorithms are terrifically common.