Optimize <* for sequences

[treeowl]

We should be able to optimize <* for sequences to get more sharing within subtrees and go faster. Basically, we want to use <$ to make subtrees instead of <$>.

We want to maintain the incremental bounds. In particular, (xs <* ys) `index` k should produce a result in logarithmic time.

[treeowl]

This looks trickier than I thought! I suspect doing this well will require rather more work than <* did.

[treeowl]

@oisdk, I haven't been able to give this enough sustained attention to get it done. Do you think you can have a look? It has to be a sort of mash-up of things from aptyMiddle with things from applicativeTree. Instead of actually rigidifying the second tree, we must instead track the sizes the tree components should have (or something like that). The function we build going down (corresponding to map23) has to produce 2-3 trees with maximal sharing. I expect the function corresponding to aptyMiddle will have a type similar to

beforeMiddle
  :: c
  -> c
  -> (a -> c)
  -> FingerTree (Elem a)
  -> Int
  -> Int
  -> FingerTree (Node c)

but that could be wrong.

[oisdk]

Yeah I can take a look!

[treeowl]

I'd expect m <* n to take O(|m| log |n|) time and space. It currently takes a full O(|m||n|).