Add a 'partition' recurrence

[rockbmb]

Closes #107.

[rockbmb]

Benchmarks for Math.NumberTheory.partition as of commit 5ff9a29:

benchmarked Recurrencies/Partition function/partition/!!100
time                 237.4 ns   (203.8 ns .. 261.8 ns)
                     0.923 R²   (0.897 R² .. 0.953 R²)
mean                 268.6 ns   (256.3 ns .. 282.2 ns)
std dev              45.85 ns   (39.81 ns .. 54.31 ns)
variance introduced by outliers: 83% (severely inflated)

benchmarked Recurrencies/Partition function/partition/!!1000
time                 3.403 μs   (3.387 μs .. 3.419 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 3.446 μs   (3.437 μs .. 3.457 μs)
std dev              33.26 ns   (26.85 ns .. 44.39 ns)

benchmarked Recurrencies/Partition function/partition/!!10000
time                 44.19 μs   (43.89 μs .. 44.51 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 44.07 μs   (43.98 μs .. 44.17 μs)
std dev              325.4 ns   (271.7 ns .. 417.7 ns)

[rockbmb]

@Bodigrim can you try doing take 10 (Math.NumberTheory.Recurrencies.partition) :: [Math.NumberTheory.Moduli.Mod 10] in a cabal new-repl session?

It calculates the head of the list, and that's as far as it goes. Consumed 12GB of RAM before I killed the session.

[rockbmb]

@Bodigrim Travis CI's Haddock builds tell me:

50% (  2 /  4) in 'Math.NumberTheory.Recurrencies.Pentagonal'
  Missing documentation for:
    Module header

The module header part is the one that has the Copyright:/Maintainer fields, right? Is there anything in particular I need to put there?

[rockbmb]

Benchmark with Map:

benchmarked Recurrencies/Pentagonal/Partition function/partition/!!1000
time                 8.449 μs   (7.654 μs .. 9.516 μs)
                     0.919 R²   (0.883 R² .. 0.952 R²)
mean                 8.802 μs   (8.394 μs .. 9.332 μs)
std dev              1.450 μs   (1.187 μs .. 1.838 μs)
variance introduced by outliers: 81% (severely inflated)

benchmarked Recurrencies/Pentagonal/Partition function/partition/!!10000
time                 74.68 μs   (66.34 μs .. 84.05 μs)
                     0.888 R²   (0.822 R² .. 0.943 R²)
mean                 97.04 μs   (91.75 μs .. 106.8 μs)
std dev              21.70 μs   (15.41 μs .. 34.40 μs)
variance introduced by outliers: 89% (severely inflated)

benchmarked Recurrencies/Pentagonal/Partition function/partition/!!100000
time                 3.629 ms   (3.455 ms .. 3.833 ms)
                     0.981 R²   (0.961 R² .. 0.994 R²)
mean                 3.370 ms   (3.294 ms .. 3.461 ms)
std dev              241.9 μs   (184.1 μs .. 371.2 μs)
variance introduced by outliers: 37% (moderately inflated)

Benchmark criterion: FINISH

Benchmark with IntMap:

benchmarked Recurrencies/Pentagonal/Partition function/partition/!!1000
time                 4.951 μs   (4.893 μs .. 5.000 μs)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 4.969 μs   (4.941 μs .. 5.009 μs)
std dev              114.5 ns   (89.21 ns .. 157.1 ns)

benchmarked Recurrencies/Pentagonal/Partition function/partition/!!10000
time                 59.54 μs   (58.64 μs .. 60.56 μs)
                     0.998 R²   (0.996 R² .. 1.000 R²)
mean                 60.45 μs   (60.03 μs .. 61.42 μs)
std dev              1.987 μs   (1.065 μs .. 3.635 μs)
variance introduced by outliers: 16% (moderately inflated)

benchmarked Recurrencies/Pentagonal/Partition function/partition/!!100000
time                 3.019 ms   (2.993 ms .. 3.041 ms)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 3.023 ms   (3.009 ms .. 3.035 ms)
std dev              38.90 μs   (29.73 μs .. 56.17 μs)

Benchmark criterion: FINISH

[rockbmb]

@Bodigrim Inside partition, do you have any preference for

go :: forall a . (Enum a, Num a, Ord a) => IM.IntMap a -> Int -> [a]
    go dict !n =
        let intN = fromEnum n
            n' = (sum .
                  pentagonalSigns .
                  map (\m -> dict IM.! (intN - m)) .
                  takeWhile (\m -> intN >= m) .
                  tail) (pents :: [Int])
            dict' = IM.insert intN n' dict
        in n' : go dict' (n+1)

or

go :: forall a . (Enum a, Num a, Ord a) => IM.IntMap a -> [Int] -> [a]
    go dict (n : ns) =
        let intN = fromEnum n
            n' = (sum .
                  pentagonalSigns .
                  map (\m -> dict IM.! (intN - m)) .
                  takeWhile (\m -> intN >= m) .
                  tail) (pents :: [Int])
            dict' = IM.insert intN n' dict
        in n' : go dict' ns
    go _ _ = []

?

[Bodigrim]

@Bodigrim Inside partition, do you have any preference for...

I'd prefer the first snippet.

[rockbmb]

@Bodigrim The PR should be complete now.

[Bodigrim]

Merged. Thanks for your efforts and contribution!