Last time I discussed the power set monad and how it shows up in certain methods of building fractals. This time I’ll go a bit further, and also explain some Haskell code I actually use to generate fractal pictures like this:
To do this, I’ll introduce Kleisli categories, the list monad, and a bit about how monads work in Haskell!
Recall we were considering fractals that can be built using a “replication” function
on some set of “shapes” . As an example, we had considered a map that takes any triangle in the plane to sets of three new triangles as shown here:
and we noted that “iterating” this map indefinitely gives us all of the triangular “holes” in a Sierpinski triangle:
I also described how iterating this map, if we do everything carefully, involves the structure of the power set monad.
In fact, considering maps like leads us directly to the “Kleisli category” associated to the power set monad. I want to explain this here, because in computer science people actually tend to think of monads essentially in terms of their associated Kleisi categories, and that’s how monads are implemented in Haskell.
Every monad has an associated Kleisli category, but since I’ve been working with the power set monad in the category of sets, I’ll start with that special case.
First, in the Kleisli category, which we’ll denote , the objects are the same as the original category
: they’re just sets. A morphism from the set
to the set
, however, is a function
For now, at least, I’ll avoid making up any special notation for morphisms in the Kleisli category, and instead freely regard either as a morphism from
to
in the category
of sets, or as a morphism from
to
in the Kleisli category
; these are really the same thing. If this is confusing, whenever you’re thinking of
as a morphism in the Kleisli category, just think of the
as decoration on the arrow , rather than on the codomain object
.
Given two functions and
, the Kleisli composite
is defined by
Checking the domain and codomain of each of the functions on the right, we can see that this indeed gives a morphism from to
in the Kleisli category:
You can check that is associative, and that the maps
are identity morphisms, so we really do get a category. That’s all there is to the Kleisli category.
Returning to the sort of function we had been considering for generating fractals:
these are clearly just endomorphisms in the Kleisli category. This also makes it clear what we mean by “iterating” such a function: it’s an endomorphism, so we can just compose it with itself as many times as we want. In particular, analogously to how we define “powers” of ordinary functions by repeated composition, we can define the nth Kleisli power of recursively by
That is, the 0th power of is the identity, while the nth power of is the Kleisli composite of
with its (n-1)st power.
For example, consider the set of all equilateral triangles in the plane and consider the map
defined so that
has six elements, each 1/3 the size of, and linked together around the boundary of the original triangle
, as shown here:
Then, starting with an arbitrary triangle the images under successive Kleisli powers of the generating endomorphism:
look like this:
Some Haskell
Let’s do some Haskell—If you don’t know Haskell, don’t worry; I’ll explain what everything means. If you do know Haskell, this will be super easy, perhaps even obvious, though I may write things in ways you won’t expect, since I’m transitioning over from the categorical definition of monad, rather than diving in with how monads are actually defined in Haskell.
The code we really need is almost embarrassingly short, mainly because monads are extremely well suited to the task at hand. What we need most is just to be able to compute Kleisli powers!
Here’s how the formula for the Kleisli power of an endomorphism becomes a function in Haskell:
import Control.Monad kpow :: Monad m => Int -> (a -> m a) -> a -> m a kpow 0 _ = return kpow n f = f <=< kpow (n-1) f
Let’s go through this line by line.
The first line just loads some tools for working with monads; there’s not much I need to say about that now.
The next line is the first one of real content; it’s the “type signature” of the function “kpow”. The first bit, Monad m
, just says that m
is any monad; Haskell knows about several monads, and you can also define your own. Then, the rest of that line:
Int -> (a -> m a) -> a -> m a
can be interpreted as declaring that we have a function that takes one integer (Int
), the “power,” and one element of , (i.e. something of type
a -> m a
), and gives us another element of . So if I were to write this line in standard mathematical notation, I would write:
where is any monad, and
is any type. We take an integer and a Kleisli endomorphism for the monad m, and return another endomorphism. Notice there’s a slight discrepancy here, in that an
Int
is any integer, whereas I used the natural numbers . But the integer really is intended to be non-negative. If you fed a negative integer into
kpow
, the recursion would never terminate; so, my code doesn’t forbid it, but you shouldn’t do it.
The last two lines of the code give the actual formula for the Kleisli power. If you just look at my earlier formula:
and compare this to these two lines:
kpow 0 _ = return kpow n f = f <=< kpow (n-1) f
you can probably figure out all of the Haskell syntax just by matching up symbols.
The first line says “whenever the first argument of kpow
is 0, the result is “return
.” This may be confusing if you’re used to how the keyword “return” is used in many other programming languages. Sorry; it’s not my fault! In Haskell “return
” means “ for any object
“, where the objects in this case are always data types.
The second line says “the nth Kleisli power of f is the composite of f with the (n-1)st power of f”, just as in the other formula. You probably guessed that the Kleisli composite is written
f <=< g
in Haskell.
Here’s a dictionary relating the notation I’ve been using to Haskell notation for the same thing:
I didn’t need to use , a.k.a.
join
explicitly in the definition of Kleisli powers, since it’s already wrapped into the definition of Kleisli composition.
List monad
To do some examples I’ll use the list monad, which is a built-in monad in Haskell. This is very much like the power set monad, since “lists” are like sets in many ways, so I can introduce this pretty quickly. We really just need a very basic idea of how the list monad works.
A “list” of elements of “type” can be written written simply as
for a finite list, or for an infinite list.
Making lists of elements of a given type clearly gives a functor analogous to the power set functor: for any function we get a function that just acts element-wise on lists:
mapping a list of elements of type into a list of elements of type
.
Based on what we’ve done with sets, you can probably guess how the two natural transformations in the list monad work, too.
First, any single item can be regarded as a list with only one item on it, so
In Haskell, for example, you could take an element of type Int
, say the integer 5, and turn it into a list of integers by using return 5
. As long as Haskell has a context to know it is working in the list monad rather than some other monad, this will output [5]
. Voilà!
Second, the natural transformation turns lists of lists into lists. If you’ve got a list of to-do lists, you can always turn it into a single list by first writing down the items on the first list, in order, then continuing with the items on the second list, and so on.
In Haskell, If you enter join [[1,2,3],[4,5]]
, you’ll get [1,2,3,4,5]
as output. That’s .
There’s one noteworthy subtlety, which is that infinite lists are also allowed. So, if you have a list of lists:
[Fun stuff to do, Work to do]
and the first item happens to be an infinite list, then if you try joining these lists up into one in the way I described, you’ll never get to any items on the second list. This is one way in the list monad differs from
in the power set monad: In the former, as soon as one of the lists is infinite, everything after that gets thrown away. This last part is not obvious; you certainly could devise ways to join a list of infinite lists together and include all of the items, but that’s not how things work in this monad.
You can easily work out how Kleisli composition works from this, so we’ve now got everything we need.
Cantor set in the List Monad.
Let’s do an example: the Cantor set. I’ll represent closed intervals on the real line by ordered pairs in Haskell. So, when I write (0.3, 1.5)
, I mean the set . I know, round brackets for closed intervals is weirdly non-standard, but in Haskell, square brackets are reserved for lists, and it’s better to keep things straight.
To generate the Cantor set, all we need is the Kleisli endomorphism in the list monad that describes the general step. This can be defined by a one-line Haskell function:
f (p,q) = [(p, p + (q-p)/3), (q-(q-p)/3, q)]
If we apply this to the unit interval (0, 1)
, here’s what we get:
[(0.0,0.3333333333333333),(0.6666666666666667,1.0)]
So this works: it’s mapping the closed interval to a list of two closed intervals:
and
.
Now we can compute any step in the construction of the Cantor set by computing Kleisli powers. Let’s just do one. Once you’ve loaded the function kpow
, enter this in Haskell:
kpow 3 f (0,1)
and—kapow!—you’ll get this output:
[(0.0,3.7037037037037035e-2), (7.407407407407407e-2,0.1111111111111111), (0.2222222222222222,0.25925925925925924), (0.2962962962962963,0.3333333333333333), (0.6666666666666667,0.7037037037037037), (0.7407407407407408,0.7777777777777778), (0.888888888888889,0.9259259259259259), (0.962962962962963,1.0)]
Ugly isn’t it? But convert to fractions and you’ll see this is doing just the right thing.
I’ll do more examples in the next post.