[Haskell-cafe] Is it possible to zip sequences any faster?

containers-0.5.6 has a new implementation of zipWith in Data.Sequence that, like the old one, offers O(n) zipping, but unlike the old one offers immediate O((log(min{i,n-i}))^2) access to the elements, where i is the requested index. I haven't been able to think of a way to bring that down from polylogarithmic to logarithmic. The difficulty is that t splits one of the sequences repeatedly, so reaching an element the first time is kind of like pushing a snow shovel all the way down the driveway, rather than throwing snow off to either side. Does anyone have an idea for doing it better, or a good argument that it can't be done? Thanks, David Feuer