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

[David Feuer]

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