Hi @rupert, thank you for your work on this. The sample implementation makes for interesting reading.
I have a question, which you might or might not be able to answer. (Because I’m not sure if it’s a genuinely difficult problem or whether there’s an obvious solution that I’m missing.) I’ve developed an elm app that’s basically a tree editor. One of the operations that the app supports (and which seems like it would be common in any sort of editor for a tree-like structure) is to move a node from one place in the tree to another. So the Msg that comes to the app is something like MoveNode from to, where from and to are paths in the tree. The fly in the ointment is that inserting or deleting a node might change the structure of the tree so that the paths are no longer valid.
When I was figuring out how to implement this, I looked at an article about multi-zippers. I thought that this might be a would be a way of implementing the functionality that’s correct in principle, but I haven’t had the time to do it. (This editor is just a tool for me to do my primary job, so “mostly works now” is more important than “works correctly and elegantly in the general case”. It’s a very complicated algorithm (at least for me), so I fear it would take too long for me to nail down the implementation).
Like you, I implemented paths as a list of integers. What I wound up doing was writing code to compare from and to to see if deletion at from would affect the validity of to, and if so to modify the to value for the insertion. This eventually worked, but it was a bug-ridden road to get there. The code is also difficult to understand at a glance (even for me, who wrote it). I’ve pasted it below (warning: it’s ugly; inevitably some support functions are missing but I have added additional comments and I hope the remaining omitted material is obvious). It’s a particular requirement of my app that movement must not alter the linear order of the nodes; that validation is mixed up in this code as well (but wouldn’t be needed in the general case).
I like your concept of the tree datatype as a combination of a tree of IDs plus a mapping of IDs to datums. I think if I were to reimplement this code from scratch, I would probably adopt your structure and implement node movement by:
- Creating a new ID whose datum is a copy of
from's datum - Inserting this ID into the tree at
to - Deleting the ID of
tofrom the mapping, and from the tree
In step 3, we no longer need the path to to to be valid, because we would walk the whole tree and use equality to find where to delete the to ID. This is not terribly efficient (since we have to walk the whole tree, instead of just the paths from the root to from and to. But it has the advantage of being simple and obviously correct. (If speed turned out to be a problem in practice, I have a feeling I could leverage some facts about the shape of the trees in my application domain to optimize the algorithm, at the cost of generality.)
So my question, which has turned into more of a musing, is whether you have thought about how to implement node movement in your library, and if so what conclusions you have drawn.
-- Return the new tree and also the path to the moved node
-- (It will be shown as "selected" in the interface)
-- The "to" argument is the intended new parent node;
-- depending on the direction of movt we will insert the
-- moved node either as the first or last child of this node.
-- Result is a custom type which is isomorphic to
-- (elm core) Result String a, with a few more bells and
-- whistles not used in this fn; the R.(succeed,fail) =
-- core's Ok and Err constructors
moveTo : Path -> Path -> Tree -> Result (Tree, Path)
moveTo from to tree =
if isOnlyChildAt tree from
then R.fail "Can't move only child"
else
let
-- Split the path into the common prefix and the differing suffixes
-- For reasons, provide the full suffix as well as the head::tail
-- of each list (head = sib, tail = tail, whole suffix = frag)
{ common, sibFrom, sibTo, tailFrom, tailTo, fragFrom, fragTo } = Path.splitCommon from to
in
case (sibFrom, sibTo) of
(Nothing, _) -> R.fail "Can't move to own child"
(Just sFrom, Nothing) ->
-- Movement to own parent
case (allFirst (Path.childPath sFrom common) tailFrom tree,
allLast (Path.childPath sFrom common) tailFrom tree) of
(True, False) ->
-- Leftward
let
toPath = Path.childPath sFrom common
in
R.succeed <| (performMove from toPath tree, toPath)
(False, True) ->
let
toPath = Path.childPath (sFrom + 1) common
in
R.succeed <| (performMove from toPath tree, toPath)
(False, False) -> R.fail "can't move from the middle"
otherwise -> R.fail "should never happen"
(Just sFrom, Just sTo) ->
case sFrom - sTo of
-1 ->
-- Rightward
case (allFirst (Path.childPath sTo common) tailTo tree,
allLast (Path.childPath sFrom common) tailFrom tree) of
(True, True) ->
let
adjPath1 = case Path.isFragEmpty tailFrom of
True -> Path.join (Path.childPath sFrom common) tailTo |> Debug.log "adjusted"
False -> Path.join common fragTo
adjPath = adjPath1 |> Path.childPath 0
in
R.succeed <| (performMove from adjPath tree, adjPath)
otherwise -> R.fail "can't move to/from the middle"
1 ->
-- Leftward
case (allFirst (Path.childPath sFrom common) tailFrom tree,
allLast (Path.childPath sTo common) tailTo tree) of
(True, True) ->
let
nKids = get to tree |>
children.get |>
Array.length
adjPath1 = Path.join common fragTo
adjPath = Path.childPath nKids adjPath1
in
R.succeed <| (performMove from adjPath tree, adjPath)
otherwise -> R.fail "can't move to/from the middle"
otherwise -> R.fail "can't move from non-adjacent siblings"
performMove : Path -> Path -> Tree -> Tree
performMove from to tree =
let
moved = get from tree
in
deleteAt from tree |>
insertAt to moved