Catsters guide


In an attempt to solidify and extend my knowledge of category theory, I have been working my way through the excellent series of category theory lectures posted on Youtube by Eugenia Cheng and Simon Willerton, aka the Catsters.

Edsko de Vries used to have a listing of the videos, but it is no longer available. After wresting a copy from a Google cache, I began working my way through the videos, but soon discovered that Edsko’s list was organized by subject, not topologically sorted. So I started making my own list, and have put it up here in the hopes that it may be useful to others. Suggestions, corrections, improvements, etc. are of course welcome!

As far as possible, I have tried to arrange the order so that each video only depends on concepts from earlier ones. Along with each video you can also find my cryptic notes; I make no guarantee that they will be useful to anyone (even me!), but hopefully they will at least give you an idea of what is in each video.

I have a goal to watch two videos per week (at which rate it will take me about nine months to watch all of them); I will keep the list updated with new video links and notes as I go.

Posted in haskell, math, teaching | Tagged | 2 Comments

In defense of drawing by coding

Just some half-baked thoughts in repsonse to Bret Victor’s talk, Drawing Dynamic Visualizations (along with his addendum here). As usual, it is a fun and inspiring talk, so if you haven’t seen it I highly recommend it; but I will summarize it here.

He starts by surveying the state-of-the-art in options for the creative scientist who wants to visualize some data. The options he outlines are:

  1. Use some program like Excel which has a standard repertoire of graphs it can generate. The problem with this approach is that it completely stifles any creativity and freedom in visualizing data.

  2. Use a drawing program like Illustrator or Inkscape. This gives more freedom, of course, but the process is tedious and the results cannot easily be modified.

  3. The final option is to write some code in a framework like Processing or d3.js. The problem here, Victor says, is that you are just staring at a mass of symbols with no immediate, dynamic feedback.

He then goes on to demo a really cool prototype tool that allows drawing using a graphical interface, a bit like Illustrator or Inkscape. But the similarity is only surface deep: where those programs are restrictive and inflexible, Victor’s is richly interactive and editable. Instead of drawing concretely located lines, circles, and so on, it infers the relationships between things you are drawing, so updating the characteristics or positioning of one element automatically updates all the others which depend on it as well. In other words, one can construct a generic, editable visualization just by drawing one particular example of it.

Victor is quite negative about option (3) above—drawing by coding—referring to programming as “blindly manipulating symbols”: “blind” because you can’t actually see the picture you are creating while writing the program.

What I would like to point out is that in fact, despite his negativity about drawing by programming, when using his graphical tool Victor is still programming! It’s just that he has a graphical interface which allows him to construct certain sorts of programs, instead of writing the programs directly. In fact, you can see the programs he constructs on the left side of the screen in his tool. They appear to be structured imperative programs, consisting of sequences of drawing instructions together with things like loops and conditionals.

The problem is that this kind of higher-level interface cannot provide for all possible circumstances (unless you somehow make it Turing complete, but in that case it probably ceases to be at all intuitive). For example, Victor impressively drags and drops some spreadsheet data into his application. But what if I want to use data which is structured in some other format? What if I need to preprocess the data in some computationally nontrivial way? Or on the drawing end, what if I want to draw some shapes or compute some positions in a way that the interface does not provide for? We can’t completely get away from the need to write code in the service of visualization.

What we really need is a more inclusive idea of “programming”, and a continuum between direct manipulation of images and manipulation of symbols to produce images. Symbolic methods, of course, can be incredibly powerful—there is nothing inherently wrong with manipulating symbols.

More specifically, I am proposing something like the following:

  1. First, I am all for making elegant and powerful high-level graphical interfaces for constructing interactive, editable drawings—and not just drawings but code that generates drawings. This can probably be pushed quite far, and there is lots of HCI research to be done here. There are also some very interesting questions relating to bidirectional computation here: making an edit via the graphical interface corresponds to some sort of edit to the code; how can this be done in a sensible and consistent way?

  2. Recognizing, however, that sometimes you do need to actually write some code, how can we make the underlying language as beautiful as possible, and how can we make the interaction between the two systems (code and higher-level graphical interface) as elegant and seamless as possible? The ideal is for a user to be able to flow easily back and forth between the two modes, ideally spending much of their time in a high-level graphical mode.

