[Haskell-cafe] Q about last&init

[Tom Ellis]

On Thu, Jul 17, 2014 at 03:34:17PM +0400, Закиров Марат wrote:
> Tom said that finger tree gives us O(1) on removing last element, but
> in haskell all data is persistent.
> So function should return list as is minus last element. How it could
> be O(1)? This is just blows my mind...

Sounds like magic doesn't it :)

> My hypothesis is that somehow compiler reduces creating of a new list
> to just adding or removing one element. If it is not so.
> Then even ':' which is just adding to list head would be an O(n)
> operation just because it should return brand new list with one elem
> added. Or maybe functional approach uses pretty much different
> complexity metric, there copying of some structure "list" for example
> is just O(1)? If so then Q about compiler is still exists.

But no, there's no compiler magic, just an amazing datastructure.  The
caveat is that the complexity is amortised, not guaranteed for every
operation.  Have a look at the paper if you learn about how it works.  It's
linked from the Hackage docs.

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

Tom