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.

Cheers,
--Lucas

2015-04-20 22:12 GMT+01:00 Gleb Peregud <gleber.p@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@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe