1. 7

  2. 3

    This means that we are free to either “clean first, then aggregate”, or “aggregate first, then clean”

    If you react/aggregate first, then clean, you’d need to aggregate a second time afterwards.

    For example abAcdD.

    If you clean b then you get aAcdD then aggregate to get c.

    If you aggregate first you get abAc then clean b to get aAc (which requires another aggregate step to equal the above case).

    1. 1

      Here, aggregation and cleaning does commute. That’s because “cleaning” is not “remove c”. Cleaning means “re-interpret under a new group where C is the group identity.

      So, cleaning b from abAc doesn’t mean “remove b”. It means “re-interpret your result with c being replaced with the identity element”.

      And under that situation, re-interpreting a <> b <> A <> b where c = 1, does give us the right answer, c. Cleaning isn’t a “remove”, but a “re-react”.

      To clarify, we have:

      a <> b <> A <> c <> d <> D

      this is the aggregation. The aggregation is not aAcdD, but it is, itself, a <> b <> A <> c <> d <> D.

      Now, cleaning b is not “removing c”, but rather “replace c with 1”, so we have:

      clean (a <> b <> A <> c <> d <> D)
        = clean a <> clean b <> clean A <> clean c <> clean d <> clean D

      In the first, we aggregate-then-clean. In the second, we clean-then-aggregate.

      In both situations, we get the same final result.

      1. 1

        I have added a section in the post to address what I really mean by “clean first then aggregate” vs “aggregate first then clean” :)


        1. 1

          This actually happens because we’re not in a group anymore.

          Let F(26) be the free group on the alphabet. The the group G(26) in the problem is that group modulo the relations that every letter squares to the identity. There is a quotient map F(26) -> G(26).

          However, we don’t like computing with equivalence classes, so for each class [w] we pick the word w in F(26) in it that has the sortest lenght. That embeds G(26) in F(26) as a set, because as you point out the embedding is not closed under he group operation.

          So the blog post is mostly right.

        2. 1

          for Part1, what do you gain with that extra dependency over just

          import Data.Char
          thing1 a []     = [a]
          thing1 a (b:bs) = if toLower a == toLower b && (a /= b) then bs else a : b : bs
          thing2 = length . foldr thing1 ""


          (We don’t know that the ordering doesn’t matter because it’s a group – we know that it’s a group because the ordering doesn’t matter.)

          1. 1

            We don’t know that the ordering doesn’t matter because it’s a group – we know that it’s a group because the ordering doesn’t matter.

            This is true, but from the perspective of this post, recognizing that this is a classic example of a group reminds us that it is a group, so ordering doesn’t matter by definition. If we don’t recognize this group as a classic example of a group, we would have to look at the operations, think about whether or not the action is associative, think about whether there is an identity, think about if each operation has an inverse.

            The point is that we can recognize it from Group Theory, and apply things that were already done by group theorists to help us. That’s the crux of the benefit, I believe. Not that this wasn’t a group before we came along, but that because we can recognize it as a commonly studied group, we can draw from the large corpus of established properties that have already been studied by it.