Draft of my TMR article on multiset partitions

Here’s a draft of the article I’m writing for hopeful inclusion in the upcoming issue of The Monad.Reader:

[EDIT, 11/10/2007: I've removed the draft version since it seems that people are finding it from searches and reading it without realizing it's a draft. I'd much rather people read the (much better) version that was actually published in the Monad.Reader: you can find it here, in Issue #8 of the Monad.Reader. The literate Haskell source can be found here.]

I’d be extremely grateful to anyone who felt inclined to read it and offer comments (it’s about 12 pages). I’m particularly interested in whether it is (in your opinion) clear, and whether it is written at an appropriate level, or if it could use more/less explanation; but of course I’d be grateful for feedback of any sort. I’m also curious whether anyone can point to anything related in the literature. I haven’t turned anything up but I can’t imagine this has never been done before.

To give a very brief synopsis, the article starts out with the problem of efficiently enumerating all the partitions of a multiset — for example, [1,1,2] has four unique partitions: [[[1,1,2]], [[1,1],[2]], [[1,2], [1]], [[1],[1],[2]]]. I then develop some Haskell code to enumerate vector partitions, and use this to compute multiset partitions by representing multisets as vectors of element counts. That’s the bare-bones outline, although there’s more to it than that, of course — in particular the vector partition code ends up having a few additional applications as well. I think it’s neat and (mostly) pretty elegant.

So, thanks in advance to anyone who takes the time to offer me some feedback! Maybe someday I’ll get a chance to bake you some cookies. Or something.

Mapping over a nested functor?

The other day I had a triply-nested list of type [[[a]]], and found myself applying this function to it:

sort . map sort . map (map sort)

This annoyed me. I want a way to say, “map this function over every level of this nested functor”. In other words, given a function transf :: (Functor f) => f a -> f a, I want a function nfmap which, given transf and a “nested functor” (i.e. something of type f a, or f (f a), or f (f (f a)), or …) applies transf on all levels (i.e. transf . fmap transf . fmap (fmap transf) ...). Ideally, then, I would be able to write nfmap sort :: [[[a]]] -> [[[a]]] in place of the code that annoyed me.

Sadly, how to implement the type class NestedFunctor eludes me at the moment. Has anything like this been done before? (I’d be surprised if it hasn’t.) Anyone with some serious Haskell-type-fu want to show me how to implement this?

Rationals!

Inspired by this totally sweet paper by Calkin & Wilf (read it for more details, it’s very short and quite elegantly written) (no really, you should read it):

import Data.Ratio

buildHB (x1:x2:xs) = (x1 + x2) : x1 : buildHB (x2:xs)
hypbin = 1 : 1 : buildHB hypbin
rationals = zipWith (%) hypbin (tail hypbin)

How cool is that? The infinite list of all positive rational numbers, each occurring exactly once in reduced form. In only three lines of Haskell. There are actually better ways to do this; e.g. see the functional pearl by Gibbons, Lester, and Bird. In particular the three-line version above uses O(n) memory to generate the first n rationals, since half of the hypbin list has to be kept around to generate the rest of it, whereas it can actually be done in constant memory. But it’s still nifty.