Would love this to be available. Was this ever explored in more depth? On Friday, June 16, 2017 at 5:20:28 PM UTC-4 Wiebe-Marten Wijnja wrote:
> The 'indexed data structure' that is often used now in many projects is > the built-in (Hash)Map that the newer versions of Erlang/OTP provide. The > keys of a map kan be seen as a poor-man's pointers if you want to have > (amortized) constant field access and update behaviour data structure. This > is for instance the approach I took in the implementation of sparse > vectors/matrices/tensors in the Tensor library ( > https://github.com/qqwy/tensor). The nice thing about offloading most of > the work to a built-in data structure is that the handling of this data > structure happens in a compiled piece of code, that is furthermore allowed > to 'cheat' the functional rules (as long as the final outcome remains pure). > > It is worth noting that many of Erlang's built-in tools are still of the > time that Erlang did not have map-support, which means that there are now > more options available to us to implement certain data structures > differently. > (That being said, maps are definitely slower than plain tuples at least up > to a certain size and depending on the kind of structure you want to build > and the guarantees it should have.) Benchmarking will show us what happens > in practice. > > > I'd love there to be an Elixir-variant of Haskell's Data.Sequence (which > is built on top of 2-3 trees and has O(1) element appending and prepending, > and O(min(log(length(seq1), length(seq1))) concatenation) and Patrizia > trees+sets. > On a related note, I've lately done a little bit of work to write out the > different efficient functional FIFO queues (and deques) that Okasaki wrote > about, both the trivial amortized O(1) variant (which is similar to what > :queue does now) and the less trivial hard real-time O(1) variant. I plan > to benchmark these against :queue and each other, to see for what input > which version works the best. > > > Data structures really are fun! :D > > > On Thursday, June 1, 2017 at 12:09:25 PM UTC+2, Robert Virding wrote: >> >> I am just curious: what is your use case? >> >> If you look in my luerl system, https://github.com/rvirding/luerl, you >> will see a module ttdict.erl which uses 2-3 trees. These are basically the >> same as red-black trees. Well, actually, rb trees are sort 2-3 trees but >> only using binary nodes. I have not done any serious speed comparison but >> my guess is they should be about as fast s rb trees. An easy way to handle >> the slowness of size would be to carry around an explicit size field. the >> 2-3 trees and rb trees have the same interface as dict. >> >> For fun I also implemented aa trees and sets, which Arne Andersson trees. >> >> Data structures are fun. >> >> Robert >> >> P.S. I use 23-trees in luerl as maps are missing one very important >> function needed for implementing Lua and that is to be able to efficiently >> step through a tree. I need a 'first' function which returns the first >> key-value pair and then a 'next' which returns the next pair after a given >> key. Order is unimportant but I need guarantees that I will see all pairs. >> >> On Sunday, 28 May 2017 09:19:59 UTC+2, Ricky Han wrote: >>> >>> Hi José, >>> >>> I posted an update on the benchmark here [1]. >>> >>> [1] https://github.com/elixir-lang/elixir/issues/6161 >>> >>> Best, >>> Ricky >>> >>> On Wednesday, May 24, 2017 at 7:20:58 AM UTC-4, José Valim wrote: >>>> >>>> Thanks for the proposal Ricky Han! >>>> >>>> It is also worth mentioning the red black trees library from Robert >>>> Virding: https://github.com/rvirding/rb >>>> >>>> While having a library is already great for the ecosystem, we can >>>> consider this being added as part of Elixir given Elixir doesn't have an >>>> indexed data structure besides tuples (which are expensive to transform). >>>> >>>> However, there is a lot of work to do before we are able to fully >>>> evaluate it: >>>> >>>> 1. As you said, it needs documentation. You mention the 1990 look and >>>> feel from the Erlang libraries but they are at least *documented* >>>> >>>> 2. We need to validate the claims it is fast and space efficient. Have >>>> you benchmarked it against gb_trees and gb_sets and measured >>>> insertion/retrieval/deletion times as well as memory usage? For example, >>>> your implementation uses maps for nodes and using tuples will likely be >>>> much more efficient >>>> >>>> The core team has discussed adding indexed data structures multiple >>>> times in the past but we haven't found something that feels right. >>>> >>>> >>>> >>>> >>>> *José Valim* >>>> www.plataformatec.com.br >>>> Skype: jv.ptec >>>> Founder and Director of R&D >>>> >>>> On Wed, May 24, 2017 at 11:10 AM, Ricky Han <ricky...@gmail.com> wrote: >>>> >>>>> The most important data structure elixir is missing - *sorted, >>>>> ordered sets and maps*. Say what? Elixir only has non-ordered sets. >>>>> The default(recommended) map is HashMap whereas Haskell Data.Map is >>>>> backed >>>>> by binary tree. JVM, stdlib, .NET are treemaps too. This is strange >>>>> because >>>>> there is 0 penalty for functional language to use trees.(sidenode: Redis >>>>> uses skip lists which is bad for immutability). >>>>> >>>>> These are actually several solutions out there: >>>>> >>>>> :orddict, :ordset, :gb_sets, :gb_trees >>>>> >>>>> :orddict and :ordset are very bad as they are backed by lists and have >>>>> linear time complexity. >>>>> >>>>> :gb_sets and :gb_trees are performant because they are backed by AA >>>>> trees. However, annoyingly they don't track size of subtrees which means >>>>> can't be indexed unless converted to list(expensive). >>>>> >>>>> Here is why this would be better than all the existing solutions and >>>>> should be integrated into elixir stdlib. >>>>> >>>>> 1. Being able to index keys means we can it can replace Redis sorted >>>>> set completely. With ZRANK, ZRANGE abilities >>>>> 2. All the other languages have it >>>>> 3. Proves to be fast and space efficient >>>>> 4. First class citizen so no need to use inferior Erlang library with >>>>> limited functionalities and 1990s documentation >>>>> >>>>> I find sorted sets and maps very useful in other languages(especially >>>>> ruby). So like a good hacker I ported red black tree from Haskell[1] >>>>> Currently, both data structures are functional but documentations are few >>>>> and far between. >>>>> >>>>> [1] https://github.com/rickyhan/rbtree >>>>> >>>>> -- >>>>> You received this message because you are subscribed to the Google >>>>> Groups "elixir-lang-core" group. >>>>> To unsubscribe from this group and stop receiving emails from it, send >>>>> an email to elixir-lang-co...@googlegroups.com. >>>>> To view this discussion on the web visit >>>>> https://groups.google.com/d/msgid/elixir-lang-core/5b22966b-3f82-4446-b494-ec06d892991c%40googlegroups.com >>>>> >>>>> <https://groups.google.com/d/msgid/elixir-lang-core/5b22966b-3f82-4446-b494-ec06d892991c%40googlegroups.com?utm_medium=email&utm_source=footer> >>>>> . >>>>> For more options, visit https://groups.google.com/d/optout. >>>>> >>>> >>>> -- You received this message because you are subscribed to the Google Groups "elixir-lang-core" group. To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-core+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/969ac152-d57b-402c-86ee-9833493410aen%40googlegroups.com.
