foldr is made of monoids

> import Data.Monoid

In his recent blog post What is foldr made of?, Tom Ellis made the clever observation that foldr is equivalent in power to the combination of map and compose, where

> compose :: [a -> a] -> a -> a
> compose []     = id
> compose (f:fs) = f . compose fs

We can then write

> foldr' :: (a -> b -> b) -> b -> [a] -> b
> foldr' g z xs = compose (map g xs) z

which (as Tom proves) is exactly equivalent to the usual foldr.

This is a really neat idea which I don’t remember ever seeing before. But now that I have, I realized that I could expand on it a bit—compose doesn’t come out of thin air quite as much as it might first appear.

Consider the standard function mconcat (from Data.Monoid), which combines a list of values from some Monoid:

mconcat :: Monoid m => [m] -> m
mconcat []     = mempty
mconcat (m:ms) = m `mappend` mconcat ms

I claim that in the presence of map, compose and mconcat are equivalent. Why is that? First, it’s easy to see that compose can be implemented in terms of mconcat—we just instantiate it to the monoid of endofunctions (where mempty = id and mappend = (.)), with a little bit of syntactic noise due to the need to convert in and out of the Endo newtype:

> compose' :: [a -> a] -> a -> a
> compose' = appEndo . mconcat . map Endo

Proving that compose' is the same as compose is not hard; I leave it to you as an exercise.

Implementing mconcat in terms of compose is a bit more interesting:

> mconcat' :: Monoid m => [m] -> m
> mconcat' = ($mempty) . compose . map mappend

The key idea is that we can turn any value from some monoidal type m into a function m -> m by partially applying mappend; composing these functions then corresponds to combining the original values, and the final value can be recovered by applying the resulting function to mempty.1 That is,

m_1 \diamond m_2 \diamond \dots \diamond m_n = ((m_1 \diamond) \circ (m_2 \diamond) \circ \dots \circ (m_n \diamond))\ \varepsilon

(where I have used \diamond and \varepsilon to represent mappend and mempty, respectively). Written out this way, I hope you can see why the equality holds by thinking about what the composition on the right evaluates to (and remembering the right identity law, x \diamond \varepsilon = x).

So we can also say that foldr = map + mconcat! This gets at the idea that lists are free (or initial) monoids, which intuitively means that of all monoids, they “preserve the most information”—up to the monoid laws, combining lists preserves all the information about the original lists and how you have combined them. This also means that there is a canonical way to “convert” a list into any other Monoid: that is, given a mapping f :: a -> m, there is a canonical way to take a list [a] and turn it into an m, namely, mconcat . map f.

Let’s make the connection to foldr even more explicit. First, let’s swap around the order of arguments and add some parentheses which aren’t strictly necessary:

foldr'' :: (a -> (b -> b)) -> [a] -> (b -> b)

Hmm, b -> b… why does this look so familiar? I claim we can actually pull a similar trick2 as with compose/mconcat, and replace b -> b with Monoid m => m to come up with a function equivalent to foldr'' (and hence foldr as well):

fold :: Monoid m => (a -> m) -> [a] -> m

Hmm, so how would this be implemented? Let’s see…

> fold :: Monoid m => (a -> m) -> [a] -> m
> fold f = mconcat . map f

So actually, fold itself (and hence, equivalently, foldr) is the canonical mapping from a list down to any monoid which I mentioned earlier! And here we can see quite directly that fold is indeed equivalent to mconcat + map.

In summary: foldr is equivalent to map plus compose/mappend, because lists are free monoids.


  1. Incidentally, this amounts to saying that mappend itself is a monoid homomorphism (a structure-preserving map between monoids), and this is where difference lists come from. For more, see my recent paper, Monoids: Theme and Variations.

  2. I leave this as an exercise too.

Posted in haskell, math | Tagged , , , , | 15 Comments

Using multiple versions of GHC in parallel with GNU stow

Do any of the following apply to you?

  • You sometimes hack on GHC.
  • You sometimes want to try out an unreleased GHC version.
  • You maintain a library and want to make sure it builds with several different versions of GHC.
  • You want to try out a newly released version of GHC but without blowing away your existing (working!) GHC install.

As you can see, these are roughly in order from most to least “hard core”, and I expect that the last two are fairly common, even if the first two are not. The common thread, of course, is having multiple versions of GHC installed simultaneously.

The solution