Of course, if you hadn’t guessed by now, in the long term this is the sort of direction I would love to go with diagrams… though I need to finish my dissertation first (more on that subject soon).

Posted in diagrams | Tagged , , , , , , , | 3 Comments

Come visit the FARM!

Registration is now open for the first (!) ACM SIGPLAN Workshop on Functional Art, Music, Modeling and Design (FARM), to be held in Boston on September 28 (the day after ICFP). I’m really excited—it’s shaping up to be a really awesome event. Check out the list of accepted papers and demos:

  • Samuel Aaron and Alan F. Blackwell. From Sonic Pi to Overtone: Creative Musical Experiences with Domain-Specific and Functional Languages
  • Henrik Bäärnhielm, Mikael Vejdemo-Johansson and Daniel Sundström. Using Haskell as DSL for controlling immersive media experiences (Demo)
  • Guillaume Baudart, Louis Mandel and Marc Pouzet. Programming Mixed Music in ReactiveML
  • Jean Bresson, Raphael Foulon and Marco Stroppa. Reduction as a Transition Controller for Sound Synthesis Events
  • Kelsey D’Souza. PySTEMM – A STEM Learning Tool for Exploring and Building Executable Concept Models (Demo)
  • Andy Gill and Brent A. Yorgey. Functional active animation (Demo)
  • Jason Hemann and Eric Holk. Visualizing the Turing Tarpit
  • Paul Hudak. Euterpea: From Signals to Symphonies (Demo)
  • David Janin, Florent Berthaut, Myriam Desainte-Catherine, Yann Orlarey and Sylvain Salvati. The T-Calculus : towards a structured programing of (musical) time and space
  • David Janin and Florent Berthaut. LiveTuiles for tiled composition of audio patterns (Demo)
  • Thomas Jordan. Spontaneous Musical Explorations of Visible Symmetric Structures (Demo)
  • Hendrik Vincent Koops, José Pedro Magalhães and W. Bas de Haas. A Functional Approach To Automatic Melody Harmonisation
  • José Pedro Magalhães, Bas De Haas, Gijs Bekenkamp, Dion ten Heggeler and Tijmen Ruizendaal. Chordify: Chord Transcription for the Masses (Demo)
  • Donya Quick and Paul Hudak. Grammar-Based Automated Music Composition in Haskell
  • Chung‐chieh Shan and Dylan Thurston. Braiding in circles (Demo)

Note the early registration deadline is August 22, so don’t delay! In case you’re not already convinced, here’s a short description of the workshop and what it’s trying to accomplish:

The functional programming community is largely interested in writing beautiful programs. This workshop is intended to gather researchers and practitioners interested in writing beautiful programs that generate beautiful artifacts. Such artifacts may include visual art, music, 3D sculptures, animations, GUIs, video games, physical models, architectural models, choreographies for dance, poetry, and even physical objects such as VLSI layouts, GPU configurations, or mechanical engineering designs.

The goal of FARM is to gather together researchers, practitioners, and educators in this interdisciplinary field, as well as anyone else with even a casual interest in the area. We wish to share ideas, look for common ground, and encourage more activity. We also hope to legitimize work in the field and facilitate potential collaboration among the participants.

Posted in haskell | Leave a comment

FARM 2013: call for demonstration proposals

Do you enjoy writing beautiful code to produce beautiful artifacts? Have something cool to show off at the intersection of functional programming and visual art, music, sound, modeling, visualization, or design?

