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 mind-bending 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 imperative-land, and so when thinking about algorithms for my Go game I kept feeling the need for a while loop.

Although Elm doesn’t have built-in 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. Mathema­tician 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.

Next: Don't listen to your tests