Collatz sequences by function composition by Mark Seemann

Mostly in C#, with a few lines of Haskell code.

A recent article elicited more comments than usual, and I've been so unusually buried in work that only now do I have a little time to respond to some of them. In one comment Struan Judd offers a refactored version of my Collatz sequence in order to shed light on the relationship between cyclomatic complexity and test case coverage.

Struan Judd's agenda is different from what I have in mind in this article, but the comment inspired me to refactor my own code. I wanted to see what it would look like with this constraint: It should be possible to test odd input numbers without exercising the code branches related to even numbers.

The problem with more naive implementations of Collatz sequence generators is that (apart from when the input is 1) the sequence ends with a tail of even numbers halving down to 1. I'll start with a simple example to show what I mean.

Standard recursion #

At first I thought that my confusion originated from the imperative structure of the original example. For more than a decade, I've preferred functional programming (FP), and even when I write object-oriented code, I tend to use concepts and patterns from FP. Thus I, naively, rewrote my Collatz generator as a recursive function:

public static IReadOnlyCollection<int> Sequence(int n)
{
    if (n < 1)
        throw new ArgumentOutOfRangeException(
            nameof(n),
            $"Only natural numbers allowed, but given {n}.");
 
    if (n == 1)
        return new[] { n };
    else
        if (n % 2 == 0)
            return new[] { n }.Concat(Sequence(n / 2)).ToArray();
        else
            return new[] { n }.Concat(Sequence(n * 3 + 1)).ToArray();
}

Recursion is usually not recommended in C#, because a sufficiently long sequence could blow the call stack. I wouldn't write production C# code like this, but you could do something like this in F# or Haskell where the languages offer solutions to that problem. In other words, the above example is only for educational purposes.

It doesn't, however, solve the problem that confused me: If you want to test the branch that deals with odd numbers, you can't avoid also exercising the branch that deals with even numbers.

Calculating the next value #

In functional programming, you solve most problems by decomposing them into smaller problems and then compose the smaller Lego bricks with standard combinators. It seemed like a natural refactoring step to first pull the calculation of the next value into an independent function:

public static int Next(int n)
{
    if ((n % 2) == 0)
        return n / 2;
    else
        return n * 3 + 1;
}

This function has a cyclomatic complexity of 2 and no loops or recursion. Test cases that exercise the even branch never touch the odd branch, and vice versa.

A parametrised test might look like this:

[Theory]
[InlineData( 2,  1)]
[InlineData( 3, 10)]
[InlineData( 4,  2)]
[InlineData( 5, 16)]
[InlineData( 6,  3)]
[InlineData( 7, 22)]
[InlineData( 8,  4)]
[InlineData( 9, 28)]
[InlineData(10,  5)]
public void NextExamples(int n, int expected)
{
    int actual = Collatz.Next(n);
    Assert.Equal(expected, actual);
}

The NextExamples test obviously defines more than the two test cases that are required to cover the Next function, but since code coverage shouldn't be used as a target measure, I felt that more than two test cases were warranted. This often happens, and should be considered normal.

A Haskell proof of concept #

While I had a general idea about the direction in which I wanted to go, I felt that I lacked some standard functional building blocks in C#: Most notably an infinite, lazy sequence generator. Before moving on with the C# code, I threw together a proof of concept in Haskell.

The next function is just a one-liner (if you ignore the optional type declaration):

next :: Integral a => a -> a
next n = if even n then n `div` 2 else n * 3 + 1

A few examples in GHCi suggest that it works as intended:

ghci> next 2
1
ghci> next 3
10
ghci> next 4
2
ghci> next 5
16

Haskell comes with enough built-in functions that that was all I needed to implement a Colaltz-sequence generator:

collatz :: Integral a => a -> [a]
collatz n = (takeWhile (1 <) $ iterate next n) ++ [1]

Again, a few examples suggest that it works as intended:

