compact-sequences
compact-sequences copied to clipboard
treeowl
Stacks and queues with compact representations
I really wanted to implement queues and deques by close analogy to Okasaki's implicit queue and implicit deque structures, with Hinze and Paterson's strictness modification to `cons` and `snoc` to...
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...
Stacks, at least, can support a rather more efficient (in constant factors) unordered merge than append. This is just plain addition of the numerical representations. We might as well offer...
It seems plausible that we could append queues in `O(min(m,n))` time rather than `O(m+n)` time. Can we append stacks faster too? Maybe `O(m)` time?
We don't actually *need* a lazy spine. An alternative representation for a queue, for example: ```haskell data N10 n a = N10 !(Array n a) !() data N11 n a...
We use different names to describe the same ideas in different `Internal` modules. Let's fix that.
Hi. I came here from your message https://mail.haskell.org/pipermail/haskell-cafe/2020-August/132593.html Could you please add (in the README) a few words on this data structure(s) and their use cases? When should I prefer...
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...
`O(n log n)` is pretty wretched. One simple option is to use `fromListN` with `length`. It's kind of nasty though, and may or may not be faster in practice.
We can probably borrow some from the `Data.Sequence` benchmarks. We'll certainly want to compare run-time performance to other stack/queue/deque implementations.