Melange_compiler_libs.Diffing_with_keys
When diffing lists where each element has a distinct key, we can refine the diffing patch by introducing two composite edit moves: swaps and moves.
Swap
s exchange the position of two elements. Swap
cost is set to 2 * change - epsilon
. Move
s change the position of one element. Move
cost is set to delete + addition - epsilon
.
When the cost delete + addition
is greater than change
and with those specific weights, the optimal patch with Swap
s and Move
s can be computed directly and cheaply from the original optimal patch.
let with_pos: list('a) => list(with_pos('a));
type change('l, 'r, 'diff) =
| Change(mismatch('l, 'r, 'diff))
| Swap of {
}
| Move of {
}
| Insert of {
}
| Delete of {
}
;
This specialized version of changes introduces two composite changes: Move
and Swap
let prefix: Stdlib.Format.formatter => change('l, 'r, 'diff) => unit;
module Define: (D: Diffing.Defs with type eq := unit) => { ... };