Combining Things

Below you'll find a series of simple Ruby examples. I want you to spot the commonality.

Addition

( 1 + 2 ) + 3 # => 6
1 + ( 2 + 3 ) # => 6

5 + 0 # => 5
0 + 5 # => 5

Multipication

( 2 * 5 ) * 3 # => 30
2 * ( 5 * 3 ) # => 30

5 * 1 # => 5
1 * 5 # => 5

Array Concatenation

[1,2] + ( [3,4] + [5,6] ) # => [1, 2, 3, 4, 5, 6]
( [1,2] + [3,4] ) + [5,6] # => [1, 2, 3, 4, 5, 6]

[1,2,3] + [] # => [1,2,3]
[] + [1,2,3] # => [1,2,3

String Concatenation

( "foo" + "bar" ) + "baz" # => "foobarbaz"
"foo" + ( "bar" + "baz" ) # => "foobarbaz"

"foo" + "" # => "foo"
"" + "foo" # => "foo"

Clock Arithmetic

# the implementation of `Hour` can be found below
# but the focus is on a `+` method, such that:
#
#    6 + 6 = 12
#   12 + 6 =  6

h6  = Hour.new 6
h7  = Hour.new 7
h8  = Hour.new 8
h12 = Hour.new 12

( ( h6 + h7 ) + h8 ).num # => 9
( h6 + ( h7 + h8 ) ).num # => 9

( h6 + h12 ).num # => 6
( h12 + h6 ).num # => 6


class Hour
  attr_reader :num
  def initialize(num)
    @num = num
  end

  def +(hour)
    num = ( self.num + hour.num ) % 12
    num = if num == 0 then 12 else num end
    Hour.new(num)
  end
end

The Commonality

Did you spot it?

The "Class"

In each case we have...

• a collection of things
• a rule for combining the things
• and that rule obeys some meta rules

These observations courtesy of the Brian Beckman video linked below.

The "Instances"

In particular, "a collection of things"...

• all real numbers (addition, multiplication)
• all arrays (array concatenation)
• all strings (string concatenation)
• 1..12 (hour arithmetic)

"A rule for combining the things"...

• Numeric#+ (addition)
• Numeric#* (multiplication)
• Array#+ (array concatenation)
• String#+ (string concatenation)
• Hour#+ (hour arithmetic)

The Rules

"That rule obeys some meta rules"...

• our combination rule is associative
• a "unit" (or "zero") exists
• unit combine x = x (left identity)
• x combine unit = x (right identity)

Let's go through each of these meta rules.

Associativity

If you, like me, had forgotten the definition of math concepts from middle school like "associativity", Wikipedia says that the associative property means:

"[...] the order in which the operations are performed does not matter as long as the sequence of the operands is not changed."

If you go back through the Ruby snippets above, you'll see that the first pair of examples for each prove associativity for their respective combination rules.

"Unit" or "Zero"

"Unit" would be defined as follows:

• 0 (addition)
• 1 (multiplication)
• [] (array concatenation)
• "" (string concatenation)
• 12 (hour arithmetic)

... well, technically, Hour.new(12) for that last one, but you get the picture.

And looking back over each second pair of examples above, you'll see that these prove the existence of a unit, as well as left & right identity!

Cool. ... So what?

Well, now that we've noticed this commonality, let's work on abstracting things a bit.

Adding Abstraction

So let's say we have a bunch of alike things in hand, and we don't care what they are, we just want to combine them.

But what are they?

It doesn't matter! Just combine them, dammit!

Imagining a Array#combine that applies our combination rule to examples of the homogenous collections above, we'd want it to do this:

[1,2,3].combine
# => 6

[2,5,3].combine
# => 30

["foo","bar","baz"].combine
# => "foobarbaz"

[ [1,2], [3,4], [5,6] ].combine
# => [1, 2, 3, 4, 5, 6]

[ h6, h7, h8 ].combine.num
# => 9

But there's also the heterogeneous case:

[ 5, [], "asdf", Hour.new(5) ].combine
# ... BOOM

The rules we've discussed only make sense when thinking about a collection of things of the same type, so I can't think of path that makes sense here other than to throw, so that's what we'll do.

And since addition and multiplication both operate on numbers, we'll just arbitrarily pick multiplication as the combination method for Numeric.

Implemenation

So what's our plan here? Well, the first implemenation that came to mind for me was using Enumerable#reduce (also known as #inject), and it looks like this:

[1,2,3,4].reduce(1) {|prd, n| prd * n} # => 24
# [1,2,3,4]        # |  1, 1| ->  1
# [2,3,4]          # |  1, 2| ->  2
# [3,4]            # |  2, 3| ->  6
# [4]              # |  6, 4| -> 24

