[Haskell-cafe] Q about last&init

Frerich Raabe raabe at froglogic.com
Thu Jul 17 09:39:32 UTC 2014

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

More information about the Haskell-Cafe mailing list