[Haskell-cafe] Looking for help finishing off Data.Sequence <*> optimization

David Feuer david.feuer at gmail.com
Thu Dec 4 19:53:33 UTC 2014


With help from Carter Schonwald, I've put together a framework to optimize
both the zip functions and the (<*>) method for sequences, as shown in
https://github.com/haskell/containers/pull/84

The zip optimization is complete, but I'm getting lost in modular
arithmetic in the optimization of fs<*>xs. The remaining challenge is to
come up with an efficiently splittable representation of

fmap (\f -> fmap f xs) fs

and a way to split it. The first part, coming up with a representation that
(theoretically) does the job, is easy:

data CP a b = SingleCP a (Seq b) | FullCP Int Int (Seq a) (Seq b)

The SingleCP constructor represents [f] * xs; the FullCP one holds fs, xs,
and the start and end points within the original sequence (this
representation was half-heartedly suggested by Cale Gibbard, who thinks
probably no one uses the Applicative instance for Seq anyway).

The trouble is that actually calculating things properly with these numbers
is rather confusing for me; I keep going off by one in one way or another,
and producing unreadable code. Can anyone help?

David Feuer
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20141204/aa90649e/attachment.html>


More information about the Haskell-Cafe mailing list