thorsten-michael
What is the idomatic way to process tree data structures in Elixir?
I have a database table that holds a ton of rows which define a hierarchy by an attribute called parent_id.
Solution 1: Huge Map
A Tree module that transforms the rows into a map. For each row, it contains the mapping froim the id attribute of each row to something like %{item: row, children: [children_ids...], parent: parent_id}. Also, a list of root_ids is stored, for rows without a parent_id. So, the structure returned looks like:
%{ nodes: %{
1 => %{item: %{...}, children: [2, 3], parent: nil},
2 => %{item: %{...}, children: [], parent: 1},
3 => %{item: %{...}, children: [4], parent: 1},
...,
roots: [1]}
The module has functions to get the root nodes and to fetch nodes by their id from the map. The same way, it fetches the children for a given node.
Solution 2: Using Agents
Instead of a huge map, I tried to use an Agent for every node in the tree. Its a process holding quite the same data as above, but it is easier to set up the structure from the initial list of rows.
%{ roots: [#PID<0.122.0>] }
and an Agents with their state like
%{item: %{}, children: [PID#<0.123.0>, PID#<0.124.0>], parent: nil} # PID#<0.122.0>
%{item: %{}, children: [], parent: PID#<0.122.0>} # PID#<0.123.0>
I can even map a function over a tree to transform all the nodes while keeping the structure. But here I can shoot in my foot: If I just map a function f that transforms the agents item state, I get the behaviour of a mutable data structure.
So I did not transform the state of the agent, but created a new one with the transformed item and the parent and children properly set up.
Where Next?
Trending in Questions
Other Trending Topics
Latest on Elixir Forum
Sponsor Spotlight
Error tracking, logs, APM, uptime and cron monitoring in one dev-friendly platform. Find and fix problems before your users notice.
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #library
- #deployment
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #elixirconf
- #channels
- #exunit
- #discussion
- #code-sync
- #podcasts
- #javascript
- #onsite
- #dialyzer
- #docker
- #authentication
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #ecto-query
- #elixirconf-us
- #ai
- #blog-post
- #elixir-ls
- #phoenix_html
- #iex
- #graphql
- #genstage
- #websockets
- #supervisor
- #advent-of-code
- #distillery
- #processes
- #api
- #forms
- #metaprogramming
- #hex
- #security
Our Sponsors
Build Elixir applications with speed and confidence.
Supporting innovation across the BEAM ecosystem.
We build reliable cloud platforms for business-critical systems.
Catch errors, track performance, monitor hosts and more.
Error tracking, logs, uptime, and Just Enough APM. Built for developers.
Practical resources that improve the lives of professional developers.
Producing high quality Elixir screencasts since 2017.
**Building the future of software with AI, trust, and human connection.**
The team behind Membrane, Popcorn, LiveDebugger. Available for hire.
Courses that'll move you from confusion to "Aha, now I get it!"
First Post!- Show Best Posts
- Show All (oldest first)
- Show All (newest first)
href
You could use the erlang’s digraph module, which uses an ETS table as the underlying storage. An acyclic digraph is the same as a “tree”.
Most Liked
sasajuric
To be completely honest I’ve tried this approach myself way back when, in my Erlang days. That’s why I’m confident it’s not a good approach
It’s hard to say, because the problem is vaguely described, but I think concurrent processing should be possible with a flat huge map (though can’t say if it’s worth it for your case). However, if you need to process from bottom to top, it might be better to organize the map as child to parent relationships and the list of leaves.
You also suggest that the amount of data is huge. That might lead to a large active heap, and cause some larger GC pauses in the owner process, as I briefly discussed here. If that’s the case,
:digraphmight be a good fit, because it’s based on ETS. Or otherwise, your hand-rolled ETS table. This might also simplify concurrent processing.I definitely don’t advise agents (or processes). It’s going to be 2kb overhead per node (and you suggest there are a lot of them). It’s also going to involve a lot of extra message passing and scheduler overhead. With some careful work, you should be able to achieve whatever you want without agents. A large map or a nested data structure would be functional solutions, while ETS is an optimization for the cases when you have a frequently changing large active working set.
benwilson512
Is it a directed acyclic graph or a tree? That is, does any node ever have more than one parent? If it’s a true tree then my recommendation is to just have a big nested structure of maps, it ends up working pretty well.
If it’s actually a DAG then something like
:digraphis likely to work best. Going the agent route would be a great example of something that The Erlangelist - To spawn, or not to spawn? argues against.Qqwy
The way your database is set up, there is nothing preventing cycles from happening. Also, when you want to query all nodes back up the tree, or the subtree starting at a certain node, you will require
Ndatabase queries (I think? Maybe there is some archaic black magic to follow all the parent IDs in SQL directly, but it isn’t going to be pretty).What I have seen other libraries, most notably the Ruby gem ‘Ancestry’, do, is to store a list of IDs of the path back up the tree. This way, cycles are prevented, and you can also select a subtree at once.
As for how to represent them in memory: Hex.PM contains Arbor, zipper_tree, Garph, and quite possibly some more packages that can help with this (disclaimer: I have not inspected them in detail). The basic idea of a ‘rose tree’ like the one you are attempting to build, is to have a node, which has a list of children (each of these being a node again). In Haskell parlance:
data Tree a = Node a [Tree a]In Elixir, this would be something like
Traversing these kind of trees is simple: Given a node, do something with the value, and then call it recursively for all the children (this is pre-order traversal, post-order traversal would be to first go to the children, and then the current node). An implementation of this can be seen in
Macro.prewalkandMacro.postwalk: Yes, quoted elixir code is also a tree: an Abstract Syntax Tree (Although it is of course not wrapped in a stuct).Last Post!
user20230119
Is there anything better than digraph or libgraph to traverse tree structs?