[Haskell-cafe] Q about last&init

[Закиров Марат]

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.
С уважением Марат.