The deadline for submitting a paper has passed, but the Workshop on Functional Art, Music, Modeling and Design (FARM 2013) is currently seeking proposals for 10-20 minute demonstrations to be given during the workshop. For example, a demonstration could consist of a short tutorial, an exhibition of some work, or even a livecoding performance. Slots for demonstrations will be shorter than slots for accepted papers, and will not be published as part of the formal proceedings, but can be a great way to show off interesting work and get feedback from other workshop participants. A demonstration slot could be a particularly good way to get feedback on work-in-progress.

A demo proposal should consist of a 1 page abstract, in PDF format, explaining the proposed content of the demonstration and why it would be of interest to the attendees of FARM. Proposals will be judged on interest and relevance to the stated goals and themes of the workshop.

Submissions can be made via EasyChair.

Posted in meta | Tagged , , , , , , , , | Leave a comment

Workshop on Functional Art, Music, Modeling and Design

I’m helping organize a new workshop, FARM, to be held in Boston this September (right after ICFP). Many readers of this blog may have already seen the announcement, but I thought it worth saying a bit more about it here, in the spirit of trying to spread the word as widely as possible.

The short of it is—it should be super interesting and a lot of fun. If you are at all interested in the intersection of functional programming and design, art, music—anything that has to do with using beautiful code to produce beautiful artifacts—you should consider submitting a paper, or planning to attend! Papers can be submitted in two categories, full papers novel research contribution) and “aesthetic applications” (which should describe some sort of beautiful way to produce something beautiful). The deadline for submissions is June 14. See the website for more details.

Posted in meta | Tagged , , , , , , , , | 2 Comments

Monad transformers: a cautionary tale

