[Haskell-cafe] Q about last&init

[John Lato]

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 at 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20140718/fb371463/attachment.html>