As pointed by Martin, 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
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.
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.
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
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. or Pawlik and Augsten, 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., which was later extended by Vassena. I am currently focusing on approaches that distance themselves from edit scripts for the very problems I pointed earlier, such as our latest work or some earlier work 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.