Brent Yorgey wrote a post on using
category theory to formalize patch
theory.
In the middle of it, he talks about the need to commute a patch to the
end of a patch series, in order to apply a patch undoing it. He suggests
a necessary condition to do this is that, given patches P and Q, we need
to be able to find patches Q' and P' such that PQ=Q'P', and preferably
such that Q' and P' capture some of the info in P and Q.
However, as such, this is not enough to solve the issue. For one thing,
we can set Q'=P and P'=Q, and things are the way he asks for.
Now, I wonder whether we can solve this by using PROPs (or possibly
di-operads or something like that). Let's represent a document as a list
of some sort of tokens. We'll set [tex]D_n[/tex] the set of all lists
of length [tex]n[/tex], and we'll set [tex]P_n^m[/tex] to denote
operations that take a list of length n and returns a list of length m.
One operation here is obvious - the identity operation. So we'll take
that into the mix. And we'll also want to have some manner of composing
operations. So, set [tex]\circ_i:P_n^m\times P_r^s\to
P_n^{m+s-r}[/tex] to be the operation that applies the second argument
to the elements i,i+1,...,i+m of the list outputted by the first
argument.
This way, we can make patch trees - using the identities to fill out
when a patch doesn't influence everything; and have composition of
operations represent composition of patches.
Now, the commutativity that Brent asks for would manifest as an
additional relation - on top of those inherent in the definition of a
PROP - to rebuild trees. One obvious one pops out immediately - as long
as the trees don't overlap, in other words, as long as the subtree we
want to reorganize is contractible (in the topological sense), we can
commute patches freely.
When trees -do- overlap, however, the undo operation Brent asks for is
much more tricky. Consider the following sequence of edits:
[] -> [a] -> [b] -> [cbd]
Now, undo the insertion of [a].
Sure, taken this way, we cheat a little. Maybe we want to restrict edit
descriptions to explicit deletions and additions. So we would have
[] -> [a] -> [] -> [b] -> [cb] -> [cbd]
and here we could probably move things around a bit easier. I don't
quite see how to do it, right now, though.