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 <[email protected]> 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 [email protected]. > 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 [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/CAGnRm4JS6_1Mn-0k4NJ%3DYr6Hs_v%3DhZjgGDrufdZ2rC53puDaYg%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
