[Haskell-cafe] Q about last&init

[Tillmann Rendel]

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.

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

If you want to learn how that works, you can follow the source links on 
the API documentation or reads the research paper they link to.

   Tillmann