Functional node joining interface?

[kawu]

Perhaps it would be better to replace the monadic interface for joining nodes in a feature graph with a functional one. Right now, we are using a monadic interface mainly because:

• We are using a pipe for logging,
• There's an underlying state with disjoint-set of node identifiers, queue of node-pairs and the feature graph itself.

Logging is not that important, especially now that we know what we are doing.

Queue is only valid within the scope of one join operation, because every time we join two nodes we want to perform the iterative node-merging process as long as the queue is not empty.

Feature graph can be an explicit argument and result of the join operation.

What remains is the disjoint-set over graph nodes. It is a by-product of the join operation as well. Otherwise, we would have to update all external pointers to graph nodes (as well as internal identifiers kept in edges), taking into account that some of the nodes might have been merged with others and subsequently removed.

If we don't want to update external identifiers, we need to make sure that all identifiers valid before the join are also valid after the operation. They may point to different nodes, but still -- they need to be valid. The only reasonable solution seems to be to represent the graph and the disjoint-set jointly, in one data structure.

[kawu]

It seems that we will need a monad after all. Even the simple node function, which is supposed to retrieve a node hidden under the given ID, modifies the underlying disjoint-set. It would be inconvenient to keep track of the graph all the time.

Besides, we might want to use a lower-level, ST/IO-based implementation of disjoint-set at some point and that would require from us to use a monadic interface.