There are also purely functional worst case constant time (not amortized) queues out there. I'm on my phone right now, otherwise I'd try to hunt a package to link. Some of them are actually pretty simple and easy to remember how to write. Okasaki's Purely Functional Data Structures describes some.
To give an idea of how far it can go, there are even (much, much more complicated) worst case constant time doubled ended queues that support constant time concatenation (again, without amortization).
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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe