Digrasp - The options for representing digraphs with pairs

Digrasp 3

Previously

This is a long-ish answer to John's comment on How are dotted graphs second-class?, where he asks how I have in mind to represent digraphs using pairs.

The options for representing digraphs with pairs

I'm not surprising that it comes across as unclear. I'm deliberately leaving it open which of several possible approaches is "right". ISTM it would be premature to fix on one right now.

As I see it, the options include:

1. Unlabelled n-ary rooted digraph. Simplest in graph theory, strictest in Kernel: Cars are nodes, cdrs are edges (arcs) and may only point to pairs or nil. With this, there is no way to make dotted graphs or lists, so there is no issue of their standing nor any risk of "deep" conversion to dotted graphs. It loses or alters some functionality, alists in particular.
2. Labelled binary rooted digraph: More natural in Kernel, but more complex and messier in graph theory. Cars and cdrs are both edges, and are labelled (graph theory wise) as "car" or "cdr". List-processing operations are understood as distinguishing the two labels and expecting a pair in the cdr. They can encounter unexpected dotted ends, causing errors.
3. Dynamic hybrid: Essentially as now. Dottedness can be checked for, much like with `proper-list?' but would also be checkable recursively. There's risk of "deep" conversion from one to the other; list-processing operations may raise error.
4. Static hybrid: A type similar to pair (undottable-pair) can only contain unlabelled n-ary digraphs, recursively. List operations require that type and always succeed on it. There's some way to structurally copy conformant "classic" pair structures to undottable-pair structures.
5. Static hybrid II: As above, but an undottable-pair may hold a classic pair in its car but not its cdr, and that's understood as not part of the digraph.

And there's environments / labelled digraphs

By DIGRASP, I also mean fully labelled digraphs in which the nodes are environments and the labels are symbols. But they have little to do with the list-processing combiners.