The Theory of patches-vector | Hacker News Reader

The Theory of patches-vector

liamoc.net

22 pointspsibi12 comments

Would it not be sufficient to define Edit a minimally as:

    data Edit a = Insert  Int a
                | Delete  Int

given that a Delete only needs the place of deletion and a Replace is a Delete followed by an Insert?

I assumed that `Int` was the sequence index of the Edit, not the line number. The line position, which is not necessarily the line number, it might be contextual, is encoded in `a`. In fact the way I read the article was that `a` was a file, so you can have operations:

- Insert Int File == "create file"

- Delete Int File == "delete file"

- Replace Int File == "patch file"

Removing and Inserting a file each time it changes, while technically correct is probably not what you want.

The nice thing about what Liam proposes (and type classes in general) is that it doesn't matter what we each interpret `a` to be.

Well, a patch is defined as Patch [Edit a], so I presume the sequence of the edit is implicit in the list position. The article says that an edit is the modification of an element of a Vector. I think the parameter a is the type of the elements of the Vector. In your example, a Patch File would be something to apply to a Vector File, and the Int in the edit should be the index of the file in the vector.

Is there a 'category theory for programmers' text anyone could recommend?

Yes! http://bartoszmilewski.com/2014/10/28/category-theory-for-pr...

It uses both Haskell and C++ for examples, although for best effect it'd help if you could read (basic) haskell types. Or maybe not, I read it after learning haskell so I find it hard to just how it is from a just C++ perspective.

That's perfect :) Thanks a lot

Other than formalism what new stuff does this introduce that text OT libraries (such as google wave(?), etherpad, etc) haven't done?

"All right, but apart from the sanitation, the medicine, education, wine, public order, irrigation, roads, the fresh-water system, and public health, what have the Romans ever done for us?"

Also, the writer of the article worked on google wave.

I am not attacking formalism by the way. All of OT is basically "if these have x properties then we can do y" so I understand it is necessary. But author claims he invented a new flavor of "patch theory" but I can't see anything new here. Most of it is a standard intro on how operational transformations work except using category theory terminology.

Would like to know for example how his choice of edit operations and requirement of properties compare with let's say share.js's: http//github.com/ottypes/docs (which was also written by an ex-google wave intern). Explaining the subtle differences between OT implementations and what new advantages his theory brings is more interesting IMO.

I don't think the author claims they found something groundbreakingly new. In fact just the references contain all the points Liam makes.

Patches-vector seems to be different to ottypes for example in that ottypes have predicted what types you would want to synchronize and provides you a correspondig OT type for each of them. What if I want to synchronize binary data or javascript objects or some other weird thing? If equality is defined for my object the library shouldn't need to make any other assumptions.

Besides this practicality though, I think the whole point of the article is that one can mathematically reason about patches-vector.

A better title would be "how to make simple things complicated"

Absolutely agree. I find the phrase "simple, but theoretically-sound manipulation of diffs" physically disgusting.

Reply on news.ycombinator.com