3 ms·
Interesting, I have seen CRDTs mostly in the Erlang context (monitoring and following works Basho has been doing for Riak). Basically a lot of this: http://ba
by rdtsc 13y ago
Interesting, I have seen CRDTs mostly in the Erlang context (monitoring and following works Basho has been doing for Riak).
Basically a lot of this:
http://basho.com/tag/crdt http://basho.com/tag/crdt
But using Haskell's type system is an interesting idea.
You can start with one level higher than just looking for associative, commutative and idempotent, because that actually comes the definition of a semilattice
http://en.wikipedia.org/wiki/Semilattice http://en.wikipedia.org/wiki/Semilattice
The crucial part is that you have an appropriate meet or join operator (and that it satisfies the above requirements).
Informally think of a functions like max() over natural numbers or a union() over sets. Those are some examples.
I don't know Haskell but found this interesting gist of someone who has tried this, and frankly a lot of stuff there is above my head, but it might help you:
https://gist.github.com/pozorvlak/6540639 https://gist.github.com/pozorvlak/6540639
- boothead 13y agoThat is interesting (but also sadly over my head too). I think some of the theory there is starting to get into operational transformation territory [1]. If that's the case then a really interesting application might be applying the same semantics indexing a stream of events to expressing events as a diff against state and propagating them to clients... [1] http://en.wikipedia.org/wiki/Operational_transformation http://en.wikipedia.org/wiki/Operational_transformation
- benjumanji 13y agoYou probably want to look at LVish, is you want to see what this looks like in haskell. http://www.cs.indiana.edu/~lkuper/ http://www.cs.indiana.edu/~lkuper/ Has tons of papers and https://hackage.haskell.org/package/lvish https://hackage.haskell.org/package/lvish is the lib.
- tel 13y agoThis is definitely aligned with OT. OT typically comes in two steps—merge and simplify. Merge takes two divergent histories and puts them together into a collective view. Simplify takes that collective view and reduces it to a single "consistent" view according to domain rules. With CRDTs the merge operation is made such that the simplify operation is id. It's also interesting to note that the merge operation is just a pullback in the appropriate category.
- lgas 13y agoI've never used it, but there is a lattice package on hackage which provides typeclasses for semilattices: http://hackage.haskell.org/package/lattices-1.2.1/docs/Algebra-Lattice.html http://hackage.haskell.org/package/lattices-1.2.1/docs/Algeb...