Smart way to walk and edit a tree

Learn
1

New to Elm but already delighted by the ease of refactoring and the joy of writing correct code.

I’m playing around with Tree and Zipper to prototype a Tree editor.

To move a node, I end up with this code:

-- Tree and Tree.Zipper modules are exposed
moveDown : Zipper NodeWithId -> Zipper NodeWithId
moveDown z = 
  let
    currTree = z |> tree
    currId = z |> Tree.Zipper.label |> .id
  in
  z
    |> nextSibling
    |> Maybe.map (append currTree)
    |> Maybe.andThen previousSibling
    |> Maybe.map removeTree
    |> Maybe.withDefault (Just z)
    |> Maybe.withDefault z
    |> findNext (\x -> x.id == currId)
    |> Maybe.withDefault z
-- moveUp, moveLeft, moveRight are variations of the above.

I kinda works, but my intuition is that this code could be smarter.

First I don’t like the fact that I have to specialize the node to have an Id so I can reposition the zipper on the initial focus after the operation, mainly due to remove that send the focus back to the parent.

Second I don’t like the fact that I have to “unwrap” all those Maybe.

Do you have any suggestions for any of these issues or other improvement ?

Cheers

2

Hi @setop !

Based on the API, it appears that you are using the zwilias/rosetree package for these Trees.

The Maybe’s could be brought under a bit more control by using Maybe.andThen a lot more:

z
  |> nextSibling
  |> Maybe.map (append currTree)
  |> Maybe.andThen previousSibling
  |> Maybe.andThen removeTree
  |> Maybe.andThen (findNext (\x -> x.id == currId))
  |> Maybe.withDefault z

It may make sense to actually also remove that final Maybe.withDefault and just let this function return a Maybe (Zipper NodeWithId), using the Nothing case to indicate that the operation was not possible just like the underlying library does.

This last part is a bit more “off the wall”, so feel free to disregard it. Taking a step back, there is actually a completely different pattern that I encountered in a blog post that I am currently unable to find where you convert your “impossible states are impossible” data type into a less safe (but more convenient) data type, make the change in that data type, and then parse it back into your safe data type.

In this case, our safe data type is our Tree NodeWithId / Zipper NodeWithId. A less safe, but more convenient, data type might be a Dict Id NodeWithRelationships, where each NodeWithRelationships contains an Id for their parent and a relative rank within its sibling group. This is obviously not safe (so many impossible states are possible to represent), but is much more convenient. For example, moving a tree within this data type is as simple as updating the parent Id and sibling rank on a single record. After you make this change, you use the general purpose parsing function to turn it back into a Tree or Zipper. If the general purpose parsing function cannot turn it back into a Zipper, then that means that the update you made in the unsafe data type was actually not valid.

1 Like
3

Thanks @Enkidatron for the advises.

Zipper sounds appealing because it was modeling my business logic quite well : navigate in a tree, book-keeping the current position. But the mutating part seems less obvious.

I’ve started implementation with other data structure : dict, list depth first, list breath first. Nothing obvious for the moment. Mutating the immutable is tricky :slight_smile:

4

For the record, in Elm Designer I store the document nodes as a a rosetree structure using Tree.Zipper - elm-rosetree 1.5.0 - so you may want to take a look how it is done.

The relevant code is in Document.elm: elm-designer/Document.elm at master · passiomatic/elm-designer · GitHub

5

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