Re: [Haskell-cafe] Q about last&init

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@froglogic.com www.froglogic.com - Multi-Platform GUI Testing