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,_))     = []
algebra (Just (_, past)) = (nub . (getAll =<<)) (fmap (1:) past)getAll :: [Natural] -> [[Natural]]
getAll = fmap (dropWhile (==0) . sort) . subsets
where subsets xs = flip sumIndicesAt xs <$> indices xsindices :: [Natural] -> [[Natural]] indices = join . para algebra where algebra Nil = [] algebra (Cons x (xs, [])) = [[x:xs]] algebra (Cons x (xs, past)) = (:) <$> [x:xs,[]] <*> pastsumIndicesAt :: [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.Naturalsmain :: 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.