PurelyFunctional.tv Newsletter 349: Tip: monoid pattern

Issue 349 - October 21, 2019 · Archives · Subscribe

Clojure Tip 💡

monoid pattern

Clojure, and many Lisps before it, has a way of representing monoids. Monoid is a mathematical term for an operation with two properties:

The operation has an identity, meaning a value that has no effect. For instance, the identity of addition is 0 because x + 0 = x

The operation's order of operations don't matter. For instance, the parentheses don't matter in this expression: 10 + 4 + 5. In other words, (10 + 4) + 5 = 10 + (4 + 5)

You can learn more about monoids in a podcast episode I recorded.

Addition of numbers is a monoid. Clojure represents this with 4 things:

=> (doc +)
-------------------------
clojure.core/+
([] [x] [x y] [x y & more])

1. There is the normal 2-argument version that adds them.
2. There is a 1-argument version that just returns its argument.
3. There is an n-argument version that adds all the arguments.
4. There is a 0-argument version that return the identity.

All of those are possible because it is a monoid.

Item #1 is just required. #2 is basically derived from the identity (+ 1 0) is the same as (+ 1). #3 is because it is associative and to alleviate the need for nesting parens. In many languages you would write 3 + 4 + 5 +10 which would turn into (+ 3 (+ 4 (+ 5 10))) without #3. #4 is a way to get at the identity value.

Note that they don't need to be implemented in exactly this way, but the behavior has to be there for the pattern to work.

We see this in other monoids. Multiplication of numbers is a monoid, and we see the same pattern:

=> (doc *)
-------------------------
clojure.core/*
([] [x] [x y] [x y & more])

And then there are other things that are monoids but that maybe it's not as obvious. Try running doc on each of these.

concat
str
comp
set/union

There are probably more.

Then there are some things which are technically monoids which don't have the pattern implemented correctly. For instance:

user=> (merge)
nil

Hash map merge is a monoid, so it should probably return an empty hash map. The other arities of merge are implemented correctly.

Takeaway

Consider if an operation you are writing is a monoid and try to implement the four arities of the monoid pattern. You're probably using and taking for granted lots of monoids in your software.

Why are monoids useful?

Because the order of operations (the parentheses) don't matter, you can break a problem up in basically arbitrary ways and still be able to put it back together. That means it can be parallelized very easily. Break a list in half, run work on each half-list in separate threads, and concatenate the results back together. This is what lets reducers so effectively use your cores.

But it goes further. This same property that lets it be put back together easily is useful even on a single thread. Monoids give you a lot of freedom in how you combine them, which lets you optimize design decisions. They also avoid an important corner case (like what to do with no values? just use the identity).

Conference alert 🚨

I booked my tickets to the 2019 Clojure/conj in Durham, North Carolina this week. If you're going, let me know! I haven't been to a conj in a couple of years and I'm really excited.

I'm also planning on attending a local Elixir conference (The Big Elixir) if you happen to be going to that. In that case, give me a holler!

Currently recording 🎥

I published two new lessons this week in the Property-Based Testing course.

1. Testing with Spec: functions---part two of the Clojure Spec integration. This time we look at how to build tests into the spec itself and what kinds of tests can't be in the spec.
2. When to test: during system design---we design a small system to make sending an email idempotent . We use PBT to make sure the invariants hold before we implement it. And our result is a model that that we can use to test our real system.

A note about the course

The course is way longer than I ever thought it would be. I'm committed to finishing it. However, once I'm done recording, I'm going to split it into at least two courses. It's just too long. The courses will probably be beginner/advanced, but I haven't decided yet. I don't know what lessons will go where. And don't worry, if you bought the course, you'll get both of the courses after the split.

Clojure Challenge 🤔

Last week's challenge

The challenge in Issue 348 was to write a function to run n tasks in parallel.

You can check out the submissions here.

This week's challenge

monoid pattern

It strikes me that you can generate functions that implement the monoid pattern knowing only two things: the identity value and the 2-arg case. The other two cases (n-arg and 1-arg) can be calculated for you.

Your task is to write a function that takes the identity and the 2-arg case and returns a new function that implements the monoid pattern.

(defn monoid [id fn-2]

I should be able to call it like this:

(monoid 0 (fn [a b] (+ a b)))

and get an addition monoid out.

As usual, please send me your implementations. I'll share them all in next week's issue. If you send me one, but you don't want me to share it publicly, please let me know.

Rock on!
Eric Normand