Splitting may be too slow about containers HOT 9 CLOSED

This is exactly why I suggested the slicing approach (another name change, but slicing is better as subsetting, as you have said) -- because slicing can be done quickly (in amortized constant time per level).

Nevertheless, the problem is, that after we have shaved some amount of the FingerTree, the Nodes are becomming deeper, so lookup in the tree being shaved is taking more time O(depth of current Nodes), which will be probably something like O(levels that were traversed to get to this spot). Well -- that would actually work, because for a node at level i, the lookup time would be O(i) to get that deep, O(i) to perform the slicing and O(i) to perform lookup in the Nodes of the tree being shaved, which have O(i) bound. This is all based on the fact that when we traversed to the depth d of the "original" tree (not being sliced), we could have only traversed O(d) leves in the tree being sliced, which I think is true.

from containers.

There's still a tradeoff with memory behavior, which seems to me a bigger
potential nastiness, but you might be able to convince me.

from containers.

I've thought about this a bit more, and I'm increasingly skeptical about our chances of doing much better. There's an inherent challenge that finger trees having the same number of elements can have different structures at all scales. It might (I'm not sure) be possible to get better constant factors with slicing, but I'm pretty sure you won't get better than polylogarithmic immediate indexing.

from containers.

Well it can hardly be better than polylogarithmic :-) But I believe we can make it log(i) instead of log(i)^2, where i is the lesser distance of an indexed element from either end of the sequence.

It is true that the structure can be different, but there are still both upper and lower bounds, which guarantee that if an element is in depth d in one structure of size n, it is in depth \Theta(d) in any structure of size n.

What I am not 100% sure is whether the constant factors of the slicing factor would be better -- the slicing checks will take some time. So it may happen that the splitting approach would work better for sequences of depth <= 3 for example.

from containers.

I still don't see how you're going to be able to use slicing to get all the
way to O(log(min{i,n-i})) without breaking the O(n) total. Explain? One
other constant-factor cost of slicing is the memory to hold the slice
constructors—it's not huge, but it's there.

from containers.

Oh, you are right that the straightforward O(log(min{i,n-i})) will be O(n log n) in total, because the deep _Node_s are not split and will therefore cause the O(n log n). In order to get O(n), one would have to split the deep _Node_s too, and I am not sure that even that would guarantee O(n).

If someone ever has desire to try this, we will see the numbers :-)

from containers.

Well, you can try the naive way very easily using

zipWith' f xs ys = mapWithIndex (\i x -> f x $ ys `index` i) xs

from containers.

It is true that the structure can be different, but there are still both upper and lower bounds, which guarantee that if an element is in depth d in one structure of size n, it is in depth \Theta(d) in any structure of size n.

This is what keeps me wondering if there's some kind of magic trick I'm missing, but every time I try to think of a way around this, something seems to get in the way. It's driving me nuts.

from containers.

I don't think this is going anywhere anytime soon. It probably can't get too much better.

from containers.