<p>There is quite a bit of work in this direction. You could start by looking at [1, 2], but they don't exhaust the topic.</p>

<hr>

<ol>
<li><p>S. Mimram, C. Di Giusto, <a href="https://arxiv.org/abs/1311.3903" rel="noreferrer">A Categorical Theory of Patches</a>.</p></li>
<li><p>C. Angiuli, E. Morehouse, D. R. Licata, R. Harper, <a href="https://www.cs.cmu.edu/~rwh/papers/htpt/paper.pdf" rel="noreferrer">Homotopical Patch
Theory</a>.</p></li>
</ol>

CC BY-SA 4.0
2019-07-05T09:37:56.223Z
2019-07-05T09:37:56.223Z
Martin Berger
<p>As pointed by <a href="https://cstheory.stackexchange.com/users/898/martin-berger">Martin</a>, there is some work on the categorical representation of patches. Mimram and Di Giusto's "A Categorical Theory of Patches" being the most extensive categorical approach to edit-scripts as used by the <code>UNIX diff</code>.</p>

<p>In their sense, you have what you want. The objects are finite sequences of words over an alphabet <span class="math-container">$L$</span>, seen as a mapping <span class="math-container">$A : [n] \rightarrow L$</span>, where <span class="math-container">$[n]$</span> denotes the set with <span class="math-container">$n$</span> elements. An arrow between <span class="math-container">$A : [n] \rightarrow L$</span> and <span class="math-container">$B : [m] \rightarrow L$</span> is an injective partial increasing mapping <span class="math-container">$f : [n] \rightarrow [m]$</span>. Injectivity and increasing are there to indicate that copies never <em>cross over</em> each other. You can find all the details on the <a href="https://arxiv.org/abs/1311.3903" rel="noreferrer">paper</a>.</p>

<p>Yes, merging is seen as the pushout on the free cocompletion of the above category.
We need the cocompletion to make sure we add merge conflicts to our construction.
It is not the case that a merge always exists.</p>

<p>Onto your second question, there is no categorical notion of minimal edit script for two main reasons.</p>

<ol>
<li><p>Edit-scripts come in all shapes and forms. Some authors consider insertions, deletions and copies, some authors like to add substitutions as an operation too.
When you generalize from strings to trees, then, a plethora of other operations become
feasible.</p></li>
<li><p>More importantly, though, minimal-cost edit-scripts are not unique.
Take the file <span class="math-container">$ab$</span>, and write a patch that transforms it into <span class="math-container">$ba$</span>. What is the
minimal edit script that does this? There are two! Once again, when generalizing into
trees one can find even more situations where a notion of "minimality" is doubtful.</p></li>
</ol>

<p>There has been a lot of work on generalizing edit scripts to trees. This has been split in two main bodies of work:</p>

<ul>
<li><p><strong>Untyped Trees</strong>: Think of s-expressions only. The tree-edit-distance between two
trees is the string-edit-distance between the preorder traversal of said trees. You can check some bibliography by <a href="http://www.faculty.idc.ac.il/smozes/ted.pdf" rel="noreferrer">Demaine et al.</a> or <a href="https://arxiv.org/pdf/1201.0230.pdf" rel="noreferrer">Pawlik and Augsten</a>, for example.</p></li>
<li><p><strong>Typed Trees</strong>: Patches over Abstract Syntax Trees that are guaranteed to preserve
the well-typedness of the object, ie, applying a patch will always yield a valid AST.
Under the typed umbrella, there are less edit operations one can consider. Substitution, for example, doesn't make sense. Nevertheless, there exists a <em>diff over the preorder traversal of the trees</em> by <a href="http://www.andres-loeh.de/GDiff.html" rel="noreferrer">Lempsink et al.</a>, which was later extended by <a href="https://research.chalmers.se/en/publication/249246" rel="noreferrer">Vassena</a>. I am currently focusing on approaches that distance themselves from edit scripts for the very problems I pointed earlier, such as <a href="http://www.staff.science.uu.nl/~swier004/publications/2019-icfp-submission-b.pdf" rel="noreferrer">our latest work</a> or some <a href="https://victorcmiraldo.github.io/data/tyde2017.pdf" rel="noreferrer">earlier work</a> which tries to take advantage of the structure of the type of the values being "patched".</p></li>
</ul>