A solution that I’ve found which works quite well (on Linux, and I expect it would work on OSX as well) and deserves to be better known is GNU stow. Here’s how it works: instead of installing things directly in /usr/local (or $HOME/local, or whatever), you instead install in sandboxed locations like /usr/local/stow/ghc-7.6.1. You then tell stow that you want to “install” ghc-7.6.1, and it creates all the necessary symlinks to mirror the directory structure under the ghc-7.6.1 directory into /usr/local. But of course it tracks everything so that you can easily uninstall all these symlinks as well. (And yes, it’s smart about symlinking an entire directory when possible, instead of all the individual files, and later “splitting up” such big-scale links when necessary.)

The pros of this sort of scheme should be clear:

  1. Once you’ve “installed” a particular version you just use it as normal—no need to pass the right directories as flags to tools like cabal or ghc-pkg.
  2. Switching to a different version of GHC is relatively quick (see below).
  3. Installing new versions is pain-free; it’s just as easy to have twenty different versions as it is to have two.

Of course, there are a few downsides as well:

  1. Trusting a Perl script to munge your /usr/local. (Though for what it’s worth, I have been using it heavily for about a year now—I currently have six different versions of GHC installed—and have never once encountered a single problem.)
  2. You can’t use several versions of GHC at once—there is always exactly one “current” version. So if you want to, e.g., do test builds of a library under several versions of GHC in parallel, you need a different solution.

A step-by-step guide

So here’s how this works in more detail. First, of course, you have to install stow itself; I’ll assume you can get it from your OS package manager or know how to build it from source. What you get is simply an executable called stow.

Now, when installing GHC (whether a binary distribution or from source), give the configure step an extra prefix argument, for example:

./configure --prefix=/usr/local/stow/ghc-7.6.1

Just take the directory where you would usually install GHC, and add stow and then an additional subdirectory for the particular version you are installing. This directory doesn’t have to already exist; the installer will create it if it doesn’t.

(Note that if you already have GHC installed, you’ll have to uninstall it first and then reinstall it with stowstow won’t work unless it can manage all your GHC installs.)

After the installation process completes, you have an unusable ghc because, of course, .../stow/ghc-7.6.1 isn’t on any relevant paths. All you have to do to finish installing it is

cd /usr/local/stow && stow ghc-7.6.1

This instructs stow to make symlinks into ghc-7.6.1 from /usr/local. After this completes, that’s it! You can use your new GHC as usual.

To uninstall, follow the same procedure but give stow the -D option:

cd /usr/local/stow && stow -D ghc-7.6.1

To switch from one version of GHC to another just uninstall the current version and then install the new one. I actually have a script which automates this process: it looks in the stow directory to see which versions are availble, prompts me to choose one from a list, then uninstalls the current version (obtained with ghc --numeric-version) and installs the newly selected version. On my laptop this process takes just a couple seconds.

That’s it! Happy stowing!

Posted in haskell | Tagged , , , | 10 Comments

Decomposing data structures

So, what are combinatorial species? As a very weak first approximation, you can think of them as a generalization of algebraic data types.1 That doesn’t really say much about what they are, but at least it does explain why programmers might be interested in them.

The goal of species is to have a unified theory of structures, or containers. By a structure we mean some sort of “shape” containing locations (or positions). Here are two different structures, each with eight locations:

One thing that’s important to get straight from the beginning is that we are talking about structures with labeled locations. The numbers in the picture above are not data being stored in the structures, but names or labels for the locations. To talk about a data structure (i.e. a structure filled with data), we would have to also specify a mapping from locations to data, like \{ 0 \mapsto \texttt{'s'}, 1 \mapsto \texttt{'p'}, 2 \mapsto \texttt{'e'} \dots \}

Now go reread the above paragraph! For programmers I find that this is one of the most difficult things to grasp at first—or at least one of the things that is easiest to forget. The fact that the labels are often natural numbers (which are often also used as sample data) does not help.

One useful intuition is to think of the labels as memory addresses, which point off to some location where a data value is stored. This intuition has some particularly interesting consequences when we get to talking about operations like Cartesian product and functor composition, since it gives us a way to model sharing (albeit only in limited ways).

Why have labels at all? In the tree shown above, we can uniquely identify each location by a path from the root of the tree, without referencing their labels at all. However, the other structure illustrates one reason why labels are needed. The circle is supposed to indicate that the structure has rotational symmetry, so there would be no way to uniquely refer to any location other than by giving them labels.

