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