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

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

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

That 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

This 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.

You probably want to look at LVish, is you want to see what this looks like in haskell.

http://www.cs.indiana.edu/~lkuper/

Has tons of papers and

https://hackage.haskell.org/package/lvish

is the lib.

I'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/Algeb...

It's an idempotent commutative monoid, so you can encode that quite straightforwardly as a type class.

Twitter's Algebird[1] has a wide range of monoid implementations (in Scala). It's a surprisingly useful type class for something so simple.

I have a talk[2] and some code [3] that goes into more detail on CRDTs and the connection to monoids.

[1:] https://github.com/twitter/algebird

[2:] http://noelwelsh.com/programming/2013/12/20/crdts-for-fun-an...

[3:] https://github.com/noelwelsh/crdt

Thanks Noel, I had seen algebird before - it looks great!

It's only a monoid if there's an identity.

They can be tested with quickcheck as well: http://yellerapp.com/posts/2014-05-08-testing-riak.html

Relevant work I've done in the past:

http://christophermeiklejohn.com/coq/2013/06/11/distributed-...

Also, see related papers from PaPEC '14:

http://dl.acm.org/citation.cfm?id=2596631

Cool, what's your database?