Update a node in a tree

[Y0hy0h]

I was trying to learn more Elm with a toy project, but I ran into an conceptual issue. This is the first time that I have a problem in Elm that I know how to solve in other languages, but not at all in Elm.

The project is a tournament planner (not too great code, yet) that will let you play against your friends. Of course, a central part is the tournament tree, which I implemented quite naturally as a recursive tree structure.

The issue is when I want to update a node. My intuitive approach (which is valid in e. g. Vue) was to build the view recursively and register click listeners on each node that would tell update what node to update. Unfortunately, this is not possible in Elm, as I would need to pass around a pointer to that node.

I know that I can associate an ID to each node, but that would complicate the model and provoke additional calculations for walking through the tree. I am very confident that Elm has an approach to this problem that is elegant and performant, but that I just got at it from the wrong angle.
I’m perfectly ok to completely change the model, if there is a structure that helps with this problem.

What is the most elegant and efficient way in Elm to (build and) update a recursive tree when an event on one of the node happens?

[joelq]

TL;DR

• You probably want some Tree.indexedMap
• Here’s an example

Lists

Let’s look at an easier case. In a list where elements didn’t have ids, you might do this using List.indexedMap:

view list =
  ul [] <| List.indexedMap viewItem list

viewItem idx item =
  li [ onClick (ClickedItem idx)] [ text item ]

and in the update

update msg list =
  case msg of
    ClickedItem id -> List.indexedMap (updateClickedItem id) list

updateClickedItem id idx item =
  if idx == id then doSomething else item

Trees

It turns out that list are trees (with a branching factor of 1). We can define many common list operations for trees too, like Tree.map and Tree.indexedMap. This package does exactly that. There are a lot of handy functions in that tree package, I recommend reading through the docs for it .

What is the most elegant and efficient way in Elm to (build and) update a recursive tree when an event on one of the node happens?

Here’s an example using an indexedMap approach.

[Y0hy0h]

Thank you so much, especially for the example. It’s exactly my use case.

I will have a closer look at it later, but I’m confident that I have no further questions. Thanks again!

[rtfeldman]

As it happens, this is one of the topics covered in depth in Chapter 7 of Elm in Action.

It’s currently in the editor’s hands, though.

[joelq]

Nice! I didn’t realize you covered trees in your book

[evancz]

I heard a couple people talking about this, so I have been telling folks about a type like this:

type TreeExplorer
  = BranchL TreeExplorer Tree
  | BranchR Tree TreeExplorer
  | Focus Whatever Tree Tree

type Tree
  = Branch Tree Tree
  | Empty

You have a guarantee that a TreeExplorer always has a Focus. You can write functions to move the Focus up and down through the tree, through different branches. You probably will put additional data in all these nodes. (I did not get a chance to look through your code.)

Everyone uses different variations though, for whatever their case is. One case was a math formula editor, Richard’s case was a file viewer, another colleague wanted an infinitely nesting list where you could keep going one level deeper for details, etc. I’ll probably be talking about this a bit at Elm Europe in the context of making full use of union types!

Anyway, does that help you (or someone else here) get going in the right direction?

[evancz]

Oh, and the debugger in elm-reactor may be a good example of wanting to handle events recursively. I think I use Html.map at each level with some type like:

type Toggle
  = Index Int Toggle
  | Field String Toggle
  | Toggle

From there you write a toggle function that recursively goes through your structure, and you have a guarantee that it will match because the event is processed synchronously!

Not sure exactly what the type should be in your case, but I find that it’s easiest to just customize the idea for my scenario.

[rupert]

It may also be worth looking into tree zippers to handle this:

http://package.elm-lang.org/packages/tomjkidd/elm-multiway-tree-zipper/1.10.2/MultiwayTree

In my Msg type I have:

type Msg
    = ...
    | ToggleOpen (Zipper ContentNode)

So as you walk the tree to render the UI, you set up event handlers with the Zipper positioned at the node being rendered. The Zipper itself is then passed with the event, and you use that to update the tree, then pull it inside out by walking back to the root, and you get the complete new updated tree.

There is a potential stale data problem with this approach though - the Zipper captures the current state, and that may become stale if multiple events occur fast enough that the UI is not refreshed with the new state in between. In practice I have never seen that happen but I also did not use this approach in situations where it seemed likely to happen.

[rupert]

It turns out that list are trees (with a branching factor of 1). We can define many common list operations for trees too, like Tree.map and Tree.indexedMap .

Will this also suffer from a stale data problem? If one event changes the structure of the tree, a subsequent event might have its index map to the wrong place in the tree? That is, if the second event picks up a stale index.

[mattpiz]

Will this also suffer from a stale data problem? If one event changes the structure of the tree, a subsequent event might have its index map to the wrong place in the tree? That is, if the second event picks up a stale index.

As long as you don’t change the tree structure, like in the example that just close or open items, there is no risk. The risks come when the tree structure is modified by the events (removal, insertions, …) because then, as you suggested, the ids generated by the indexedMap might not correspond.

