I agree that Diffing.diff is essentially a functor with only one function in the body. This is really the edge case where I hesitate between functors and functions with too many arguments.

The gains from my perspective are the following:

• less type parameters all around: I can actually read the types now
• no need to carry ~test ~update all around

The loss is the fact that some forms of parametrization between different "instances" cannot be easily expressed anymore: map is not expressible for example. But we didn't need those anyway. Having to repeat the type declarations in the producer and the consumer also gets tiresome, so I kept a parametrized version of change outside the functor.

(There is room for potential naming discussions: maybe the types eq and diff should be eq_witness and diff_witness for example?)

@Drup What is the problem with having some Diff callsites use a Diffable parametrized over the local environment? I could get rid of this by defining them as a local module inside the corresponding diff function, but I thought it would be clearer this way. It is purely a client-side decision, not related to the functorized API on the Diffing side. (I could of course shoehorn (loc, env) as a non-changing part of the state, or add yet another type component to the functor input module for this callsite information, but that would be more complex.)

It's not a "problem" per se. but you are trading parametric polymorphism with 4 or 5 arguments, with a functor+local functor declaration. The complexity difference just isn't that big.

It's the same on the callsite, but the definition side is substantially simpler, I think? Both in the type declarations and in the implementation.

(I realize now reading the functor implementation again that I forgot to propagate the weight, test, update functor parameters to the internal functions, which are still parametrized when they don't need to. Let me change that.)

Done.

On types:

-val diff :
-  weight:(('l, 'r, 'eq, 'diff) change -> int) ->
-  test:('state -> 'l -> 'r -> ('eq, 'diff) result) ->
-  update:(('l, 'r, 'eq, 'diff) change -> 'state -> 'state) ->
-  'state -> 'l array -> 'r array -> ('l, 'r, 'eq, 'diff) patch

+ val weight : change -> int
+ val test : state -> left -> right -> (eq, diff) result
+ val update : change -> state -> state * left array option * right array option
+ val diff : T.state -> T.left array -> T.right array -> T.patch

On terms:

-let diff ~weight ~test ~update state line column =
-  let update d fs = { fs with state = update d fs.state } in
-  let fullstate = { line; column; state } in
-  compute_matrix ~weight ~test ~update fullstate
-  |> construct_patch
- 
+ let diff state line column =
+  { state; line; column }
+  |> compute_matrix
+  |> construct_patch

(I'm thinking of going ahead and functorizing Diffing_with_keys as well.)

Concerning the Diffable functor, this can be avoided by integrating the environment and location in the state, isn't it?

I pushed a new commit that also functorizes Diffing_with_keys, resulting in a pleasant simplification. (The user does not have to deal with two diffing modules at once.) There is a bit of boilerplate in building the Diffable argument to the Diffing-with-keys functor, but I think this is less frightening for users/maintainers than unspeakable (or rather unwritable) parametric polymorphism.

There you go: the Diffable modules are now inside the Diffing functions instead of being functorized over their parameters, a 40% reduction in the number of functor applications introduced by this patchset.

Also as a generic comment, the functorization of the Diffing module seems orthogonal to the parent PR? Once we converge on an interface, I would propose that I (and @Drup ?) review it as an independent PR. Then I will the functorization commit of the keyed version.

I wanted to see Diffing_with_keys functorized as I was reviewing the PR, and I thought that getting my hands dirty would be even better in terms of code-understanding-sharing than just asking someone else to consider extra work. (Sure was.) Functorizing Diffing was a natural first step before functorizing Diffing_with_keys. I don't have strong opinions in the order in which the PRs should be considered.

I'm a bit frustrated by the discussion around this PR. I have the impression that I made a real effort working on this code to get the hang of it; not expecting a medal, but you could sound more enthusiastic about #2 at least!

Thank you for taking the time of understanding the rootPR.
The dead code fix in #2 is nice.
Nevertheless, I am not enthusiastic about either PRs.

#2 is mostly moving around complexity (maybe decreasing it a little?).
#3 seems to be mostly increasing complexity by lifting back a functor that was lowered to the core language. If the core issue was the unreadable types, maybe something like 0ac0fef would work better?

In order to facilitate comparison with other approaches, I implemented the restricted interfaces with Diffing.Make, Diffing.MakeVariadicLeft and Diffing.MakeVariadicRight. There is a bit more (harmless) boilerplate in the library (four interfaces and four functors, three of them exposed and one hidden), but it does simplify the client code a bit.

Re. termination: I think that the key argument is that termination is ensured when the update function that the "input sizes" of all produced intermediary states are globally bounded in both directions. One sufficient criterion for this is that (1) one size never extends, and (2) the other never extends on Insert/Delete, but both aspects could be relaxed, it's just that nobody cares to write the more general implementation and that we don't have use-cases for now. (The current codebase is not correct in presence of extension on both sides; I think that the matrix computation works but reconstruction of the best path does not. This is a sensible reason to hide the extending-on-both-sides capability from the user.)

I have played with a version with twice the number of functors: https://github.com/Octachron/ocaml#semdiff_functor_types . Having separate type definition functors make the impact on the implementation less intrusive while making sure that each diffing function is constrained to its own change type.
Of course, this is also probably totally over-engineered.

I think the result is reasonably nice. Would you care to submit it as a PR to your PR, superseding these ones?

Some comments looking at semdiff_type_decl...semdiff_functor_types (I can't post comments inline), in reverse patch order:

• in Diffing_with_keys, I find the name Extended_defs unfelicitous ; these definitions are arguably not an "extension" of the previous ones (we are never working with both at the same time), but rather a sort of "inner core" on which the features related to the Defs are built. So I would call them Inner_def.
• In Diffing, sig val diff : ... end is duplicated three times. This also happens in my version (in the present PR; ), but I can't avoid it as the type of my diff depends on the functor argument. This is not the case in your version, you could have a Defined.Diff module type for this, and you could in fact also reuse it in Diffing_with_keys.
• Going in a different direction: I find your diffing_with_keys.mli hard to read, because it exposes a lot of details on the setup structure of Diffing, you have to be familiar with this module to understand the Diffing_with_keys signature. (This was already somewhat the case with my version, but less so.). Most of this internal layout is not in fact needed to describe the type of the final diff function. I think you should try unfolding/inlining the functor layers here, see if you can get a definition that is conceptually slightly more redundant, but more self-contained and much easier to read in practice.
• Why are you using a generalize function to witness the relation between the specialized change and the generic version, instead of just exposing type change = (left, right, ...) Generic.change in the signature?
• Defined is not a very nice name (the fact that its argument is named Defs suggest that you ran out of naming inspiration at that point.) If we want a bland name, what about just Make? Its result could be named Diff, and then the result of Simple would be just F (instead of Diff).

Indeed, I completely ran out of naming fuel along the way.

Why are you using a generalize function to witness the relation between the specialized change and the generic version, instead of just exposing type change = (left, right, ...) Generic.change in the signature?

This has the advantage of making the update and test handles the correct change type by construction since the specialized change type is the only one in scope.

Superseded by #4