["a","b","c"].reduce("") {|str, ch| str + ch} # => "abc"
# ["a","b","c"]         # |"",   "a"| -> "a"
# ["b","c"]             # |"a",  "b"| -> "ab"
# ["c"]                 # |"ab", "c"| -> "abc"

The pattern here is identical, with the exception of two things:

1. the unit, our starting value (0 & "", respectively)
2. the method call for combining (* & +)

And while those method calls have special character operators, under the hood they're just message sends, so let's refactor to make that apparent, and our code more generic:

[1,2,3,4]     .reduce(1)  {|x, y| x.send(:*, y)} # => 24
["a","b","c"] .reduce("") {|x, y| x.send(:+, y)} # => "abc"

Making this pattern even more generic, we might write it as:

reduce(unit) {|x, y| x.send(combine_sym, y)}

That's the logic to generically combine our collections of things, so all we have left is to provide a means of figuring out unit and combine_sym (for our message send) based on the class of objects we have.

Here's my implementation of Array#combine for this:

PSA: Consider carefully before defining methods on standard library classes like Array. (Read: "Don't do this.")

class Array
  def combine
    ensure_combinable!
    reduce(unit) {|x, y| x.send(combine_sym, y)}
  end

private

  def unit
    case first
    when Integer then 1
    when Array then []
    when String then ""
    when Hour then Hour.new(12)
    else raise "Unsupported class for ##{__method__}: `#{first.class}`"
    end
  end

  def combine_sym
    case first
    when Integer then :*
    when Array then :+
    when String then :+
    when Hour then :+
    else raise "Unsupported class for ##{__method__}: `#{first.class}`"
    end
  end

  def ensure_combinable!
    raise "Cannot ##{__method__} members of empty Array" if empty?
    raise "Cannot ##{__method__} hetergeneous Array" unless homogenous?
  end

  def homogenous?
    map(&:class).uniq.count == 1
  end
end

And that does it!

It's worth noting that given Ruby's lack of a type system, it may be argued that defining unit isn't super helpful (since we could do this without unit and just by checking first in non-empty arrays), but in statically typed languages like Haskell, it can be quite useful, because it lets us do things with unit of the type we expect, even if the collection is empty. For example, when expecting a collection of Strings, we can get a "" even though our collection we're combining is [].

None of this is terribly important to grasp to get the intuition for these concepts, but if you happen to be thinking this is kind of unnecessary in practice in Ruby... I'll grant you that.

Our Discovery

So... what is this?

Well, it turns out that mathematicians (of the abstract algebraic persuasion) have a name for this thing: monoid.

Says Wikipedia:

In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element.

It's important to note that in this context "binary" here means "arity 2", as in "a function with 2 parameters", which is essentially what all of our combination methods (e.g. Numeric#*, String#+) are, if you think of these methods as functions with self as their "first parameter".

As for the "identity element", that's our unit.

So, as a Rubyist, the wording in this definition certainly feels a bit awkward, but it does perfectly describe what we've seen above!

To summarize things in plainer English, let's turn back to Brian Beckman's definition of a monoid from this YouTube video:

A "monoid" is...

• a collection of things
• plus a rule for combining the things
• and that rule obeys some meta rules

Coming soon...

So that's all well and interesting, but... so what?

Well, that's where we'll stop today, but as a teaser: there's another common thing that's monoidal that you probably wouldn't expect. There are also some pretty cool things we can do expounding on that fact.

... Next time!

Bonus

I didn't use it because it sort of obfuscates the usefulness of having a unit in our implementation, but there's also a shorthand in Ruby for doing the kind of #reduce we want:

[1,2,3,4].reduce(:+) # => 10

# works the same as if we pass this block...
[1,2,3,4].reduce(0) {|x, y| x.send(:+, y)} # => 10
# and uses the passed symbol here  ^^

Also, while looking through the Enumerable#reduce docs to figure out how this works without providing an initial value, I found this:

If you do not explicitly specify an initial value for memo, then the first element of collection is used as the initial value of memo.

This doesn't make use of a unit, but it does demonstrate part of the usefulness of a monoid: any arbitrary thing from the collection of things can be combined with any other, so we can just use the first thing in the collection as the starting point for combining all the things.

So, if you think about it, this shorthand for #reduce actually has a tacit expectation that the array it's acting on contains members of a monoid!

In fact, check it out:

[1, "2"].reduce :+
# TypeError: String can't be coerced into Integer

... I mean, you could argue that technically this has to do with duck-typing in Ruby, but regardless, the intent of the message sends inside of a #reduce block in this shorthand are almost certainly taking place to perform some sort of combining or accumulating, so it logically follows that it's almost certainly the members of a monoid that are being acted on.