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.