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).