Loops in Functional Languages

Adventures in Programming

In this article, we are going to look at how loops are used, first in an imperative language, like Python, then in a pure functional language, like Elm. While the particular languages used are not as important as the ideas, these are languages that I have used a lot, and which I like a lot, though for different purposes. The first few examples will be mathematical, but involve nothing more exotic that adding numbers. The very last example is about text processing.

The article is organized as follows:

• Imperative Loops recalls how we do loops in an imperative language like Python, with a side note on the notion of infinity in the fourteenth century.
• A Primer on Functional Languages reviews some basic notions, that functions have types a -> b or a -> b -> c . Skip if you know this already
• Reduce and fold presents a standard way of doing loops in functional languages. Can be skipped if you know about reduce and fold.
• Functional Loops is the fun part. We will talk about the type Step state a and all the goodness that flows from it.

1 Imperative Loops

Let’s go back to the days when we first learned to program, computing things like the sum 1 + 2 + 3 + … + 9. This is a task perfectly suited to the for loop, as in the Python example below.

>>> sum = 0
>>> for i in range(1,10):
...   sum = sum + i
>>> sum
45

For loops are good when we know the number of times the loop body will be executed. However, that is not always the case. Consider the so-called harmonic sum,

    h(n) = 1 + 1/2 + 1/3 + ... + 1/n

It was known to the mathematician|bishop Nicole Oresme (ca. 1323–1382) that this sum diverges, so that if you add all the terms, you get infinity. Since neither you nor a computer can do infinitely many additions, what this really means is the following. Choose a number L. Then there is always an n such that h(n) > L. We can write a program to find n given L:

>>> sum = 0
>>> n = 0
>>> L = 10
>>> while sum < L:
...   n = n + 1
...   sum = sum + 1.0/n
...
>>> n
12367

2 A Primer on Functional languages