The idea of decomposing data structures as shapes with locations combined with data is not unique to species. In the computer science community, the idea goes back, I think, to Jay and Cockett (1994) in their work on “shapely types” (their “locations” are always essentially natural numbers, since they work in terms of shapes and lists of data) and more recently Abbott, Altenkirch, and Ghani (2003) with their definition of “containers” (which, like the theory of species, has a much more general notion of locations). However, it should be noted that the literature on species never actually talks about mappings from labels to data: combinatorialists don’t care about data structures, they only care about structures!

Now that we have some motivation, and with the requisite disclaimers about labels out of the way, in my next post I’ll motivate and explain the formal definition of species.

References

Abbott, Michael, Thorsten Altenkirch, and Neil Ghani. 2003. “Categories of Containers.” In Foundations of Software Science and Computation Structures, 23–38. http://dx.doi.org/10.1007/3-540-36576-1_2.

Jay, C. Barry, and J. Robin B. Cockett. 1994. “Shapely Types and Shape Polymorphism.” In ESOP ’94: Proceedings of the 5th European Symposium on Programming, 302–316. London, UK: Springer-Verlag.

Posted in math, species | Tagged , , , | 9 Comments

And now, back to your regularly scheduled combinatorial species

I’ve already mentioned this to people here and there, but haven’t yet announced it publically, so here it is: Stephanie Weirich and I have been awarded a grant from the NSF to study the intersection of combinatorial species and (functional) programming, and so I’ll be returning the topic for my dissertation.

I’ve always found blogging to be an excellent way to organize my thoughts, and it often prompts great feedback and insights from readers which fuel further exploration. So as one aspect of my research, I plan to write a series of blog posts explaining the theory of combinatorial species and its relationship to algebraic data types. I’ll start with the very basics and (hopefully) progress to some deeper results, pulling together references to related things along the way.

I’ve written about species on this blog before (here, here, here, here, and here), and I published a paper in the 2010 Haskell Symposium on the topic, so I’ll certainly end up duplicating some of that content. But it’s worth starting over from the beginning, for several reasons:

  • I want as many people as possible to be able to follow along, without having to tell them “first go back and read these blog posts from 2009”.
  • I’m not completely happy with the way I presented some of that material in the past; in the intervening years I feel I’ve had some better insights into how everything fits together.
  • Those previous posts—and my Haskell Symposium paper—conflated explaining species with explaining my Haskell library for computing with species,1 which I now think is not all that helpful, because it glosses over too many subtle issues with the relationship of species to algebraic data types.

So, in my next post, I’ll begin by defining species—but with some extra context and insight that I hope you’ll find enlightening, even if you already know the definition.


  1. It’s on Hackage here, but I haven’t touched it in a long time and it doesn’t build with recent versions of GHC. I plan to fix that soon.

Posted in combinatorics, math, writing | Tagged , | 10 Comments

FogBugz, Beeminder, and… pure functions in the cloud?

For a number of years now, I’ve used a free personal instance of FogBugz to track everything I have to do. At any given time I have somewhere between 50-150 open tickets representing things on my to-do list, and over the last four years I have processed around 4300 tickets. This has been immensely successful at reducing my stress and ensuring that I don’t forget about things. However, it’s been somewhat less successful at actually getting me to do stuff. It’s still all too easy to ignore the really important but intimidating tickets, or at times to simply ignore FogBugz altogether.

Just last week, I discovered Beeminder. I’ve only been using it a week, but early indications are that it just might turn out to be as revolutionary for my productivity as FogBugz was. The basic idea is that it turns long-term goals into short-term consequences. You set up arbitrary quantifiable goals, and Beeminder tracks your progress over time and takes your money if you get off track—but you get to set the amount, and in fact it’s completely free until the second time you fail at a particular goal. In fact I haven’t even pledged any money for any of my goals; just the threat of “losing” has been enough to motivate me so far. (In fact, I’m writing this blog post now because I made a goal to write two blog posts a week, and by golly, if I don’t write a new post by tomorrow I’m going to LOSE!)

