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 <raabe@froglogic.com>:
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. С уважением Марат.