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

Question

The docs say Data.Sequence.reverse is O (n). Could you change the type of the final sequence by setting the flag? (In fact, ending with "start countdown" with.)

Answer 1

If you have only one flag, you will have problems. Suppose i want

 xs <> reverse xs 

How could I calculate this? With just one flag, I would have to do an expensive reverse before adding. To actually do it right, you need more flags located around the tree. Everything around the tree. Each node in the tree needs to carry information about the opposite. It is definitely possible, but it is somewhat expensive. Even worse, each step of each operation must properly manage the U-flag, which is a nightmare for those who need to write and maintain code. This idea was developed somewhere in paper (I don’t remember which one), but in practice it is not funny.

If you have an algorithm that is mainly based on the opposite, then you should use a custom sequence type with a lot of flags and include only those operations that you need (if you use your type on Data.Sequence , you should probably steal one bit from each size field). But I do not think that such algorithms are terribly common.

Answer 2

Yes it is possible.

However, this adds a small price to each search (check the flag first!), And the win only applies to users who use reverse lot. This last group was probably small. Since throwing the appropriate flag on a type can be performed on the client side, it makes sense not to pay this price in the library for each use of each function. Instead, a programmer who intends to call reverse lot is forced to make this choice of performance compromise if he wants to, which seems perfectly reasonable to me.

Answer 3

Well, you can determine

 data S a = S { forward :: Seq a , backward :: Seq a } 

and then implement all operations with an invariant that

 forall a :: Type, s :: S a : reverse (forward s) == backward s . 

This doubles the cost of each, but gives a constant reverse time.

Answer 4

I think it can be done in O(1) if concatenation >< allows concatenation xs >< reversed ys without penalty (some kind of hack is required in the structure of the fingers).

Looking at Data.Sequence , all operations have an inverse analogue (for example, takeWhileL ~ takeWhileR ) or take O(n) (or worse, for example zip take O(min(n1,n2)) , then seq1 n1<n2 , etc. .), except for the operation >< .

In any case, xs >< ys will take O(min(|xs|,|ys|)) as the worst case (two out of four possible cases). In practice, this is slightly better than O(n) (normalization to a unique direction and vice versa is required).

Then the question arises:

Can xs >< reversed ys be better than O(min(|xs|,|ys|)) ?

(ideally O(log(min(|xs|,|ys|))) )

Of course, if you do not use the >< operation, the reverse operation takes O(1) (for example, using a flag to check when using the left or right copy).

On the other hand, if the performance of concatenating inverse sequences is critical, there may be some other optimal structure, or you might consider using the @ d8d0d65b3f7cf42 strategy .