<p>In either of those cases I have not seen a careful categorical interpretation of tree-structured patches.</p>

CC BY-SA 4.0
2019-07-05T12:44:09.207Z
Awesome answer! But why should there be no categorical notion of minimal edit scripts just because they're not unique? (Co)limits aren't unique either, only up to isomorphism.
Turion
CC BY-SA 4.0
2019-07-05T12:45:37.410Z
I guess we could take the cocompletion and include conflicts, or just say that pushouts don't always exist, and when they don't exist there is no merge?
Turion
CC BY-SA 4.0
2019-07-05T13:56:05.277Z
@Turion, uniqueness up to isomorphism is pretty strong. We don't have that with edit scripts. This makes it pretty difficult to define _the_ arrow between $A$ and $B$ as the minimal edit script. Instead, on says that `diff` finds the minimal, but the model will consider any edit script as an arrow between $A$ and $B$. Composition is another problem, for example. Composition of minimal edit scripts is not guaranteed to be minimal.

On the other comment, yes, we could say some merges don't exist. But `diff3` does compute them. This would remove conflict handling from the model altogether.
Victor Miraldo
CC BY-SA 4.0
2019-07-05T11:48:05.563Z
2019-07-05T11:48:05.563Z
Victor Miraldo
<p>Is there a category of patches that looks roughly like this:</p>

<ul>
<li>The objects are strings in some base alphabet</li>
<li>The morphisms are edit scripts ("diffs" or "patches") between the strings</li>
</ul>

<p>I'm interested in these questions:</p>

<ul>
<li>Is there a categorical notion of <em>minimal</em> edit script? Maybe the category of patches is enriched in PO-Sets?</li>
<li>Is <em>merging</em> of patches the categorical pushout?</li>
<li>How to generalise this from strings to trees (a file system, or an algebraic datatype)?</li>
</ul>

