Oddly enough, I don't think anyone has attempted to answer the original questions, so I'll try to do so.

On Thu, Jul 17, 2014 at 5:35 PM, Закиров Марат <marat61@gmail.com> 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).
My questions are:
1) Is last function is something like "black box" written in C++ which
perform O(1)?

No. Haskell lists are equivalent to linked lists in C. If you know how to get the last element of a singly-linked list in O(1), you should be able to implement the same algorithm in Haskell (hint: it's not possible, but if you're more familiar with C maybe this will help you see why).

So I shouldn't even try to imagine some haskell O(1) equivalent.
2) Or will optimizer (llvm?) reduce init&last complexity to 1?

Generally no, for the same reasons.

3) Some people suggest to use sequences package, but still how do they
implement O(1) init&last sequences equivalent in haskell?

By using a different data structure. The finger tree data structure is designed to have O(1) access to either end. Access to elements near the middle is slower, but the worse case is some complicated log factor so it's still better than O(n).

I expect your C algorithm uses arrays, not linked lists. You could do exactly the same in Haskell (using mutable arrays) and then you would have the same algorithmic complexity as your C code. The big downside is that mutable array operations are in IO or ST.

John L.