<div dir="ltr">Note: all of the options for playing with lists and queues and fingertrees come with trade-offs.<div><br></div><div>Finger trees give you O(log n) appends and random access, O(1) cons/uncons/snoc/unsnoc etc. but _cost you_ infinite lists.</div>
<div><br></div><div>Realtime queues give you the O(1) uncons/snoc. There are catenable output restricted deques that can preserve those and can upgrade you to O(1) append, but we've lost unsnoc and random access along the way.</div>
<div><br></div><div>Skew binary random access lists give you O(log n) drop and random access and O(1) cons/uncons, but lose the infinite lists, etc.</div><div><br></div><div>Tarjan and Mihaescu's deque may get you back worst-case bounds on more of the, but we still lose O(log n) random access and infinite lists.</div>
<div><br></div><div>Difference lists give you an O(1) append, but alternating between inspection and construction can hit your asymptotics.</div><div><br></div><div>Lists are used by default because they cleanly extend to the infinite cases, anything more clever necessarily loses some of that power.</div>
<div><br></div><div>-Edward</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, Jul 18, 2014 at 2:04 AM, Tony Morris <span dir="ltr"><<a href="mailto:tmorris@tmorris.net" target="_blank">tmorris@tmorris.net</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><p dir="ltr">data SnocList a = SnocList ([a] -> [a])</p>
<p dir="ltr">Inserts to the front and end in O(1).</p><div class="HOEnZb"><div class="h5">
<div class="gmail_quote">On 17/07/2014 7:47 PM, "Закиров Марат" <<a href="mailto:marat61@gmail.com" target="_blank">marat61@gmail.com</a>> wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

Thanks, but maybe I badly formulated my question. I'd like to insert<br>
at the beginning of the list and remove from the tail both in O(1).<br>
<br>
<br>
2014-07-17 13:39 GMT+04:00 Frerich Raabe <<a href="mailto:raabe@froglogic.com" target="_blank">raabe@froglogic.com</a>>:<br>
> On 2014-07-17 11:35, Закиров Марат wrote:<br>
>><br>
>> I am teaching myself haskell. The first impression is very good.<br>
>> But phrase "haskell is polynomially reducible" is making me sad :(.<br>
>> Anyway I am trying to backport my algorithm written in C. The key to<br>
>> performance is to have ability to remove element from the end of a<br>
>> list in O(1).<br>
>> But the original haskell functions last and init are O(n).<br>
><br>
><br>
> On viable option might be to adjust the algorithm such that instead of<br>
> appending to the list, it prepends (which is O(1) in Haskell), i.e.<br>
> you manage the list in reverse and only actually reverse it to the<br>
> original order when needed (e.g. when printing).<br>
><br>
> --<br>
> Frerich Raabe - <a href="mailto:raabe@froglogic.com" target="_blank">raabe@froglogic.com</a><br>
> <a href="http://www.froglogic.com" target="_blank">www.froglogic.com</a> - Multi-Platform GUI Testing<br>
> _______________________________________________<br>
> Haskell-Cafe mailing list<br>
> <a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
> <a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
<br>
<br>
<br>
--<br>
Regards, Marat.<br>
С уважением Марат.<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</blockquote></div>
</div></div><br>_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br></div>