Should splits and joins be treated as ordered or unordered?

[bel28kent]

One problem in mapping Humdrum data on to graphs or trees is spine splits, particularly when there is more than one.

Currently, they are represented as parent:

(struct parent (token left right) #:transparent)
; Parent is (parent Token (listof Node) (listof Node))
;  Represents a node with two children. The last
;  token in each list is a spine-join.

The parent-token is always a spine split. The data in the two spines that follow the split are continuously read until a spine join ends both columns. For example:

(parent (token "*^" SPINE-SPLIT 1)
        (list (leaf (token "4a" SPINE-DATA 2))
              (leaf (token "4b" SPINE-DATA 3))
              (leaf (token "4c" SPINE-DATA 4))
              (leaf (token "*v" SPINE-JOIN 5)))
        (list (leaf (token "4aa" SPINE-DATA 2))
              (leaf (token "4bb" SPINE-DATA 3))
              (leaf (token "4cc" SPINE-DATA 4))
              (leaf (token "*v" SPINE-JOIN 5))))

If there are multiple splits, then a parent becomes nested in the left or right list, as appropriate, of the previous parent:

(parent (token "*^" SPINE-SPLIT 1)
        (list (leaf (token "4a" SPINE-DATA 2))
              (leaf (token "*" NULL-INTERPRETATION 3))
              (leaf (token "4bb" SPINE-DATA 4))
              (leaf (token "4cc" SPINE-DATA 5))
              (leaf (token "*" NULL-INTERPRETATION 6))
              (leaf (token "*v" SPINE-JOIN 7)))
        (list (leaf (token "4aa" SPINE-DATA 2))
              (parent (token "*^" SPINE-SPLIT 3)
                      (list (leaf (token "4b" SPINE-DATA 4))
                            (leaf (token "4c" SPINE-DATA 5))
                            (leaf (token "*v" SPINE-JOIN 6)))
                      (list (leaf (token "4bb" SPINE-DATA 4))
                            (leaf (token "4cc" SPINE-DATA 5))
                            (leaf (token "*v" SPINE-JOIN 6))))
              (leaf (token "*v" SPINE-JOIN 7))))

[bel28kent]

Currently, the converter (hfile->ab-hgraph) has no issues in the examples above, i.e. only one split or splits ordered from left to right balanced by joins from right to left. By ordered data, I mean ordered on the record: always splitting in the right most column, and always joining from the right column to the left column.

When splits and joins are treated as ordered data, a counter for the index of the token is easy to increment and decrement. The counter is necessary because the converter is given a list of tokens for each record, with all of the lists wrapped in one outer list. I believe that Humdrum, though, allows for splits and joins to be unordered. But this makes the counter variable very difficult to increment and decrement. The converter is recursive, and different recursive calls are handling the left list and the right list. These two recursive calls have no awareness of each other. This means that the recursive calls have to independently work out how its pair might be splitting or joining to then adjust the counter properly. Given that splits and joins are arbitrary, the number of cases is large and difficult to reason about.

Here are some possible solutions:

1. Assume splits or joins are ordered. This passes cases that the converter can't handle back to the user, i.e. re-encode the data or don't use the converter.
2. Assume splits or joins are unordered, so pass the data through a preprocesser that orders them. This would complicate the conversion from the graph or tree back to a list that is necessary to write to file, because the user presumably doesn't want the parser to change their orders. Could also cause semantic errors, e.g. trying to join two columns that have different rhythmic durations.
3. Remove the counter. This is theoretically possible by having the list be a top-level variable that all recursive calls can reference, rather than a parameter/operand. The state of the list could be modified such that each recursive call deletes the token it used off the front of the list, and shifts the list down. A given call can then assume that the first of the list is always its token. One thing this complicates is the order of the left list and right list, since both left and right tokens are in one list for one record. The left list would need to pass through first and delete only its token from each record's list, leaving the rest in place for the right list.
4. Revise the data definition.

[bel28kent]

In humdrum-data:

[bel28kent]

Proportions of splits out of spine records with only splits:
Only one split = 52438/61542 = 85%
More than one split = 9104/61542 = 15%

Only two consecutive "*v" = 61319/66717 = 92%
More than two consecutive "*v" = 948/66717 = 1%
Non-consecutive "*v" = 3993/66717 = 6%