So, two great tastes that taste great together, right? I could make Beeminder goal(s) to ensure that I close a certain number of tickets per week, or a certain number of high-priority tickets, or a certain number of tickets with a given tag, or whatever seems like it would be helpful. Beeminder has a nice API for entering data, and FogBugz comes with a “URL trigger” plugin which can automatically create GET or POST requests to some URL upon certain events (such as closing a ticket matching certain criteria). The URL trigger plugin lets you construct an arbitrary URL using a list of special variables which get filled in with values from the given ticket. So I can just trigger a POST to the Beeminder URL for entering a data point, and give it arguments indicating the timestamp of the ticket event and a comment with the name of the ticket.

No problem, right?

Well… almost. There’s just one tiny catch. You see, FogBugz outputs timestamps in the format YYYY-MM-DD HH:MM:SS… and Beeminder expects a number of seconds since the epoch. Argggh!

I want to just plug in a little function in the middle to do the conversion. But both the FogBugz and Beeminder APIs are running on remote servers that I have no direct control over. I’d have to somehow send the FogBugz POST to some other server that I do control, munge the data, and forward it on to Beeminder. But setting this up from scratch would be a lot of work, not to mention the expense of maintaining my own server.

Here’s what I really want: a website where I can somehow write my function in a little domain-specific language, and get a URL where I can point FogBugz, which would cause my function to run on the timestamp and the result forwarded appropriately to Beeminder. Of course there are issues to be worked out with security, DOS attacks, and so on, but it seems to me it should be possible in principle.

Does something like this already exist? If not, why not? (And how hard would it be to build one using all the great Haskell tools for web development out there? =) It seems to me that the ability to write “glue” code like this to sit in between various APIs is becoming quite important.

Posted in meta | Tagged , , , , , , , | 16 Comments

Creating documents with embedded diagrams

If you read my recent post about type algebra, you may have wondered how I got all those nice images in there. Surely creating the images and then inserting them into the post by hand would be rather tedious! Indeed, it would be, but that’s not what I did. I’m quite pleased to announce the release of several tools for making this sort of thing not only possible but even convenient.

Behind it all is the recently released diagrams-builder package. Diagrams backends such as diagrams-cairo give you a static way to render diagrams. diagrams-builder makes the process dynamic: it can take arbitrary snippets of Haskell code, merge them intelligently, and call out to hint to render a diagram represented by some Haskell expression.

As a specific application of diagrams-builder, I’ve released BlogLiterately-diagrams, a diagrams plugin for BlogLiterately. This is what I used to produce the type algebra post. The entire post was written in a single Markdown document, with inline diagrams code in specially marked code blocks. BlogLiterately-diagrams handles compiling those code blocks and replacing them with the generated images; BlogLiterately automatically uploads the images to the server. For example, including

```{.dia width='200'}
sq = square 1

foo 0 = sq
foo n = ((foo' ||| sq') === (sq' ||| foo')) # centerXY # scale 0.5
  where 
    foo'   = foo (n-1)
    sq'    = sq # fc (colors !! n)
    colors = [black, red, orange, yellow, green, blue]

dia = foo 5 # lw 0
```

in the middle of a post results in

being included in the generated HTML.

Another exciting thing to mention is the LaTeX package diagrams-latex.sty, included in the diagrams-builder distribution. It lets you embed diagrams in LaTeX documents in much the same way that BlogLiterately-diagrams lets you embed diagrams in blog posts. Just stick diagrams code between \begin{diagram} and \end{diagram} and compile the document with pdflatex --enable-write18. It probably needs more work to smooth out some rough edges, but it’s quite usable as it is—in fact, I’m currently using it to create the slides for my Haskell Symposium presentation in a few weeks.

Just to give a little perspective, this is essentially why I started building diagrams, over four years ago now—I wanted to produce some illustrations for a blog post, but was unsatisfied with the existing tools I found. With these tools, I can finally say that I’ve fully achieved my vision of four years ago—though don’t worry, my vision has grown much larger in the meantime!

Posted in diagrams, haskell, projects, writing | Tagged , , , , , , , , , | 9 Comments

BlogLiterately 0.5.2 release, with improved image uploading

Just a quick note to say that I’ve just released version 0.5.2 of BlogLiterately. (For more information about what it does, see what I’ve written about previous releases here and here, and the documentation.) The new version keeps track of which image files have been uploaded—and their corresponding URLs on the server—in a special dotfile, so it only uploads a given image once, even across multiple runs of BlogLiterately. This is quite convenient, since it means that one can simply leave the --upload-images flag on when uploading successive drafts of a post, and images will be uploaded only once and available to be viewed in the preview version of your post.

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