I decided to write a function divisorSum that sums the divisors of number. For instance 1, 2, 3 and 6 divide 6 evenly so:

$$ sigma(6) = 1 + 2 + 3 + 6= 12 $$

I decided to use Euler's recurrence relation to calculate the sum of divisors:

$$sigma(n) = sigma(n-1) + sigma(n-2) - sigma(n-5) - sigma(n-7) + sigma(n-12) +sigma(n-15) + ldots$$

i.e.

$$sigma(n) = sum_{iin mathbb Z_0} (-1)^{i+1}left( sigma(n - tfrac{3i^2-i}{2}) + delta(n,tfrac{3i^2-i}{2})n right)$$

(See here for the details). As such, I decided to export some other useful functions like nthPentagonal which returns the nth (generalized) pentagonal number. I created a new project with stack new and modified these two files:

src/Lib.hs

module Lib

    ( nthPentagonal,

      pentagonals,

      divisorSum,

    ) where



-- | Creates a [generalized pentagonal integer]

-- | (https://en.wikipedia.org/wiki/Pentagonal_number_theorem) integer.

nthPentagonal :: Integer -> Integer

nthPentagonal n = n * (3 * n - 1) `div` 2



-- | Creates a lazy list of all the pentagonal numbers.

pentagonals :: [Integer]

pentagonals = map nthPentagonal integerStream



-- | Provides a stream for representing a bijection from naturals to integers

-- | i.e. [1, -1, 2, -2, ... ].

integerStream :: [Integer]

integerStream = map integerOrdering [1 .. ]

    where

    integerOrdering :: Integer -> Integer

    integerOrdering n

        | n `rem` 2 == 0 = (n `div` 2) * (-1)

        | otherwise = (n `div` 2) + 1



-- | Using Euler's formula for the divisor function, we see that each summand

-- | alternates between two positive and two negative. This provides a stream

-- | of 1 1 -1 -1 1 1 ... to utilze in assiting this property.

additiveStream :: [Integer]

additiveStream = map summandSign [0 .. ]

    where

    summandSign :: Integer -> Integer

    summandSign n

        | n `rem` 4 >= 2 = -1

        | otherwise = 1



-- | Kronkecker delta, return 0 if the integers are not the same, otherwise,

-- | return the value of the integer.

delta :: Integer -> Integer -> Integer

delta n i

    | n == i = n

    | otherwise = 0



-- | Calculate the sum of the divisors.

-- | Utilizes Euler's recurrence formula:

-- | $sigma(n) = sigma(n - 1) + sigma(n - 2) - sigma(n - 5) ldots $

-- | See [here](https://math.stackexchange.com/a/22744/15140) for more informa-

-- | tion.

divisorSum :: Integer -> Integer

divisorSum n

    | n <= 0 = 0

    | otherwise = sum $ takeWhile (/= 0)

                                  (zipWith (+)

                                           (divisorStream n)

                                           (markPentagonal n))

    where

    pentDual :: Integer -> [Integer]

    pentDual n = [ n - x | x <- pentagonals]

    divisorStream :: Integer -> [Integer]

    divisorStream n = zipWith (*)

                              (map divisorSum (pentDual n))

                              additiveStream

    markPentagonal :: Integer -> [Integer]

    markPentagonal n = zipWith (*)

                               (zipWith (delta) 

                                        pentagonals

                                        (repeat n))

                               additiveStream

app/Main.hs (mostly just to "test" it.)

module Main where



import Lib



main :: IO ()

main = putStrLn $ show $ divisorSum 8

TL;DR:

• use memoization to speed up calculations


• if you drive for performance use quot instead of div
  


• if possible, try to define your sequences without complicated functions


• use even n instead of n `rem` 2 == 0 or odd n instead of n `rem` 2 == 1
  

Type annotations and documentation

You use both type annotations as well as documentation. Great. There are only two small drawbacks:

1. The documentation strings sometimes miss highlighting, e.g. [1, -1, 2, -2,...] in pentagonals. Cross-references would also be great, e.g. pentagonals could point to nthPentagonal in its documentation.


2. Type annotations for workers (the local bindings) only contribute noise, as their type will be inferred by its surrounding function's types.

For example

integerStream :: [Integer]

integerStream = map integerOrdering [1 .. ]

    where

    integerOrdering :: Integer -> Integer

    integerOrdering n

        | n `rem` 2 == 0 = (n `div` 2) * (-1)

        | otherwise = (n `div` 2) + 1

doesn't need the second type annotation:

integerStream :: [Integer]

integerStream = map integerOrdering [1 .. ]

    where

    integerOrdering n

        | n `rem` 2 == 0 = (n `div` 2) * (-1)

        | otherwise = (n `div` 2) + 1

Convey ideas in code as direct as possible

Above, we use n `rem` 2 == 0 to check whether a number is even. However, there is already a function for that: even. It immediately tells us the purpose of the expression, so let's use that:

integerStream :: [Integer]

integerStream = map integerOrdering [1 .. ]

    where

    integerOrdering n

        | even n    = (n `div` 2) * (-1)

        | otherwise = (n `div` 2) + 1

Use quotRem if you need both the result of rem and quot

integerStream is a special case, though: as we need both the reminder as well as div's result, we can use divMod or quotRem, e.g.

integerStream :: [Integer]

integerStream = map integerOrdering [1 .. ]

    where

    integerOrdering n

        | r         = -q

        | otherwise = q + 1

       where

        (q, r) = n `quotRem` 2

Use simpler code where applicable

We stay at integerStream. As the documentation tells us, we want to have a bijection from the sequence of natural numbers to a sequence of all integers.

While the canonical mapping is indeed

$$
f(n) =
begin{cases}
frac{n-1}{2}+1& text{if } n text{ is odd}\
-frac{n}{2}& text{otherwise}
end{cases}
$$
we don't need to use that definition in our code. Instead, we can use

$$
n_1,-n_1,n_2,-n_2,ldots.
$$

integerStream :: [Integer]

integerStream = go 1

    where

      go n = n : -n : go (n + 1)

Or, if you don't want to write it explicitly

integerStream :: [Integer]

integerStream = concatMap mirror [1..]

    where

      mirror n = [n, -n]

Both variants have the charm that no division is necessary in the computation of your list.

Use cycle for repeating lists

While the methods above arguably break down to personal preference, additiveStream can benefit from cycle:

additiveStream :: [Integer]

additiveStream = cycle [1, 1, -1, -1]

Generalize functions where applicable

delta can be written for any type that is an instance of Num an Eq, so lets generalize:

delta :: (Eq n, Num n) => n -> n -> n

delta n i

    | n == i    = n

    | otherwise = 0

I tried writing divisorSum in terms of ZipList, but it kept shrinking until that wasn't needed anymore. Which is half the point of such rewrites!

divisorSum :: Integer -> Integer

divisorSum n

  | n <= 0 = 0

  | otherwise = sum $ takeWhile (/= 0) $ zipWith (*) additiveStream $

      map (x -> divisorSum (n - x) + if x == n then 1 else 0) pentagonals

The call tree of with what arguments divisorSum calls itself is going to overlap with itself. In such situations, you can trade off space for time by keeping around a data structure that remembers the result for each possible argument after it's been calculated once. The memoize library captures this pattern:

divisorSum :: Integer -> Integer

divisorSum = memoFix $ recurse n -> if n <= 0 then 0 else

  sum $ takeWhile (/= 0) $ zipWith (*) (cycle [1, 1, -1, -1]) $

    map (x -> recurse (n - x) + if x == n then 1 else 0) pentagonals