Re: [Haskell-cafe] Q about last&init

Jake It would be great if you give some examples when find your notebook :) And link to the book about pure functional data structures which you are talking about. Also If some "haskell.org" maintainers are here I'd like to recommend them to pay more attention to optimality/performance questions. Because almost first question which is apeared in head of standart C/C++ programmer is "Do I get same perfomance?" (even if he do not need it). Maybe some simple and cool PDF tutorial which describes why haskell could be as fast as others will be great to have. 2014-07-17 17:04 GMT+04:00 Jake McArthur :

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 Jul 17, 2014 7:44 AM, "Tom Ellis" wrote:

...

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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

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