ghci> collatz 1
[1]
ghci> collatz 2
[2,1]
ghci> collatz 3
[3,10,5,16,8,4,2,1]
ghci> collatz 4
[4,2,1]
ghci> collatz 5
[5,16,8,4,2,1]

I should point out, for good measure, that since this is a proof of concept I didn't add a Guard Clause against zero or negative numbers. I'll keep that in the C# code.

Generator #

While C# does come with a TakeWhile function, there's no direct equivalent to Haskell's iterate function. It's not difficult to implement, though:

public static IEnumerable<T> Iterate<T>(Func<T, T> f, T x)
{
    var current = x;
    while (true)
    {
        yield return current;
        current = f(current);
    }
}

While this Iterate implementation has a cyclomatic complexity of only 2, it exhibits the same kind of problem as the previous attempts at a Collatz-sequence generator: You can't test one branch without testing the other. Here, it even seems as though it's impossible to test the branch that skips the loop.

In Haskell the iterate function is simply a lazily-evaluated recursive function, but that's not going to solve the problem in the C# case. On the other hand, it helps to know that the yield keyword in C# is just syntactic sugar over a compiler-generated Iterator.

Just for the exercise, then, I decided to write an explicit Iterator instead.

Iterator #

For the sole purpose of demonstrating that it's possible to refactor the code so that branches are independent of each other, I rewrote the Iterate function to return an explicit IEnumerable<T>:

public static IEnumerable<T> Iterate<T>(Func<T, T> f, T x)
{
    return new Iterable<T>(f, x);
}

The Iterable<T> class is a private helper class, and only exists to return an IEnumerator<T>:

private sealed class Iterable<T> : IEnumerable<T>
{
    private readonly Func<T, T> f;
    private readonly T x;
 
    public Iterable(Func<T, T> f, T x)
    {
        this.f = f;
        this.x = x;
    }
 
    public IEnumerator<T> GetEnumerator()
    {
        return new Iterator<T>(f, x);
    }
 
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

The Iterator<T> class does the heavy lifting:

private sealed class Iterator<T> : IEnumerator<T>
{
    private readonly Func<T, T> f;
    private readonly T original;
    private bool iterating;
 
    internal Iterator(Func<T, T> f, T x)
    {
        this.f = f;
        original = x;
        Current = x;
    }
 
    public T Current { get; private set; }
 
    [MaybeNull]
    object IEnumerator.Current => Current;
 
    public void Dispose()
    {
    }
 
    public bool MoveNext()
    {
        if (iterating)
            Current = f(Current);
        else
            iterating = true;
        return true;
    }
 
    public void Reset()
    {
        Current = original;
        iterating = false;
    }
}

I can't think of a situation where I would write code like this in a real production code base. Again, I want to stress that this is only an exploration of what's possible. What this does show is that all members have low cyclomatic complexity, and none of them involve looping or recursion. Only one method, MoveNext, has a cyclomatic complexity greater than one, and its branches are independent.

Composition #

All Lego bricks are now in place, enabling me to compose the Sequence like this:

public static IReadOnlyCollection<int> Sequence(int n)
{
    if (n < 1)
        throw new ArgumentOutOfRangeException(
            nameof(n),
            $"Only natural numbers allowed, but given {n}.");
 
    return Generator.Iterate(Next, n).TakeWhile(i => 1 < i).Append(1).ToList();
}

This function has a cyclomatic complexity of 2, and each branch can be exercised independently of the other.

Which is what I wanted to accomplish.

Conclusion #

I'm still re-orienting myself when it comes to understanding the relationship between cyclomatic complexity and test coverage. As part of that work, I wanted to refactor the Collatz code I originally showed. This article shows one way to decompose and reassemble the function in such a way that all branches are independent of each other, so that each can be covered by test cases without exercising the other branch.

I don't know if this is useful to anyone else, but I found the hours well-spent.

---

Comments

• ← Previous
• Archive
• Next →