When writing the code in my previous post, I wanted to have a monad which combined the ability to generate random numbers with the ability to fail. Naturally, I decided to use RandT Maybe. But when I tried to write a failing computation of this type, I got a type error:

    No instance for (MonadPlus (RandT StdGen Maybe))
      arising from a use of `mzero'

It seems that no one ever bothered to add a MonadPlus instance for RandT. Well, that’s easy to fix. Since RandT is just a newtype wrapper around StateT we can even derive a MonadPlus instance automatically using -XGeneralizedNewtypeDeriving. So I modified the MonadRandom package, and everything worked great.

…That is, everything worked great until I started to get some strange behavior—sometimes computations would hang when I expected them to complete quickly. I finally was able to boil it down to the following minimal example. foo succeeds or fails with equal probability; bar reruns foo until it succeeds.

foo :: RandT StdGen Maybe ()
foo = do
  r <- getRandomR (0,1)
  if r < 1/2 then return () else mzero

bar :: RandT StdGen Maybe ()
bar = foo `mplus` bar

Seems straightforward, right? bar should always succeed pretty much instantly, since there’s only a 1/2^n chance that it will have to call foo n times.

However, this is not what happens: some of the time bar returns instantly as expected, and some of the time it hangs in what seems like an infinite loop! What gives?

Have you figured it out yet? (If you like these sorts of puzzles you might want to stop and see if you can figure out what was going on.) The problem is that the mplus operation for RandT StdGen Maybe runs both of its arguments with the same random seed! In other words, when a computation fails the generator state gets thrown away. And if we think about how monad transformers work this is actually not surprising. We have the following isomorphisms:

   RandT StdGen Maybe ()
== StateT StdGen Maybe ()
== StdGen -> Maybe ((), StdGen)

So when a computation fails you just get Nothing—in particular you don’t get to see what the new StdGen value would have been, so you can’t (say) pass it along to the second argument of mplus. The upshot is that bar succeeds if the first call to foo happens to succeed; otherwise it simply keeps calling foo with the exact same seed and foo keeps failing every time.

The general principle here is that “the effects of inner monad transformers take precedence over the effects of outer transformers”—in this case the failure effect of the inner Maybe takes precedence and causes the random generator state to be lost.

So what I really wanted was MaybeT (Rand StdGen), which—after adding a MonadRandom instance for MaybeT, now released as MonadRandom-0.1.9—works perfectly.

The moral of the story: monad transformers aren’t (in general) commutative! Think carefully about what order you want. (I actually wrote about this once before; you’d think I would have learned my lesson.)

Posted in haskell | Tagged , , , | Leave a comment

Random binary trees with a size-limited critical Boltzmann sampler

Today I’d like to talk about generating random trees. First, some imports and such (this post is literate Haskell).

> {-# LANGUAGE GeneralizedNewtypeDeriving #-}
> module BoltzmannTrees where
> import           Control.Applicative
> import           Control.Arrow                  ((&&&))
> import           Control.Lens                   ((??))
> import           Control.Monad.Random
> import           Control.Monad.Reader
> import           Control.Monad.State
> import           Control.Monad.Trans.Maybe
> import           Data.List                      (sort)
> import           Data.Maybe                     (fromJust)
> import           System.Environment             (getArgs)

So here’s a simple type of binary tree shapes, containing no data:

> data Tree = Leaf | Branch Tree Tree
>   deriving Show

We’ll count each constructor (Leaf or Branch) as having a size of 1:

> size :: Tree -> Int
> size Leaf = 1
> size (Branch l r) = 1 + size l + size r

Now, suppose we want to randomly generate these trees. This is an entirely reasonable and useful thing to do: perhaps we want to, say, randomly test properties of functions over Tree using QuickCheck. Here’s the simplest, most naïve way to do it:

> randomTree :: (Applicative m, MonadRandom m) => m Tree
> randomTree = do
>   r <- getRandom
>   if r < (1/2 :: Double)
>     then return Leaf
>     else Branch <$> randomTree <*> randomTree

We choose each of the constructors with probability 1/2, and recurse in the Branch case.

Now, as is well-known, this works rather poorly. Why is that? Let’s generate 100 random trees and print out their sizes in descending order:

ghci> reverse . sort . map size <$> replicateM 100 randomTree

As you can see, this is a really weird distribution of sizes. For one thing, we get lots of trees that are very small—in fact, it’s easy to see that we expect about 50 of them to be single leaf nodes. The other weird thing, however, is that we also get some really humongous trees. The above output gets randomly regenerated every time I process this post—so I don’t know exactly what sizes you’ll end up seeing—but it’s a good bet that there is at least one tree with a size greater than 10^4. To get an intuitive idea of why this happens, imagine generating the tree in a breadth-first manner. At each new level we have a collection of “active” nodes corresponding to pending recursive calls to randomTree. Each active node generates zero or two new active nodes on the next level with equal probability, so on average the number of active nodes remains the same from level to level. So if we happen to make a lot of Branch choices right off the bat, it may take a long time before the tree “thins out” again. And if this distribution didn’t seem weird enough already, it turns out (though it is far from obvious how to prove this) that the expected size of the generated trees is infinite!

The usual solution with QuickCheck is to use the sized combinator to limit the size of generated structures, but this does not help with the problem of having too many very small trees.

Here’s a (seemingly!) stupid idea. Suppose we want to generate trees of size approximately 100 (say, within 10%). Let’s simply use the above algorithm, but with the following modifications:

  1. If we generate a tree of size < 90, throw it away and start over.
  2. If we generate a tree of size > 110, throw it away and start over. As an optimization, however, we will stop as soon as the size goes over 110; that is, we will keep track of the current size while generating and stop early if the size gets too big.

Here’s some code. First, a monad onion:

> newtype GenM a = GenM 
>     { unGenM :: ReaderT (Int,Int) (StateT Int (MaybeT (Rand StdGen))) a }
>   deriving (Functor, Applicative, Monad, MonadPlus, MonadRandom,
>             MonadState Int, MonadReader (Int,Int))

The ReaderT holds the min and max allowed sizes; the StateT holds the current size; the MaybeT allows for possible failure (if the tree gets too big or ends up too small), and the Rand StdGen is, of course, for generating random numbers. To run a computation in this monad we take a target size and a tolerance and use them to compute minimum and maximum sizes. (The (??) in the code below is an infix version of flip, defined in the lens package.)

> runGenM :: Int -> Double -> GenM a -> IO (Maybe a)
> runGenM targetSize eps m = do
>   let wiggle  = floor $ fromIntegral targetSize * eps
>       minSize = targetSize - wiggle
>       maxSize = targetSize + wiggle
>   g <- newStdGen
>   return . (evalRand ?? g) . runMaybeT . (evalStateT ?? 0)
>          . (runReaderT ?? (minSize, maxSize)) . unGenM
>          $ m

Here’s the code to try generating a tree: we call the atom function to record the increase in size, and choose between the two constructors with equal probability. atom, in turn, handles failing early if the size gets too big.

> genTreeUB :: GenM Tree
> genTreeUB = do
>   r <- getRandom
>   atom
>   if r <= (1/2 :: Double)
>     then return Leaf
>     else Branch <$> genTreeUB <*> genTreeUB
> atom :: GenM ()
> atom = do
>   (_, maxSize) <- ask
>   curSize <- get
>   when (curSize >= maxSize) mzero
>   put (curSize + 1)

genTreeLB calls genTreeUB and then performs the lower bound check on the size.

> genTreeLB :: GenM Tree
> genTreeLB = do
>   put 0
>   t <- genTreeUB
>   tSize <- get
>   (minSize, _) <- ask
>   guard $ tSize >= minSize
>   return t

Finally, genTree just calls genTreeLB repeatedly until it succeeds.

> genTree :: GenM Tree
> genTree = genTreeLB `mplus` genTree

Let’s make sure it works:

ghci> map size . fromJust <$> runGenM 100 0.1 (replicateM 30 genTree)

Neat! Okay, but surely this is really, really slow, right? We spend a bunch of time just throwing away trees of the wrong size. Before reading on, would you care to guess the asymptotic time complexity to generate a tree of size n using this algorithm?

And while you think about that, here is a random binary tree of size approximately 1000.

And the answer is… it is linear! That is, it takes O(n) time to generate a tree of size n. This is astounding—it’s the best we could possibly hope for, because of course it takes at least O(n) time to generate an object of size O(n). If you don’t believe me, I invite you to run some experiments with this code yourself. I did, and it sure looks linear:

main = do
  [sz] <- getArgs
  Just ts <- runGenM (read sz) 0.1 $ replicateM 1000 genTree
  print . (/fromIntegral n) . fromIntegral . sum . map size $ ts

archimedes :: research/species/boltzmann » time ./GenTree 50
./GenTree 50  1.37s user 0.01s system 99% cpu 1.387 total
archimedes :: research/species/boltzmann » time ./GenTree 100
./GenTree 100  3.11s user 0.02s system 99% cpu 3.152 total
archimedes :: research/species/boltzmann » time ./GenTree 200
./GenTree 200  6.82s user 0.04s system 99% cpu 6.876 total
archimedes :: research/species/boltzmann » time ./GenTree 400
./GenTree 400  13.08s user 0.08s system 99% cpu 13.208 total
archimedes :: research/species/boltzmann » time ./GenTree 800
./GenTree 800  25.99s user 0.16s system 99% cpu 26.228 total

The proof of this astounding fact uses some complex analysis which I do not understand; I wish I was joking. Of course, the constant factor can be big, depending on how small you set the “epsilon” allowing for wiggle room around the target size.1 But it is still quite feasible to generate rather large trees (with, say, 10^5 nodes).

There is much, much more to say on this topic. I just wanted to start out with a simple example before jumping into more of the technical details and generalizations, which I plan to write about in future posts. I also hope to package this and a bunch of other stuff into a library. In the meantime, you can read Duchon et. al2 if you want the details.

  1. Actually, if you set epsilon to zero, the asymptotic complexity jumps to O(n^2).

  2. Duchon, Philippe, et al. “Boltzmann samplers for the random generation of combinatorial structures.” Combinatorics Probability and Computing 13.4-5 (2004): 577-625.

Posted in combinatorics, haskell, math, species | Tagged , , , , , | 11 Comments