In the last post I mentioned the Basel problem, which is finding the solution to the equation: $$ \sum _{n=1}^{\infty } \frac {1}{n^{2}} =\frac {1}{1^{2}} + \frac {1}{2^{2}} + \frac {1}{3^{2}} + \cdots $$

Before tackling this series with (several) purely mathematical approaches, I wanted to show how the programming language Haskell can be used to approximate this series. One of the interesting things about Haskell is the way that it is able to handle infinite data structures. For instance, in Haskell, I can simply write [1..] to represent the positive integers $\mathbb{Z}^+ = \{1, 2, 3, \dots\}$

This simplicity is driven by the fact that Haskell uses lazy evaluation, meaning that any expression, even the definition of a variable, is not evaluated until it is used. If the variable we assigned this list to were never called in the main of our program, it actually wouldn't be evaluated at all!

Haskell also has the concept of treating functions as first-class citizens, meaning that we can more easily make mathemaical abstrations by creating functions that themselves take functions as arguements.

Let's think about how we can express the notion of a general infinite series in Haskell. At its core, an infinite series revolves around some series $\{a_i\}$. We'll restrict ourselves to the situation where we also have some function that takes our indices $i$ and gives us the terms of our series $f(i) = a_i$

For instance, in the Basel problem we have the function $f(i) = \frac{1}{i^2}$ which gives the series: \begin{align} \{1, 2, 3, \dots\} & \rightarrow \{ f(1), f(2), f(3), \dots\}\\ & = \left\{\frac{1}{1^2}, \frac{1}{2^2}, \frac{1}{3^2}, \dots\right\}\\ & = \{a_1, a_2, a_3, \dots\} \\ & = \{a_i\} \end{align}

Finally, the actual summation of the series is by definition: $$ \sum _{i=1}^{\infty }a_{i}=\lim _{n\to \infty }\sum _{i=1}^{n}a_{i} $$

Written in this form, it becomes a little more obvious how we could write a function to represent a general infinite series. In Haskell, I would first declare the typing as follows:

infin_series :: (Double -> Double) -> [Int] -> [Double]

Let's break down what these types represent:

(Double -> Double) is our function $f(i)$
[Int] is our list of indicies $\{a_i\}$
[Double] is our resulting series $\{f(i)\}$

infin_series :: (Double -> Double) -> [Int] -> [Double]
infin_series func index = map (func . fromIntegral) index

We simply are taking the list of indices and mapping them using the provided function. Look at how clean this is! Note that this was possible because we were able to use a function as an argument. Also, note that at this point we have done nothing to limit ourselves to a finite set of indices. We've created something pretty general here.

Now we can create another function that evaluates the basel problem to an arbitrary precision by taking a specified number of terms of returning their sum:

basel :: Int -> Double
basel sum_terms = sum $ 
                  take sum_terms $
                  infin_series (\n -> 1/(n**2)) [1..]

Here we have simply used our function infin_series and specified that we take a finite number of terms before we get the summation.

So if we call basel 10000, we will be given: $$ \frac{1}{1^2} + \frac{1}{2^2} +\frac{1}{3^2} + \dots +\frac{1}{10000^2} \approx 1.6448340718480652$$

On my desktop, this takes just under two seconds. Is there a closed-form expression for this series? Shockingly, it can be shown that this series is equal to $\frac{\pi^2}{6}$. Where did $\pi$ come from and why is it squared?! I'll give several explanations in a future post.

Beyond an analytic solution, however, we can see that Haskell has a remarkable ability to express mathematical concepts concisely. We were able to not only obtain an approximation for a particular series but construct a function to evaluate any arbitrary series that is a function of its indices. Why is this important beyond pure mathematics problems? This ability for abstraction allows us to create more readable code first of all, and also proves useful in designing code that takes advantage of structural similarities that many programming problems share, giving us an advantage in terms of both performance and the ability to write generalized code.

Code used in this article can be found here.