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

David Feuer david.feuer at gmail.com
Sun Dec 28 16:02:31 UTC 2014

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?

David Feuer

More information about the Haskell-Cafe mailing list