Could you elaborate on what the package does? The description is "Stacks,
queues, and deques that take n + O(log n) space at the cost of having
amortized O(log n) time complexity for basic operations." But why is it a
'cost' to have O(log n) instead of O(n) cost for basic operations on
list-like structures (such as insert and delete presumably)? So, I didn't
understand what the package is for.
Do you mean "take amortized O(log n) time for basic operations at the cost
of n + O(log n) space"? Or is it something else I didn't imagine?
On Wed, Sep 2, 2020 at 4:17 AM David Feuer
I am pleased to release the second version of the compact-sequences package, now with deques!
Changes: * Add deques. * Change operator precedence. * Add a test suite. Thanks to David Himmelstrup for setting up the test and CI framework. * Clean up internals somewhat. * Add a proof of amortized bounds for the stack implementation. Thanks, Li-Yao Xia.
There are still plenty of things to work on, and help is always welcome.
David Feuer _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.