Advanced Exercism • fsharp

Collatz Conjecture

Challenge Overview

Calculate the number of steps to reach 1 using the Collatz conjecture.

Visit the collatz-conjecture exercise on Exercism to read the full instructions and download the exercise files.

Dig Deeper

Recursion

module CollatzConjecture

let steps (number: int): int option =
    let rec doSteps (current: int) (numberOfSteps: int) =
        if current < 1 then None
        elif current = 1 then Some numberOfSteps
        elif current % 2 = 0 then doSteps (current / 2)  (numberOfSteps + 1)
        else doSteps (current * 3  + 1) (numberOfSteps + 1)

    doSteps number 0

To use (tail call) recursion to calculate the distance, we’ll introduce a helper function: doSteps. We’ve defined this function within the steps function (also known as a nested function), but it could just as well have been defined outside the steps function.

The doSteps function takes the number (basically, where we’re at in the collatz sequence) and the number of steps taken so far:

let rec doSteps (current: int) (numberOfSteps: int)

To allow a function to recursively call itself, the `rec` modified must be added.
In other words: by default, functions cannot call themselves.

With the doSteps function,

With each recursive call, we’ll increment This parameter represents the current distance and is updated between the recursive function calls until we’re done processing, at which point it will represent the total distance.

Our function definition looks as follows:

let rec doSteps (current: int) (numberOfSteps: int) =
    if current < 1 then None
    elif current = 1 then Some numberOfSteps
    elif current % 2 = 0 then doSteps (current / 2)  (numberOfSteps + 1)
    else doSteps (current * 3  + 1) (numberOfSteps + 1)

Within this function, we first check if the current number is less than one. If so, the input must have been less than one and is considered invalid, so we return None:

if current < 1 then None

Then we check if the current number is equal to one, which is the terminating condition for the collatz sequence. If so, we’re at the end of the collatz sequence and we can return the number of steps, wrapped in Some:

elif current = 1 then Some numberOfSteps

Finally, we’re coming to the recursive function calls, as the current number is greater than one. There are two cases we need to handle.

The current number is even
The current number is odd

In the even case, we recursively call the doSteps function with the new number (current / 2) and the number of steps increased by one (numberOfSteps + 1). For the odd case, we do the same but the new number is current * 3 + 1:

elif current % 2 = 0 then doSteps (current / 2)  (numberOfSteps + 1)
else doSteps (current * 3  + 1) (numberOfSteps + 1)

Calling the recursive helper function

The final step is to call our recursive helper function:

doSteps number 0

And with that, we have a working, tail recursive implementation that correctly calculates the number of steps in a number’s collatz sequence.

