[Haskell-cafe] Q about last&init

[Edward Kmett]

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 at 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 at 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 at 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 at froglogic.com
>> > www.froglogic.com - Multi-Platform GUI Testing
>> > _______________________________________________
>> > Haskell-Cafe mailing list
>> > Haskell-Cafe at haskell.org
>> > http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>>
>>
>> --
>> Regards, Marat.
>> С уважением Марат.
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20140720/faf3ff92/attachment.html>