[Haskell-cafe] Q about last&init

[Tom Ellis]

On Thu, Jul 17, 2014 at 01:35:58PM +0400, Закиров Марат 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)?
> So I shouldn't even try to imagine some haskell O(1) equivalent.
> 2) Or will optimizer (llvm?) reduce init&last complexity to 1?
> 3) Some people suggest to use sequences package, but still how do they
> implement O(1) init&last sequences equivalent in haskell?

I'm rather confused about your question.  If you want a Haskell data
structure that supports O(1) head, tail, init and last why not indeed use
Data.Sequence as has been suggested?  As for how it's implemented, it uses
the (very cool) fingertree datastructure.  See here for more details:

    http://hackage.haskell.org/package/containers-0.2.0.1/docs/Data-Sequence.html

Tom