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