blog

If you were on the math team during high school, you may remember integer partitions not too fondly. They're not particularly easy to get a grip on: even counting the partitions of an integer requires generating functions (which are scary when you're in high school).

But they're easily tractable with a computer, and so here we present functional algorithms for integer partitions, written in Haskell. It does use recursion-schemes, but this is more than justified by the added eloquence.

import Numeric.Natural       (Natural)
import Control.Monad         (join)
import Data.List             (nub)
import Data.Functor.Foldable (ListF (..), para)


partitions :: Natural -> [[Natural]]
partitions = para algebra
    where algebra Nothing          = []
          algebra (Just (0,\_))     = [[1]]
          algebra (Just (\_, past)) = (nub . (getAll =<<)) (fmap (1:) past)

getAll :: [Natural] -> [[Natural]]
getAll = fmap (dropWhile (==0) . sort) . subsets
    where subsets xs = flip sumIndicesAt xs <$> indices xs

indices :: [Natural] -> [[Natural]]
indices = join . para algebra
    where algebra Nil                 = []
          algebra (Cons x (xs, []))   = [[x:xs]]
          algebra (Cons x (xs, past)) = (:) <$> [x:xs,[]] <*> past

sumIndicesAt :: [Natural] -> [Natural] -> [Natural]
sumIndicesAt ix = (\\(a, b) -> sum a : b) . partition (\`elem\` ix)

While this is beautiful on its own (not to mention an instructive use of paramorphisms), we also get a very satisfying application of QuickCheck using Ramanujan's congruences, viz.

$$p(5k + 4) \equiv 0 (\text{mod } 5)$$ $$p(7k + 5) \equiv 0 (\text{mod } 7)$$ $$p(11 k + 6) \equiv 0 (\text{mod } 11)$$

where \(p(n)\) is the number of ways to partition some integer \(n\).

This leads to the following property test using hspec:

import Test.Hspec
import Test.QuickCheck
import Numeric.Naturals

main :: IO ()
main = hspec $
    describe "partitions" $
        it "should satisfy Ramanujan's identities (1/3)" $
            property $ \n -> (length . partitions) (5 \* n  + 4) `mod` 5 == (0 :: Natural)
        it "should satisfy Ramanujan's identities (2/3)" $
            property $ \n -> (length . partitions) (7 \* n  + 5) `mod` 7 == (0 :: Natural)
        it "should satisfy Ramanujan's identities (3/3)" $
            property $ \n -> (length . partitions) (11 \* n  + 6) `mod` 11 == (0 :: Natural)

From which we can confirm that our function does what we desire with a cosmic level of confidence.