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

[☂Josh Chia (謝任中)]

Isn't a stack O(1) time for push & pop and O(n) space? What is the tradeoff
being made here, where both space and time complexity increased?

Or, am I missing something about the meaning of "n + O(log)", where the 'n'
is not inside an 'O'. I don't really know what "n + O(log)" means exactly.

On Wed, Sep 2, 2020 at 12:21 PM David Feuer <david.feuer at gmail.com> wrote:

> 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/e3c16a3d/attachment.html>