Should we switch to nonempty queues?

[treeowl]

The Queue type is currently a bit of a mess, in that it doesn't have quite the right amortized bounds. In particular, if someone does something like

q = ((((s <> Empty) <> Empty) <|> Empty) <|> Empty) <|> Empty

and then evaluates viewl q in multiple futures, each of those futures will walk the Emptys to discard them.

We can't give it the right bounds without breaking laziness, a problem which has bitten us rather badly before.

What we can do is replace the catenable queues with lazy catenable non-empty queues. These don't seem to suffer from that problem, so they form a nice clean ADT to built atop. There are a couple pain points:

1. viewl ends up with a different type, which doesn't match the sequence class we currently use. Not a big deal.
2. linkAll may get a bit more complicated. I don't know how bad it'll look.
3. We'll have to define empty :: SeqT a differently. Specifically, we'll need to write

   empty = SeqT (singleton (pure Empty))

   where Empty here is the empty ViewT. This will generally be less efficient to handle than a dedicated Empty constructor in cases where a computation does nothing other than fail. For example, if someone writes m <|> (if x then empty else ...) <|> n then currently we can immediately skip over the Empty when we reach it. With the simplified version, we'll end up with a separate empty for each underlying monad, which contains a (trivial) computation we must "run" to figure out that there's nothing to do. I'm guessing the theoretical cleanliness isn't worth the performance impact, but it depends on the code people want to write.