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.htm... Tom