Question to all,
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...
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.
2014-07-17 14:07 GMT+04:00 Frerich Raabe
On 2014-07-17 12:02, Tom Ellis wrote:
On Thu, Jul 17, 2014 at 11:55:31AM +0200, Frerich Raabe wrote:
On 2014-07-17 11:47, Закиров Марат wrote:
Thanks, but maybe I badly formulated my question. I'd like to insert at the beginning of the list and remove from the tail both in O(1).
...then you might find DList interesting, see
http://hackage.haskell.org/package/dlist-0.5/docs/Data-DList.html
How does DList support O(1) removal from the tail?
Oops, sorry, it doesn't. I misread the mail.
-- Frerich Raabe - raabe@froglogic.com www.froglogic.com - Multi-Platform GUI Testing _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
-- Regards, Marat. С уважением Марат.