1
$\begingroup$

Suppose that I have some nested algebraic data type (ie. something one can construct via datas in Haskell) that is serializeable (so no functional fields a -> b) is there any literature or known algorithms about how to automatically derive an efficient delta encoding of a change to that data type.

data ADT = ...

data ADTDelta = ...

applyDelta : ADTDelta -> ADT -> ADT

There are a lot of interesting aspects to this problem, but I am not familiar enough with the CS theory to know how to phrase this question to find prior work. I italicized automatically because one would want to keep the two data types in sync and efficiently because the use case I have in mind has small changes to the data type passed over a costly communication channel.

For example, given a regular optional or maybe type

data Optional a
  = Some a
  | None

one good representation of a delta could be

data DeltaOptional a delta
= Replace a      -- When we go from None -> Some a
| Modify delta   -- Recursively change `a` inside of a Some
| Delete         -- Some a -> None
$\endgroup$
2
  • $\begingroup$ Does every type used in the ADT support efficient equality comparison? It sounds like you're looking for an algorithm to do something -- what are the inputs to the algorithm? Two instances of that data type? $\endgroup$
    – D.W.
    Commented Apr 27, 2023 at 17:49
  • $\begingroup$ Yes, every type inside can support efficient equality but that's not necessary. I think for the application of a delta you only need comparison on the constructors of a sum type or the fields of a product. I'll add an example to my original question. $\endgroup$
    – LeonidR
    Commented Apr 27, 2023 at 18:49

1 Answer 1

1
$\begingroup$

I suspect you're not going to like this answer, but the answer is yes, there is an algorithm to automatically derive a delta encoding. Given two instances of this data type, you can recursively compute the difference between them. The diff only contains the portion of the tree that corresponds to parts that are different in both. If an element is different in the two trees, then the delta indicates to replace the old value with a specific new value, and lists the new value.

You can augment this with custom algorithms for computing delta for particular data types if you wish. For instance, if you are computing the difference between two strings, instead of the delta containing the entire new string, it could contain just the "diff" between the two.

$\endgroup$
2
  • $\begingroup$ Apologies if my question is not clear, but I am looking for an algorithm to derive a delta data type, not an instance of it. Said differently, if I have a hierarchical schema, how can I derive another hierarchical schema that efficiently describes changes to the former? $\endgroup$
    – LeonidR
    Commented Apr 28, 2023 at 19:41
  • $\begingroup$ @LeonidR, I think that my answer implicitly describes a schema for describing changes to the former. (As far as what is efficient, well, you haven't defined what efficiency measure you are using, but I'd argue that my approach is reasonably efficient.) $\endgroup$
    – D.W.
    Commented Apr 28, 2023 at 22:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.