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

[Tikhon Jelvis]

That explanation makes sense. It's probably worth adding a couple of
sentences to that effect to the package description. I haven't seen that
notation before, so I wasn't sure what it meant before you explained it
here.

On Tue, Sep 1, 2020 at 9:57 PM David Feuer <david.feuer at gmail.com> wrote:

> Yes, the n not being inside the O is the point. These structures hold n
> pointers in n words, plus a logarithmic term. Something like a linked list
> or Data.Sequence will hold n pointers in around c*n words, where c>1. For a
> list, c=3.
>
> On Wed, Sep 2, 2020, 12:26 AM ☂Josh Chia (謝任中) <joshchia at gmail.com> wrote:
>
>> 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.
>>>>
>>>> _______________________________________________
> 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/20200901/87db73fe/attachment.html>