[Haskell-cafe] [ANN] compact-sequences-

David Feuer david.feuer at gmail.com
Wed Sep 2 04:21:36 UTC 2020

Typical stacks, queues, and deques are designed to have O(1) operations.
These ones experiment in a different direction.

On Wed, Sep 2, 2020, 12:19 AM ☂Josh Chia (謝任中) <joshchia at gmail.com> wrote:

> 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 <david.feuer at gmail.com> wrote:
>> 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20200902/bb08b410/attachment.html>

More information about the Haskell-Cafe mailing list