[Haskell-cafe] Q about last&init

[Tony Morris]

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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20140718/5fac3eb5/attachment.html>