[Haskell-cafe] Q about last&init
marat61 at gmail.com
Thu Jul 17 09:47:20 UTC 2014
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
С уважением Марат.
More information about the Haskell-Cafe