[Haskell-cafe] Is there a name for this algebraic structure?

[Heinrich Apfelmus]

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