# [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

--
http://apfelmus.nfshost.com