CC BY-SA 4.0
2019-07-06T20:02:22.790Z
You will want to have a look at the [theory behind the *Darcs* VCS](http://darcs.net/Theory)
Bergi
CC BY-SA 4.0
2019-07-07T07:05:03.627Z
...or [Pijul](https://www.youtube.com/watch?v=o0ooKVikV3c), a relatively recent attempt to create a "newer Darcs". (And as far as I remember from that talk, merging is the pushout in a "free completion" of the diff category...).
phipsgabler
<ct.category-theory><edit-distance>
Category-theoretic treatment of diffs, patches and merging?
Turion
# Category-theoretic treatment of diffs, patches and merging?

(Asked by: username_0 on 2019-07-05)

Is there a category of patches that looks roughly like this:

* The objects are strings in some base alphabet
* The morphisms are edit scripts ("diffs" or "patches") between the strings

I'm interested in these questions:

* Is there a categorical notion of *minimal* edit script? Maybe the category of patches is enriched in PO-Sets?
* Is *merging* of patches the categorical pushout?
* How to generalise this from strings to trees (a file system, or an algebraic datatype)?

**Tags:** ct.category-theory, edit-distance

> **Comments:**
> **username_1**: You will want to have a look at the [theory behind the *Darcs* VCS](http://darcs.net/Theory)  
> **username_2**: ...or [Pijul](https://www.youtube.com/watch?v=o0ooKVikV3c), a relatively recent attempt to create a "newer Darcs". (And as far as I remember from that talk, merging is the pushout in a "free completion" of the diff category...).  

---

## 2 answers

### Answer by username_4 on 2019-07-05. Score: 13 | Accepted answer

As pointed by [Martin](https://cstheory.stackexchange.com/users/898/martin-berger), there is some work on the categorical representation of patches. Mimram and Di Giusto's "A Categorical Theory of Patches" being the most extensive categorical approach to edit-scripts as used by the `UNIX diff`.

In their sense, you have what you want. The objects are finite sequences of words over an alphabet $L$, seen as a mapping $A : [n] \rightarrow L$, where $[n]$ denotes the set with $n$ elements. An arrow between $A : [n] \rightarrow L$ and $B : [m] \rightarrow L$ is an injective partial increasing mapping $f : [n] \rightarrow [m]$. Injectivity and increasing are there to indicate that copies never *cross over* each other. You can find all the details on the [paper](https://arxiv.org/abs/1311.3903).

Yes, merging is seen as the pushout on the free cocompletion of the above category.
We need the cocompletion to make sure we add merge conflicts to our construction.
It is not the case that a merge always exists.

Onto your second question, there is no categorical notion of minimal edit script for two main reasons.

1. Edit-scripts come in all shapes and forms. Some authors consider insertions, deletions and copies, some authors like to add substitutions as an operation too.
   When you generalize from strings to trees, then, a plethora of other operations become
   feasible.
2. More importantly, though, minimal-cost edit-scripts are not unique.
   Take the file $ab$, and write a patch that transforms it into $ba$. What is the
   minimal edit script that does this? There are two! Once again, when generalizing into
   trees one can find even more situations where a notion of "minimality" is doubtful.

There has been a lot of work on generalizing edit scripts to trees. This has been split in two main bodies of work:

* **Untyped Trees**: Think of s-expressions only. The tree-edit-distance between two
  trees is the string-edit-distance between the preorder traversal of said trees. You can check some bibliography by [Demaine et al.](http://www.faculty.idc.ac.il/smozes/ted.pdf) or [Pawlik and Augsten](https://arxiv.org/pdf/1201.0230.pdf), for example.
* **Typed Trees**: Patches over Abstract Syntax Trees that are guaranteed to preserve
  the well-typedness of the object, ie, applying a patch will always yield a valid AST.
  Under the typed umbrella, there are less edit operations one can consider. Substitution, for example, doesn't make sense. Nevertheless, there exists a *diff over the preorder traversal of the trees* by [Lempsink et al.](http://www.andres-loeh.de/GDiff.html), which was later extended by [Vassena](https://research.chalmers.se/en/publication/249246). I am currently focusing on approaches that distance themselves from edit scripts for the very problems I pointed earlier, such as [our latest work](http://www.staff.science.uu.nl/~swier004/publications/2019-icfp-submission-b.pdf) or some [earlier work](https://victorcmiraldo.github.io/data/tyde2017.pdf) which tries to take advantage of the structure of the type of the values being "patched".

In either of those cases I have not seen a careful categorical interpretation of tree-structured patches.

> **Comments:**
> **username_0**: Awesome answer! But why should there be no categorical notion of minimal edit scripts just because they're not unique? (Co)limits aren't unique either, only up to isomorphism.  
> **username_0**: I guess we could take the cocompletion and include conflicts, or just say that pushouts don't always exist, and when they don't exist there is no merge?  
> **username_4**: @username_0, uniqueness up to isomorphism is pretty strong. We don't have that with edit scripts. This makes it pretty difficult to define _the_ arrow between $A$ and $B$ as the minimal edit script. Instead, on says that `diff` finds the minimal, but the model will consider any edit script as an arrow between $A$ and $B$. Composition is another problem, for example. Composition of minimal edit scripts is not guaranteed to be minimal.  On the other comment, yes, we could say some merges don't exist. But `diff3` does compute them. This would remove conflict handling from the model altogether.  

---

### Answer by username_3 on 2019-07-05. Score: 8

There is quite a bit of work in this direction. You could start by looking at [1, 2], but they don't exhaust the topic.

---

1. S. Mimram, C. Di Giusto, [A Categorical Theory of Patches](https://arxiv.org/abs/1311.3903).
2. C. Angiuli, E. Morehouse, D. R. Licata, R. Harper, [Homotopical Patch
   Theory](https://www.cs.cmu.edu/~rwh/papers/htpt/paper.pdf).


---

