How to write a while loop in a functional language
I’ve been on an Elm kick recently. I’m trying to learn the language by writing a multiplayer Go game, which, in retrospect, might have been slightly too ambitious. Ah, well.
Learning a functional language is a mindbending experience if you’re used to imperative code. Functional languages have no loops, because changing values is verboten—instead of assigning a new value to a local variable you have to make a recursive call and pass the new value as an argument. In exchange for putting up with such restrictions, functional programs gain a wonderful property, called referential transparency, which can make them easier to reason about and test than equivalent imperative programs. However, my brain is still a citizen of imperativeland, and so when thinking about algorithms for my Go game I kept feeling the need for a while
loop.
Although Elm doesn’t have builtin support for while
loops, it’s not very hard to come up with our own while
function that does the job very nicely. We can analyze the concept of a while
loop in imperative languages and see how each of its component concepts maps onto a functional language.
In an imperative language like C or Java, three things are required for a sensical while
loop:

Some state, in the form of variables defined outside the loop body. The loop will update the value of these variables as it runs—that’s the only way a loop can have any effect on the rest of the program.

A condition which determines when the loop is finished. Note that the condition must reference some part of the loop’s state—if it didn’t, the body of the loop could never cause the value of the condition to change, and the loop would run forever.

A body which performs some computation and updates the state.
Note that imperative loops may also cause or react to side effects. For example, here’s a loop in C that has the side effect of printing to standard output:
while (1) {
printf("hello world\n");
}
Similarly, the condition of an imperative loop might watch for side effects triggered by some other process, like a file being written to the filesystem.
Since functional code cannot cause or depend on side effects, we don’t have to consider side effects when translating while
loops to a functional language.
Translating while loops to Elm
Now we can take a stab at writing a while
function in Elm.
We can represent the body of the loop as a function state > state
. That is, the function takes a state
value as an argument and returns the new state
to use for the next iteration of the loop.
We can represent the condition as a function state > Bool
. Again, this has a very close parallel in the imperative world.
So what does the concept of state translate to? Well, the state of a loop can be any collection of values. The only restriction is that the condition and body must agree on what the type of state
is. In Elm, we can represent this by using a type variable, denoted by a lowercase state
in the type signature.
while : (state > Bool) > state > (state > state) > state
In plain English: while
is a function that takes 3 arguments: a condition (a function that takes a state
and returns a boolean), an initial state, and a body function which takes a state and returns the new state. The return value of while
is the final state.
The implementation of while
is only a couple lines of Elm. Once you wrap your head around the functional trick of replacing iteration with recursive calls, it’s easy.
while condition initialState body =
if not (condition initialState) then initialState
else while condition (body initialState) body
In English:
 Given a condition, an initial state, and a body function
 if the condition is false for the initial state, just return the state with no changes.
 if the condition is true, find the state for the next iteration of the loop by calling the body function. Then return the value that
while
would have returned if the new state had been the initial state.
Checking the Collatz conjecture
Now let’s use our while
function and see how the resulting code looks. To test it out, we’ll write a program that checks the Collatz conjecture.
The Collatz conjecture is an unproven statement about what happens when you repeatedly apply a certain calculation to a number. The basic idea is this:
 Start with any positive integer. Call it
n
.  If
n
is even, divide it by 2.  If
n
is odd, multiply it by 3 and then add 1.  Repeat until
n
is 1. After that, the sequence becomes boring: a repeating loop of 1, 4, 2, 1, 4, 2….
The sequence of numbers generated by this repeated calculation is sometimes called the “hailstone sequence” because, like a hailstone in a storm, n
often goes up and down many times before finally falling to 1.
Now, if you pick a positive integer at random and apply the calculation above enough times, you’ll eventually reach 1. It works for every number that’s ever been tried. But of course that doesn’t constitute a proof that this would be true for any number, since there could still be a counterexample out there. And that’s why the Collatz conjecture is just a conjecture: we don’t know how to prove that the sequence always reaches 1. Mathematician Jeffrey Lagarias remarked that such a proof is “completely out of reach of present day mathematics.”
Here’s a function that checks the Collatz conjecture for any positive integer, and returns the number of iterations required to reach 1.
collatz : Int > Int
{ Returns the number of steps necessary for the hailstone
 sequence starting at `start` to reach 1.
}
collatz start =
let
nIsNot1 = \{n} > n /= 1
isEven = \n > n % 2 == 0
initialState =
{ n = start
, iterations = 0
}
result = while nIsNot1 initialState (\{n, iterations} >
if isEven n
then
{ n = n // 2
, iterations = iterations + 1
}
else
{ n = 3 * n + 1
, iterations = iterations + 1
})
in
result.iterations
In my opinion, the while
function produces code that is quite readable. The body function reads almost like an imperative procedure, even though we’re not actually mutating any variables! The only thing that shows this program’s true functional nature is that the while loop must explicitly state which “variables” in the collatz
function it depends on, by listing them as parameters to the body function. That makes for a bit more typing, but it does make it easy to see at a glance what the while loop is doing.
Note that in trying to keep the code simple, I’ve created a bug: the while loop runs forever if collatz
is called with 0
as the starting number. There may also be negative inputs that cause infinite loops. You’d probably want to fix this if you’re writing a real program that uses hailstone numbers.