Tillmann Rendel rendel at informatik.uni-marburg.de
Thu Jul 17 22:59:52 UTC 2014

```Hi,

Закиров Марат wrote:
> Is last function is something like "black box" written in C++ which
> perform O(1)?

This is not really about Haskell vs. C++, but about how the data
structures look like in memory. If you have single-linked list in memory:

root --> 1 --> 2 --> ... --> n

And you only have a pointer to 1, you cannot even access the n'th
element without following n pointers. So last for a single-linked list
is necessarily O(n), independently of language.

Let's look at adding an element to the front of the list. We start with
this:

old --> 1 --> 2 --> ... --> n

and we want to end up with this:

new --> 0 --> 1 --> 2 --> ... -> n

This looks bad at first, because it seems that we have to copy the
original list before putting the 0 in front. The trick is to just use
the old list in the new list without copying it:

old --> 1 --> 2 --> ... --> n
^
|
new --> 0

In C++, this trick would be dangerous: If one part of the code would use
the old pointer to modify the list, this modification would be visible
to some other part of the code using the new pointer. In Haskell, no
code can modify the list once it is created. (Note that from the point
of view of 1, nothing changed, because the 1 cannot see the 0). So this
problem doesn't arise and we can freely share most the list between old
and new. All we did was allocate 1 heap cell for the new list element,
so this operation is O(1).

But what if we want to append to the end of the list? We start with this:

old --> 1 --> 2 --> ... --> n

And we want to end up with this:

new --> 1 --> 2 --> ... --> n --> n + 1

We cannot even reach the n without doing O(n) operations. Even worse, we
cannot reuse any of the old list, because the difference between the old
and the new list is visible to every heap cell. So we have to allocate n
+ 1 new heap cells.

> Or will optimizer (llvm?) reduce init&last complexity to 1?

No.

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

They use a different data structure that's carefully designed to have
just the right pointer where and when you need it.

The API documentation of Data.Sequence mentions the complexity of each
function.