Removing items in a tree/recursive data structure

Hey, I’m writing a little game that has to render a tree (the data structure, not the plant :wink: ). Each node of the tree should be rendered as a Box. Each box has some text in it, a button to remove the node from the tree (including any children), and a button to add another child node.

Now, I’ve tried to implement this using the approach with Tree.indexedMap outlined in this post. I’m using the zwilias/elm-rosetree package for this.

The problem I’m having now is: How could I delete an element from the tree? I think the approach with indexedMap isn’t working for this, since I can’t remove elements from the tree this way, only update the labels. I think I’d have to use the tree zipper for this, but I’m having trouble even rendering the tree this way.

Could someone show me an example for how to do something like this?

Thank you!

I’ve not tried this, but as far as I understand, your idea is correct to use a Tree.Zipper. But you only need it for actually removing the node, you can store a normal Tree in your model.

When you want to delete a node, the first thing you do is convert the Tree into a Tree.Zipper using, e.g., fromTree. This gives you functions to walk along the tree.

If each node has a unique label, you can use findFromRoot. If the label may appear multiple times, you’ll have to walk along the tree towards the correct node using findNext and firstChild. (If you need the latter case, please ask. I don’t have more time right now, but someone will likely help you.)

After you’ve found the correct node, you can use removeTree to remove it.

At the end you can go back to a normal Tree using toTree, which will give you the entire tree, regardless which node is focused (as specified in the function’s documentation).

So in the simplest case, it’s

import Tree.Zipper as Zipper

let newTree = oldTree
      |> Zipper.fromTree
      |> Zipper.findFromRoot (\candidateLabel -> candidateLabel == labelIAmLookingFor)
      |> Zipper.removeTree
      |> Zipper.toTree
-- use newTree, which no longer has the node with the label `labelIAmLookingFor`.

Hey, thank you for your help! This is already helping a lot.

Right now, my labels are not unique. But I guess could work around that. My labels are records, so I could just add a unique ID to them. I tried doing this already by adding a unique, incrementing Int to the record, but that opens up new problems, how do I make sure this Int always increments when I create a new instance of my label? I tried having something like an currentAutoIncrement Int in my model, and every time I create an instance of my label, I also update it. But somehow that felt very weird/wrong to me.

Also, another question, isn’t the solution you proposed insanely expensive, performance- and memory-wise? Because as far as I understand, we’re creating a copy of the entire tree structure (stored in the Zipper), and then another one when converting it back into a tree, right? Or does Elm somehow avoid this with persistent data structures or something else under the hood?

I’m quite new to functional programming, so thank you for helping me learn and pointing me in the right direction.

Don’t worry about performance. I have large trees (dozens of trees with hundreds of nodes) that are built dynamically during the view (based on filters and other parameters), and I’m animating them. Meaning this is all getting calculated every animation frame. I’m also using elm-rosetree and performance is fine. Functional data structures rarely “create copy of the entire ___ structure”. Any data structure in a pure language can safely reuse as much of an old data structure as it needs, knowing it can’t be mutated outside of it’s control.

Very interesting, thank you for the suggestion! May I ask what you’re working on?

DM me on Elm Slack and I’d be happy to discuss.

Hello, I’m the author of Canopy, which exposes a remove function for removing nodes in a rose tree. The main problem you’ll generally encounter with targeting nodes in a tree reliably is if they’re not unique, so I suggest ensuring you have distinct unique values to be safe.

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.