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

Heinrich Apfelmus apfelmus at quantentunnel.de
Thu Apr 23 10:49:16 UTC 2015

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


More information about the Haskell-Cafe mailing list