[Haskell-cafe] Q about last&init

[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" <
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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20140717/f5c9852b/attachment.html>