<div dir="ltr">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.<br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Sep 1, 2020 at 9:57 PM David Feuer <<a href="mailto:david.feuer@gmail.com">david.feuer@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="auto">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.</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Sep 2, 2020, 12:26 AM ☂Josh Chia (謝任中) <<a href="mailto:joshchia@gmail.com" target="_blank">joshchia@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">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?<div><br></div><div>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.</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Sep 2, 2020 at 12:21 PM David Feuer <<a href="mailto:david.feuer@gmail.com" rel="noreferrer" target="_blank">david.feuer@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="auto">Typical stacks, queues, and deques are designed to have O(1) operations. These ones experiment in a different direction.</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Sep 2, 2020, 12:19 AM ☂Josh Chia (謝任中) <<a href="mailto:joshchia@gmail.com" rel="noreferrer" target="_blank">joshchia@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">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.<div><br></div><div>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?<br><div><br></div><div><br></div></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Sep 2, 2020 at 4:17 AM David Feuer <<a href="mailto:david.feuer@gmail.com" rel="noreferrer noreferrer" target="_blank">david.feuer@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">I am pleased to release the second version of the compact-sequences<br>
package, now with deques!<br>
<br>
Changes:<br>
* Add deques.<br>
* Change operator precedence.<br>
* Add a test suite. Thanks to David Himmelstrup for setting up the<br>
test and CI framework.<br>
* Clean up internals somewhat.<br>
* Add a proof of amortized bounds for the stack implementation.<br>
Thanks, Li-Yao Xia.<br>
<br>
There are still plenty of things to work on, and help is always welcome.<br>
<br>
David Feuer<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer noreferrer noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
Only members subscribed via the mailman list are allowed to post.</blockquote></div>
</blockquote></div>
</blockquote></div>
</blockquote></div>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
Only members subscribed via the mailman list are allowed to post.</blockquote></div>