Data.Sequence interop

[treeowl]

Thanks to similarities in their representations, it should be quite easy to convert a simple Deque incrementally, node by node, into a Seq using Data.Sequence internals. This will produce a Seq whose nodes are all Node2. This should also work for a non-simple deque whose smallest arrays have sizes that are a power of two, and I think also for ones whose sizes are a power of 3. For other sizes, it will certainly be more complicated and I'm not sure how to work it.

Converting a Seq to a Deque incrementally is trickier. One approach would be to generate a Seq shape (with lots of internal sharing) that matches an extra-safe calculated Deque shape, using zipWith to rejigger the Seq to match the shape, and then building the Deque incrementally from that. Is that faster in practice than just using fromListN? We'd have to try it.