[rupert]

So I guess ways that you can ensure it works might be:

Put unique ids on the nodes of the tree that do not change, so you can check that things did not move.

OR

Keep some sort of version counter, and ensure that events get tagged with the version. Ignore stale events. It may only be necessary to bump the version counter for events that modify the tree structure.

[joelq]

Will this also suffer from a stale data problem? If one event changes the structure of the tree, a subsequent event might have its index map to the wrong place in the tree? That is, if the second event picks up a stale index.

Yes, this suffers from the same issue as indexedMap. However, Elm re-renders the view (and the event handlers that use the positional ids) any time the structure changes so it’s pretty safe for normal events.

Using the positional ids for longer-lived processes (like HTTP requests) is dangerous for the reasons noted.

The tradeoff here is between having to add more permanent ids to everything which is more work but works in a broader range of situations and getting free positional “ids” that are short-lived

[joelq]

I’ll probably be talking about this a bit at Elm Europe in the context of making full use of union types!

Super excited to hear more about that!

It may also be worth looking into tree zippers to handle this

Nice! I’ve never tried tree zippers myself but the package I linked for Tree.indexedMap also provides a Tree.Zipper module

[rupert]

However, Elm re-renders the view (and the event handlers that use the positional ids) any time the structure changes so it’s pretty safe for normal events.

I have seen some situations where the events trigger close enough together that the view has not had time to update. For example if you detect mouse out on one element and mouse over on an element immediately next to it, you can get glitches. Or even a single element on its own that changes appearance when the mouse is over, you can move the mouse fast enough that the mouse out gets stale state. Sometimes it is possible to do things in such a way that the last update “wins” even though it has stale state and everything works out ok.

[rtfeldman]

@rupert could you demonstrate this with an Ellie by any chance? I’d be curious to see if 0.19’s new event handling options can address it.

[rupert]

That would definitely be interesting to learn about. I think this should be sufficient to demonstrate it:

https://ellie-app.com/yVC9wPk33xa1

[Y0hy0h]

It took me a short while to understand, but I think I got it. This type basically wraps the tree and “marks” the parts that have been walked, right?

Does this type work around the problem of rewalking the tree in the update? I ask because I do not yet have a good conceptual model for how the arguments of messages are passed to update. Following rupert’s example, I anticipate that ToggleOpen currentZipper actually passes the exact instance currentZipper to update, did I understand that correctly?

For now, I’d prefer the simplicity of an indexed tree, since I can tolerate the redundant search in update, but I’d still be interested in the most efficient way of doing it.

[rupert]

It took me a short while to understand, but I think I got it. This type basically wraps the tree and “marks” the parts that have been walked, right?

Does this type work around the problem of rewalking the tree in the update ?

I presume this is referring to the data structure that Evan posted? I was also trying to understand it, and yes, I think it is used as you describe; it marks a node in the tree with a focus and records a path that you can use later to walk back to that node.

Comparing that with with the Tree.indexedMap approach, it will be more efficient. This is due to the way indexedMap will walk the entire tree each time - the TreeExplorer will walk you more directly back to the node of interest. Provided the tree is balanced indexedMap will be O(n) but TreeExplorer will be O(log n). The zippers way will be similar in efficiency to TreeExplorer - it gives you the node of interest at zero cost but you still have to turn the zipper back into a tree with O(log n) cost. Note also, this assumed a balanced tree. A list can be viewed as a completely unbalanced tree so all the costs are O(n) worst case.

I think as you walk a tree you could maintain a list of all your path choices to get to a particular focus with this data structure:

type SignPost
  = BranchL
  | BranchR
  | Focus -- Don't really need this as end-of-list implies it.

type alias TreePath = List SignPost

(Trees displayed in a UI not likely to be binary, so type alias TreePath = List Int is more realistic).

Then you would pass the TreePath with the Msg as a way of remembering how to get back to the node of interest.

The TreeExplorer and zipper techniques both suffer from the problem that they capture the tree and pass it with the message - meaning if two msgs are triggered against the same model the second update against the tree will obliterate the first one. Tree.indexedMap and TreePath above do not have this problem.

Tree.indexedMap and TreePath avoid the stale update problem when altering the content of nodes in the tree without changing its structure. If nodes are added, removed or moved on one update, a second stale update may not find its way back to the correct node. This could lead to an intermittent bug where the wrong node is updated but the program continues to run unaware of the error. This could be solved by adding unique ids on all the nodes and checking the correct node has been found prior to making the update - what would you do in that case? simply discard that event? I also think that the unique ids could be embedded into a re-usable data structure in such a way that you don’t have to re-implement this each time.

I anticipate that ToggleOpen currentZipper actually passes the exact instance currentZipper to update , did I understand that correctly?

Yes, that is correct.

We should also look at the memory cost of these approaches, but I’ll save that for later unless someone else figures it out…

[system]

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