[darcs-users] How to extend a patch theory to fully commute

[Ben Franksen]

Am 06.07.20 um 19:33 schrieb James Cook:
>> I guess you want to avoid proper cycles, i.e. cycles other than those of
>> the form patches;patches^, but that's just an intuition.
> 
> A;A^;B;B^;C;C^ isn't a proper cycle in that sense but may be useful to
> be able to have if you're merging or have merged non-commuting patches
> A, B, C.
> 
> It may be good to avoid non-tree-like cycles like B';A';B^;A^.

That's what I meant to say.

> Maybe it's possible to avoid creating them in the first place.

Yes, I think your constructions so far do that.

> As a motivating example, suppose A;B;C don't commute at all, and we
> have the context address (A;B;C, {B}, {A, C}). (I'm leaving out the
> first two parts of the tuple, since as you point out they are
> implied.)

(Unless the sequence is empty)

> From the old point of view, we can delete C because it's in Y and
> already at the end of the sequence, producing the minimal context
> address (A;B, {B}, {A}).
> 
> But another way to do it is this: first extend the sequence to the
> cycle A;B;C;C^;B^;A^. The address becomes (A;B;C;C^;B^;A^, {A^, B,
> C^}, {A, B^, C}).

Ah, yes. I forgot your idea to turn all context addresses into cycles.

But then you also have to redefine the two sets X and Y. Because in a
cycle there is no "before" or "after. (Edit: after reading to the end I
get the idea, but I don't find it very elegant.)

> (See below for some intuition about why I extended
> the sets X and Y in that way.) Then, we eliminate C;C^ as a
> consecutive pair. However, we have to be careful: if we just always
> eliminated consecutive primitive patches we'd end up with an empty
> sequence.
> 
> Viewed as a tree, this is going to look like the following: there is a
> line A;B;C with three edges, and each edge has an orientation. The "A"
> edge points left (away from B and C), the "B" edge points right, and
> the "C" edge points left. We delete the C edge following a general
> rule that leaves can be deleted when they are connected by edges that
> point to the rest of the tree.
> 
>   o--<--o-->--o--<--o
>      A     B     C
> 
>   o--<--o-->--o
>      A     B
> 
> If all of a tree's edges point inward toward one "root" node, then all
> the edges can be deleted and the tree just represents the primitive
> context at its root.

I am confused about this redefinition of the orientation of arrows. In
my book, a patch already has an orientation. In your example this would be

  o-->--o-->--o-->--o
     A     B     C

You explain this direction thing below but I don't like the overloading
of the direction concept here.

> Here's how it could work in general.
> 
> * A context address is a tuple (S, X, Y), where S is a "tree-like"
> cycle. (I used to use the notation (Qi) but that's getting annoying.)

Yup. The traditional math notation for sequences sucks badly. I like to
keep use of indices to the barest minimum possible (sometimes you need
them but most times you don't).

> (Tree-like means following the cycle is the same as doing depth-first
> search on some tree, or in other words, for every patch P with
> start/end contexts a and b in S, the patch P^ appears with start/end
> contexts b and a.)

I really like the notation established in category theory where, in
analogy to the tradition notation for functions, you just say

  P : a -> b  and  P^ : b -> a

It is patently clear from this notation that P^ cannot have any other
type. So your explanation of "tree-like" appears vacuous to me.

> * (S, X, Y) can be thought of as a rooted tree with an orientation on
> each edge, with the following transformation.
> 
> Put the root at the start/end context of the cycle S.

A cycle has no start/end context. Okay, in your notation it has one,
because you start out with a sequence of prim patches. I'll try to
accept that and go on.

> Draw a tree by
> following all the patches in S. Each edge of the tree consists of a
> pair P and P^. Orient the edge as pointing away from the root if P is
> in X and P^ is in Y, and toward the root if P is in Y and P^ is in X.

Okay, here comes the new arrow orientation. I still don';t think this is
a good idea. Can't you avoid this?

> * We can rotate S to produce an equivalent address. When we rotate,
> patches move between X and Y. Specifically, if patch P is moved from
> the start to end of S or vice versa, P and P^ switch places. In other
> words, (P;S', {P} U X', {P^} U Y') becomes (P;S', {P^} U X', {P} U
> Y').
> 
> From the tree point of view, this preserves the orientation of all the
> edges. All that happens is the root moves.
> 
> So, we can forget where the root was and just think of it as an unrooted tree.
> 
> * If P;P^ appear consecutively in S, and P is in Y and P^ is in X,
> then they can be eliminated. Similarly if P^;P appears, P^ is in Y and
> P is in X.
> 
> In other words, we can delete a leaf from a tree so long as its edge
> points away from the leaf.

Very well. What I don't get yet is what you gain from all that.

> * More transformations on S should be allowed. I'm a bit fuzzy about
> this point, For example, I'm pretty sure if S = T + U where T and U
> are cycles, you should be able to swap the order U + T.

You can. I tried to explain this in another message. You may want to
read up a bit on the basics of inverse semigroups and groupoids.

> And I guess
> you should be able to reverse S, and also to do any commuting the
> primitive patch theory allows.

Sure.

> But I'm not sure whether that's enough,

For what?

> and whether it's okay to restrict S to be tree-like during the
> intermediate steps. It is probably simpler to just drop the cycle
> version and think only of trees, but I want to make sure I understand
> how the primitive patch theory's commuting rules turn into tree
> transformations.

Why are you so hung up on this tree / cycle thing? What is wrong about
your original context addresses and patch (sequence) adresses? If
efficiency is the concern, we are talking about a factor of two here.
This is irrelevant. For the theory you need to get the asymptotics
right, the rest are implementation details.

Cheers
Ben