Note: all of the options for playing with lists and queues and fingertrees come with trade-offs.

Finger trees give you O(log n) appends and random access, O(1) cons/uncons/snoc/unsnoc etc. but _cost you_ infinite lists.

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.

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.

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.

Difference lists give you an O(1) append, but alternating between inspection and construction can hit your asymptotics.

Lists are used by default because they cleanly extend to the infinite cases, anything more clever necessarily loses some of that power.

-Edward


On Fri, Jul 18, 2014 at 2:04 AM, Tony Morris <tmorris@tmorris.net> wrote:

data SnocList a = SnocList ([a] -> [a])

Inserts to the front and end in O(1).

On 17/07/2014 7:47 PM, "Закиров Марат" <marat61@gmail.com> wrote:
Thanks, but maybe I badly formulated my question. I'd like to insert
at the beginning of the list and remove from the tail both in O(1).


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



--
Regards, Marat.
С уважением Марат.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe