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

lucas di cioccio lucas.dicioccio at gmail.com
Mon Apr 20 21:57:06 UTC 2015

Hi Gleb,

I think join/meet-semilattices captures idempotence (in a sense, convexity
and monotonicity) pretty well, but they may require a slightly
different/stronger structure than what you may need. Depending on the
properties you really need, maybe a Poset is enough.

For example, the "meet" function maps pairs of elements of "S" to elements
of "S". Whereas your "update" takes an "S" and an arbitrary "a", which is
slightly different. However, if you have an existing "update" function for
some given a, one possibility is to project any "a" to an "S" with "update
empty :: a -> S". Then you can work using the semilattice.


2015-04-20 22:12 GMT+01:00 Gleb Peregud <gleber.p at gmail.com>:

> Hello
> 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]
> An example of this would be Data.Set:
>     empty = Set.empty
>     update = flip Set.insert
> Is there something like this in algebra?
> Cheers,
> Gleb
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20150420/6c363194/attachment.html>

More information about the Haskell-Cafe mailing list