search

treeowl / compact-sequences

Stacks and queues with compact representations
BSD 3-Clause "New" or "Revised" License
16 stars 4 forks source link

Write non-simple versions #3

Open treeowl opened 4 years ago

treeowl commented 4 years ago

Dealing with arrays of 1, 2, or even 4 elements has a proportionally unreasonable amount of overhead. We really should build something simpler above the main mechanism to streamline the top of the structure. That could look like

data F a = F1 a | F2 a a | ...
data R a = R0 | R1 a | ...
data Queue a = Empty | Full !(F a) (Q.Queue N a) !(R a)

or maybe even represent the front and rear as linked lists with their (bounded) sizes. Benchmarking will determine what works best.

The tricky part is the stupid part: arrange for the first level of the main mechanism to have an arbitrary positive array size. This will require some fiddling with how we type-tag arrays for size.

treeowl commented 4 years ago

@sjakobi, would you be interested in giving this a go? My best guess:

  1. Move the Size stuff from Array to its own module.
  2. Switch from DataKinds to plain old-school style, so we can add as many base types as we want to supplement Mul1.
  3. Experiment with a bunch of different things at the top and see what works best.

I'm likely to do some cleanups to make this all easier in the next few days. We also really need a benchmark suite first.

sjakobi commented 4 years ago

@sjakobi, would you be interested in giving this a go?

Unfortunately, I'm unlikely to find time for this.

treeowl commented 4 years ago

I realized something yesterday. We can actually cram a full O(log n) elements into the 0th node if we want, and I imagine we might!