[Haskell-cafe] Q about last&init

[Frerich Raabe]

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