I'm really close to making a second release of the compact-sequences
package (now with deques!), but I'd like to get a bit of help with module
naming/renaming now to try to avoid more painful name changes later, when
my package will hopefully have actual users. Currently, I have three "base"
implementations,
Data.CompactSequence.Stack.Internal
Data.CompactSequence.Queue.Internal
Data.CompactSequence.Deque.Internal
Each of these implements an abstract datatype representing a
stack/queue/deque of fixed-size arrays.
Additionally, I have "simple" implementations
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.
