Gleb Peregud wrote:
I am wondering if there's a well known algebraic structure which follows the following patterns. Let's call it S:
It's update-able with some opaque "a" (which can be an element or an operation with an element):
update :: S -> a -> S
There's a well defined zero for it:
empty :: S
Operations on it are idempotent:
update s a == update (update s a) a
Every S can be reconstructed from a sequence of updates:
forall s. exists [a]. s == foldl update empty [a]
If you reverse the arguments of the `update` function, then you get a map update :: A -> (S -> S) from the type `A` of "updates" to the monoid of maps Endo S . Another way to look at it is to consider a monoid `M[A]` which is generated by elements of the type `A`, subject to the condition that these elements are idempotent. In other words, you consider the following quotient M[A] = words in A / x^2 = x for each x\in A Then, the update function is a morphism of monoids: update :: M[A] -> S Mathematicians like to conflate the type `S` and the map `update` a little bit and speak of this as *representation* of your monoid. This is a useful way to look at things, for instance when it comes to the representation of groups. In any case, this is how I would approach the problem of turning this into an algebraic structure, there are probably many other ways to do that as well. Best regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com