Data.CompactSequence.Stack.Simple

Data.CompactSequence.Queue.Simple

Data.CompactSequence.Deque.Simple

that just use the base implementations with arrays of size 1. These are great as a proof of concept and for testing, but I expect their performance to be quite bad [1]. To solve the problem, I need to write separate datatypes to handle the top of the structure (the first k elements of a stack, or a prefix and suffix of a queue or deque). There are various different approaches to this, with various trade-offs and tuning factors. The first I'd like to implement, for stacks and queues, would look exactly like the base implementations but with elements instead of arrays in the first node. What might I call these? Another option would be to just use linked lists with various length bounds. Yet another would use stacks that look like

data Stack6 a = One a | Two a a | ... | Six a a a a a a

for various size bounds. But I have no idea how to name any of these things.

A second issue: I may eventually want to add alternative base implementations to support O(log n) `length` and significantly more efficient (but still O(n)) splitting, appending, and indexing operations. How might *those* work into the name situation?

Finally, I'll eventually want to offer support for unpacked data, probably via backpack. That will involve base implementations that work with ByteArray rather than SmallArray. Names, names, I hate names!

1. In the first node of the data structure, each sequence element is represented as a pointer to a SmallArray of one element. Yuck. The situation improves considerably further in, with the array size doubling in successive nodes.

2. For deques, where code size is already a matter of some concern, this approach seems likely to exacerbate the issue, but a simpler variant should work well enough.