[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 <jake.mcarthur at gmail.com>:
> 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"
> <tom-lists-haskell-cafe-2013 at jaguarpaw.co.uk> 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.html
>>
>> Tom
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



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