Fractals and Monads — Part 1

A while back, I posted a bunch of fractal artwork that I did for fun, based on variations of the Koch snowflake; like this one, for example:

This is composed entirely of equilateral triangles, but it’s just one step in an iterated process leading to a fractal consisting of infinitely many Koch snowflakes at ever smaller scales.

I had a lot of fun coming up with designs like this, but actually I didn’t start out wanting to do new things with the Koch snowflake—that was just a fun tangent.  Originally, I was thinking about monads!

It’s high time I got back to what I was originally working on and explained what these fractals have to do with the “power set monad.”  To do that, I should probably start by explaining what the power set monad is.

For any set the power set is the set of all its subsets.  If you’ve ever studied any set theory, this should be familiar.  Unfortunately, a typical first course in set theory may not go into the how power sets interact with functions; this is what the “monad” structure of power sets is all about. This structure has three parts, each corresponding to a very common and important mathematical construction, but also so simple enough that we often use it without even thinking about it.

Let me finally say what the monad structure of power sets actually is.

First, mapping sets to their power sets is actually a functor:  For any function , there corresponds a function

which sends each element , i.e. each subset , to its image:

.

This makes a functor because the mapping of functions gets along nicely with identity functions and composition.   This functor is the first part of the power set monad.

You might be accustomed to writing the image of the set under simply as , rather than .  But here, we need to be more careful: despite its frequent use in mathematics,  is a notational abuse for which is the proper form.

To motivate the next piece in the power set monad, notice that there’s a strong sense in which is just an extension of , namely, on singleton sets, it essentially “is” :

.

This might make it tempting write for , as sort of “dual” version of the previous abuse of notation, though I don’t think anyone does that.

A better way to express how extends is to introduce the canonical map sending elements of to the corresponding singleton sets:

Then, the previous equation can be written , which is precisely the equation that makes a natural transformation. This natural transformation is the second piece in the monad structure.

Anyone who’s taught elementary set theory can attest that some students have a hard time at first making with conceptual distinction between elements and singleton subsets of a set.  Indeed, conflating the two is a very “natural” thing to do, which is why this is a natural transformation.

The last piece of the power set monad is another natural transformation. Much like , which formalizes a way to think of elements as being subsets, there is a natural transformation that lets us think of sets of subsets as being subsets.  This is given by, for each set , a map:

Here is the power set of the power set of , so an element of it is a sets of subsets of , and we turn this into a single subset by taking the union.

That’s it!  Or, almost.  To form a monad, the data must be compatible in such a way that these diagrams commute:

It’s a simple exercise to check that this is indeed the case.  You can extract the general definition of monad from what I’ve written here: you need an endofunctor on some category, and two natural transformations such that the diagrams analogous to those above commute.

Now let’s come back to fractals:

Many kinds of fractals are created by taking a simple shape, making multiple copies, transforming them somehow—for example, by shrinking or rotating—and then repeating.

For example, here’s one way to build a Sierpinski triangle, or rather its complement, staring from a single triangle and a rule for how triangles should “reproduce”:

If we look closely, we see that this process naturally involves ingredients from the power set monad.

In particular, the basic building block is the self-replication rule that we can write as a function

where is the set of triangles in the plane.  We won’t need an explicit formula for the function, since a picture suffices to explain what it does:

We can get all of the triangular holes in the Sierpinski triangle by “iterating” f. But, what does this mean exactly?  It would be nice if we could just do , but, strictly speaking, this doesn’t parse: we can’t feed a set of triangles into , since this is a function that expects a single triangle as input.

Fortunately, we know the solution to this problem: since , we can’t feed it into , but we can feed it into .  Good so far.

The problem with this is that again doesn’t live in , nor does it live in —it lives in :

It seems we would be doomed to march into ever more deeply-nested sets, were it not for the natural transformation .  Fortunately, using we get

So, now we can see the process of building a fractal as just repeatedly applying this function .

One last problem: What do we apply it to?  We want to apply it to our initial triangle , but that’s an element of , not .  Good thing we can think of this as an element of using the natural transformation !

So, here’s a recipe to build a wide variety of fractals, like some of the ones I’ve posted on this blog:

but also tons of others, using the power set monad:

1. Start with a replication rule on some set of “shapes.”
2. Pick a shape .
3. Feed your initial shape into to get the initial state.
4. Iterate feeding the current state into to get a new state, as many times as you want.

In fact, in calling this a “recipe,” I mean more than just an abstract mathematical recipe: this is essentially how I really drew all of those fractal pictures.  I generated them using Haskell—a functional programming language that knows about monads.  I didn’t use the power set monad, but rather Haskell’s built in “list monad,” which works very similarly.

Tags: Fractals, monads