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

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.