[Haskell-cafe] Q about last&init

[Закиров Марат]

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 at 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 at froglogic.com
> www.froglogic.com - Multi-Platform GUI Testing
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe



-- 
Regards, Marat.
С уважением Марат.