4 ms·

Yep. And if what you have is an Abelian Group, then you also get distributed computation as well (thanks to commutativity).

dllthomas 6y ago
While true, that's too strict. An Abelian group (like any group) needs inverses. You get distributed computation if you've got an Abelian semigroup.
- lliamander 6y ago
  Thanks for the correction. I think that in Avi Bryant's talk (that I linked to above) Stripe ended up using Abelian groups for some reason, rather than Abelian semigroups, though if so I forget the reason why.
  - dllthomas 6y ago
    Inverses don't show up as much as I'd (aesthetically?) like in computing. There was an interesting application here: https://www.reddit.com/r/haskell/comments/9x684a/edward_kmett_there_and_back_again_regular_and/ https://www.reddit.com/r/haskell/comments/9x684a/edward_kmet...
- Koshkin 6y ago
  To be fair, Abel did not know (or care) about semigroups.
  - dllthomas 6y ago
    That matches my understanding, but the terminology is still (IME) common.
gnulinux 6y ago
You can distribute the computation on just a monoid as well but it needs more bookkeeping. In particular, your reduce function should know * lhs is before rhs * There is no data between lhs and rhs
- dllthomas 6y ago
  One way of looking at it is that equipping our data with that bookkeeping gives us something that commutes.
  - gnulinux 6y ago
    Hmm sure, but it is not a requirement that your underlying algebraic structure should commute, so I think original phrasing was misleading. The bookkeeping allows you to commute a specific list of objects, even though the underlying operation is anti-commutative (i.e. exists a,b a.b != b.a). At the moment of computation, you can build a new structure that commutes by enumerating the data. I guess it's true that you need a commuting intermediate data structure to be able to distribute.
    - lliamander 6y ago
      One of the ideas in the talk I link is how you can represent typically non-commutative data (like averages) in a data structure that does support commutative operations (numerator/denominator pair) and to take advantage of generic analytics infrastructure.
    - dllthomas 6y ago
      Yeah, I think it's informative that you "need commutativity" but important that you can build it yourself. It's nice (mostly from an efficiency standpoint, sometimes from a complexity stnadpoint) when you can get it "for free" because the underlying type is commutative, and the fact that you're shooting for commutativity can inform how you build and test the bookkeeping. As an interesting nit, "anticommutative" specifically means that a.b = -(b.a), which is different than simply not being commutative. A group might be commutative, anticommutative, neither, or even both (trivially true of the empty group and the group with one element, but I think it can be true of larger groups).
      - gnulinux 6y ago
        Ah, my terminology is rusty as it's been years since my math classes. I guess I need to review my algebra books again. I do have some personal code that called "exists a,b a.b != b.a" anticommutative, didn't even realize that's wrong terminology!

dllthomas 6y ago

While true, that's too strict. An Abelian group (like any group) needs inverses. You get distributed computation if you've got an Abelian semigroup.

lliamander 6y ago
Thanks for the correction. I think that in Avi Bryant's talk (that I linked to above) Stripe ended up using Abelian groups for some reason, rather than Abelian semigroups, though if so I forget the reason why.
- dllthomas 6y ago
  Inverses don't show up as much as I'd (aesthetically?) like in computing. There was an interesting application here: https://www.reddit.com/r/haskell/comments/9x684a/edward_kmett_there_and_back_again_regular_and/ https://www.reddit.com/r/haskell/comments/9x684a/edward_kmet...
Koshkin 6y ago
To be fair, Abel did not know (or care) about semigroups.
- dllthomas 6y ago
  That matches my understanding, but the terminology is still (IME) common.

gnulinux 6y ago

You can distribute the computation on just a monoid as well but it needs more bookkeeping. In particular, your reduce function should know * lhs is before rhs * There is no data between lhs and rhs

dllthomas 6y ago
One way of looking at it is that equipping our data with that bookkeeping gives us something that commutes.
- gnulinux 6y ago
  Hmm sure, but it is not a requirement that your underlying algebraic structure should commute, so I think original phrasing was misleading. The bookkeeping allows you to commute a specific list of objects, even though the underlying operation is anti-commutative (i.e. exists a,b a.b != b.a). At the moment of computation, you can build a new structure that commutes by enumerating the data. I guess it's true that you need a commuting intermediate data structure to be able to distribute.
  - lliamander 6y ago
    One of the ideas in the talk I link is how you can represent typically non-commutative data (like averages) in a data structure that does support commutative operations (numerator/denominator pair) and to take advantage of generic analytics infrastructure.
  - dllthomas 6y ago
    Yeah, I think it's informative that you "need commutativity" but important that you can build it yourself. It's nice (mostly from an efficiency standpoint, sometimes from a complexity stnadpoint) when you can get it "for free" because the underlying type is commutative, and the fact that you're shooting for commutativity can inform how you build and test the bookkeeping. As an interesting nit, "anticommutative" specifically means that a.b = -(b.a), which is different than simply not being commutative. A group might be commutative, anticommutative, neither, or even both (trivially true of the empty group and the group with one element, but I think it can be true of larger groups).
    - gnulinux 6y ago
      Ah, my terminology is rusty as it's been years since my math classes. I guess I need to review my algebra books again. I do have some personal code that called "exists a,b a.b != b.a" anticommutative, didn't even realize that's wrong terminology!