On 17/07/2014, at 9:35 PM, Закиров Марат wrote:
I am teaching myself haskell. The first impression is very good... 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).
You can't. Not in *any* programming language. That's because lists are one of many possible implementations of the "sequence" concept, and they are optimised to support some operations at the expense of others. At the beginning level, you should think of all Haskell data structures as immutable; fixed; frozen; forever unchanged. You can't even remove an element from the front of a Haskell list, at all. All you can do is to forget about the original list and concentrate on its tail.
But the original haskell functions last and init are O(n).
Haskell lists are singly linked lists. Even by going to assembly code, you could not make these operations O(1) without *using a different data structure*.
My questions are: 1) Is last function is something like "black box" written in C++ which perform O(1)?
No.
2) Or will optimizer (llvm?) reduce init&last complexity to 1?
No.
3) Some people suggest to use sequences package, but still how do they implement O(1) init&last sequences equivalent in haskell?
Well, you could try reading Chris Okasaki's functional data
structures book.
There is a classic queue representation devised for Lisp
last century which represents