Make zipWith faster

Make `zipWith` build its result with the structure of its first
argument, splitting up its second argument as it goes. This allows
fast random access to the elements of the results immediately,
without having to build large portions of the structure. It also
seems to be slightly faster than the old implementation when the
entire result is used, presumably by avoiding rebalancing costs.
I believe most of this code will also help implement a fast
`(<*>)`.

Use the same approach to implement `zipWith3` and `zipWith4`.

Clean up a couple warnings.

Many thanks to Carter Schonwald for suggesting that I use the
structure of the first sequence to structure the result, and for
helping me come up with the splitTraverse approach.

Benchmarks:

Zipping two 100000 element lists and extracting the 50000th element
takes about 11.4ms with the new implementation, as opposed to 88ms with
the old. Zipping two 10000 element sequences and forcing the result to
normal form takes 4.0ms now rather than 19.7ms. The indexing gains show
up for even very short sequences, but the new implementation really
starts to look good once the size gets to around 1000--presumably it
handles cache effects better than the old one. Note that the naive
approach of converting sequences to lists, zipping them, and then
converting back, actually works very well for forcing short sequences to
normal form, even better than the new implementation. But it starts to
lose a lot of ground by the time the size gets to around 10000, and its
performance on the indexing tests is bad.
Add zip benchmarks
Specialize splitTraverse; strictify pair splitting

Explicitly specialize `splitTraverse` functions to the necessary types.
This has no immediate performance impact, but makes it clearer what the
functions are about. Make splitting pairs a bit stricter; we don't need
that much laziness.
Add comments explaining the splitting traversal

Why it's a good idea, how it works, and what the benchmarks
say.
Nix the Splittable class; add fromFunction

Write mapWithIndex using
a hand-unboxed mapWithIndex#.

Make `split` strict, and add an internal strict `splitAt'`. This
helps `zipWith` a little.
Simplify zipWith3 and zipWith4 to reduce code size

The performance impact isn't worth the code blowup.

Also, fix a bug in `fromFunction`.
Revert the fromFunction shallowing

I don't actually know whether we want it shallower or "safer".
Make `fromFunction` easier to read.
Rename strictness tests to match other test names.
Use pre-evaluated sequences in benchmarks.
Update URL of the fingertree paper.
Add test for fromFunction.
Fix warnings.
Make sure the helper functions are inlined.
Move the closing parent to a separate line.
Remove unsafeCoerce, use only coerce on GHC 7.8 and later.

Also, move the conditional compilation to a local where definition.

On my GHC 7.6.3, there is no heap allocation in the cmm in fromFunction
for the (Elem . f) closure, so there is no penalty of not using `coerce`.
Nevertheless, GHC 7.8.3 and GHC-head (15 Dec 2014) do heap-allocate
trivial closure for (Elem . f), so `coerce` helps.

Back to GHC 7.6.3, I found that the following does not allocate in
GHC 7.6.3:
  newtype Elem a = Elem a
  elemMap :: Int -> (Int -> b) -> [Elem b]
  elemMap s f = go (Elem . f) 0
   where go :: (Int -> b) -> Int -> [b]
         go f i | i >= s = []
                | otherwise = f i : go f (i+1)
Nevertheless, the following does heap-allocate trivial closure for f:
  newtype Elem a = Elem a
  elemMap :: [Int] -> (Int -> b) -> [Elem b]
  elemMap xs f = go (Elem . f) xs
   where go :: (Int -> b) -> [Int] -> [b]
         go f [] = []
         go f (x:xs) = f x : go f xs
I am not sure what the difference is, but the current fromFunction
does not allocate too (on 7.6.3).
Add simple fromFunction benchmarks.
Use a top-down version of fromList

Ross Paterson came up with a version of fromList that avoids the
tree rebuilding inherent in the `(|>)`-based approach. This
version is somewhat strictified and rearranged. It reduces
allocation substantially over the old version. Mutator time goes
down too, but for some reason GC time rises to match it.
Remove trailing whitespace.
Use coerce for [a]->[Elem a] convertion in fromList.
Comment various conditional imports.