[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
More information about the Haskell-Cafe
mailing list