Tail recursion prevents stack overflows when a recursive function is called many times.
While the exercise does not have large test cases that would cause a stack overflow, it is good practice to always use using tail recursion when implementing a recursive functions.
If you'd like to read more about tail recursion, [this MSDN article](https://blogs.msdn.microsoft.com/fsharpteam/2011/07/08/tail-calls-in-f/) goes into more detail.
Another good resource on tail recursion is [this blog post](http://blog.ploeh.dk/2015/12/22/tail-recurse/).

Pattern matching

Instead of using if/elif expressions, you could also use pattern matching:

match current with
| x when x < 1 -> None
| 1 -> Some numberOfSteps
| x when x % 2 = 0 -> doSteps (current / 2)  (numberOfSteps + 1)
| _ -> doSteps (current * 3 + 1)  (numberOfSteps + 1)

This is functionally equivalent, but whether or not this is more readable is up for debate.

Unfold

let steps (number: int): int option =
    let collatzSequence (number: int): int seq =
        Seq.unfold (fun current ->
            if current = 1 then
                None
            elif current % 2 = 0 then
                Some (current, current / 2)
            else
                Some (current, current * 3  + 1)
            )
            number

    if number < 1 then None
    else collatzSequence number |> Seq.length |> Some

The collatz sequence is basically a while loop that updates a value and terminates when the value is equal to one. This is a common enough pattern, that F# has a built-in function for this use case: Seq.unfold.

`Seq.unfold`

The Seq.unfold function takes two arguments:

A function that takes a value and returns a value pair wrapped in an Option<T>
The initial value

The function can return either:

Some (returnValue, newValue): continue executing, whilst adding the first value (returnValue) to the list of values to return, and use newValue as the value for the next call to the lambda
None: stop execution

Once the function returns None, the accumulated return values are returned.

Unfolding the collatz sequence

Now that we know how Seq.unfold works, let’s use it to generate our collatz sequence.

Seq.unfold (fun current ->
    if current = 1 then
        None
    elif current % 2 = 0 then
        Some (current, current / 2)
    else
        Some (current, current * 3  + 1)
    )
    number

You can see that there are three different paths the lambda takes.

1. Stop executing when the number is one

The very first thing we check is whether the current number is equal to one. If so, we return None and execution stops.

if current = 1 then
    None

2. Handle an even number

We use the modulo operator to check if the number is even, and if so, we return Some (current, current / 2):

elif current % 2 = 0 then
    Some (current, current / 2)

As a reminder: the first value current is added to the list of values to return, whereas current / 2 will be the new value to work with.

3. Handle an odd number

At this point, we know the number must be odd, so we return Some (current, current * 3 + 1):

else
    Some (current, current * 3  + 1)

Step-by-step execution

Let’s run through the Seq.unfold calls to get a better feel for it working as intended:

Current number	Lambda return	Return values
5	`Some (5, 16)`	`[5]`
16	`Some (16, 8)`	`[5; 16]`
8	`Some (8, 4)`	`[5; 16; 8]`
4	`Some (4, 2)`	`[5; 16; 8; 4]`
2	`Some (2, 1)`	`[5; 16; 8; 4; 2]`
1	None	`[5; 16; 8; 4; 2]`

You can see that we’re slowly building up the return values, returning them once we’ve reached one.

Counting the number of steps

Let’s make use of our collatzSequence function within the steps function:

let steps (number: int): int option =
    if number < 1 then None
    else collatzSequence number |> Seq.length |> Some

We first check if the current number is less than one. If so, the input must have been less than one and is considered invalid, so we return None:

if current < 1 then None

Otherwise, we can use collatzSequence number to return all the numbers in the collatz sequence up to (but not including) the number one. We then count the steps using Seq.length and wrap it in a Some value:

else collatzSequence number |> Seq.length |> Some

And that’s it, we’ve correctly calculated the number of steps in a number’s collatz sequence!

Using a nested function

It’s also possible to make the collatzSequence function a nested function of the steps function. This is not unreasonable, as there is little going on in the steps function.

let steps (number: int): int option =
    let collatzSequence (number: int): int seq =
        Seq.unfold (fun current ->
            if current = 1 then
                None
            elif current % 2 = 0 then
                Some (current, current / 2)
            else
                Some (current, current * 3  + 1)
            )
            number

    if number < 1 then None
    else collatzSequence number |> Seq.length |> Some

Inline collatz sequence

It is also not unreasonable to inline the collatzSequence function:

let steps (number: int): int option =
    if number < 1 then
        None
    else
        number
        |> Seq.unfold (fun n -> if n = 1 then None elif n % 2 = 0 then Some (n, n / 2) else Some (n, n * 3  + 1))
        |> Seq.length
        |> Some

It’s a bit dense, but not unreasonably so. You do love the expressiveness of the call to the appropriately named collatzSequence function.

Sequence expression

let steps (number: int): int option =
    let rec collatzSequence (current: int): int seq =
        seq {
            if current > 1 then
                yield current
                if current % 2 = 0 then
                    yield! collatzSequence (current / 2)
                else
                    yield! collatzSequence (current * 3 + 1)
        }

    if number < 1 then None
    else collatzSequence number |> Seq.length |> Some

The collatz sequence can be generated using recursion, where the current number changes between calls. One way to generate sequence of numbers in a number’s collatz sequence is to use a sequence expression. Let’s see how that works!

Sequence expressions

With sequence expressions, one can generate sequences using very declarative code. You start with the seq keyword and its logic is written between curly braces. This (admittedly rather silly) sequence expression will return the first primes:

let firstPrimes (): int seq =
    seq {
        yield 2
        yield 3
        yield 5
    }

This will return a sequence contains 2, 3 and 5 (in that order).

Yielding multiple values

Whilst yield only ever returns one value, you can also return a sequence of values via yield!

let firstPrimes (): int seq =
    seq {
        yield 2
        yield! [3; 5]
    }

This will, once again, return a sequence contains 2, 3 and 5 (in that order).

Using conditionals

You can also use if expressions within sequence expressions:

let greaterThanTen (n: int): int seq =
    seq {
        if n > 10
            yield n
    }

Note that you don’t have to specific an else branch.

Recursive sequence expressions

Sequence expressions can also be recursive, meaning they can call themselves. Here is an function that generates an (infinite) sequence of all even numbers:

let rec evenNumbers (current: int): int seq =
    seq {
        yield current
        yield! evenNumbers (current + 2)
    }

Generating the collatz sequence

Now that we know how sequence expressions work, let’s use them to generate our collatz sequence:

let rec private collatzSequence (current: int): int seq =
    seq {
        if current > 1 then
            yield current
            if current % 2 = 0 then
                yield! collatzSequence (current / 2)
            else
                yield! collatzSequence (current * 3 + 1)
    }

This function takes the current number as its sole parameter and is marked with rec to allow it to call itself.

To allow a function to recursively call itself, the `rec` modified must be added.
In other words: by default, functions cannot call themselves.

The body of the function has code wrapped in seq {}, which indicates to the compiler that we’re generate a sequence.

1. Stop executing when the number is one

With the sequence expression, we start by checking if the current number of greater than one. Only when it is do we yield the current number:

if current > 1 then
    yield current

This has the effect that we stop generating the sequence when the number if less than or equal to one, which is exactly what we want.

2. Handle an even number

We then use the modulo operator to check if the number is even. If it is, we yield the rest of the collatz sequence by recursively calling the collatzSequence with the new value being (current / 2):

if current % 2 = 0 then
    yield! collatzSequence (current / 2)

Note: as collatzSequence returns a sequence, we have to use yield!