TDD with a Function Pipeline

Posted on by

Our “geek” group tackled a problem a couple weeks ago, that one of us had heard suggested by Michael Feathers: given a sequence of numbers, tell how many non-zero runs it has. Ron Jeffries described a procedural implementation; we’ll look at a functional “pipeline” solution.

Examples

Here are some examples:

[] → 0 // empty list

[0, 1, 0] → 1 // a simple run

[0, 9, 9, 7, 0, 0, 1, 0] → 2 // multiple 0’s ignored; runs can have multiple items

[1, 2, 0, 3] → 2 // the first item can start a run

The TDD Challenge

Pipeline solutions often have a “just so” look about them. You can look at them and trace them and convince yourself that they work. You can take a whole set of test cases and verify that they all work.

But there’s something odd about implementing them. Often, you may find that almost no tests will pass unless the whole pipeline is present. 

This is very unlike “normal” TDD where we can incrementally design, one test at a time. 

TDD with Pipelines

I don’t have a perfectly general approach, but I often use a key property of pipelines: the stages are associative. That is, they can be parenthesized in any order, just like we write a+b+c since it’s the same whether it’s (a+b)+c or a+(b+c). 

Imitating Unix pipe notation:

a | b | … | z

is the same as 

(a | b | c ) | (d | e) | (f … | z)

Each stage is a function, each parenthesized group is a function, and the whole pipeline is a function. 

And that gives us a handle for TDD: we can test the component functions, then reassemble them into the full pipeline.

The trick is to choose functions that feel the right size for TDD:)

Counting Runs

Rather than present a solution as if it just appeared, I’ll try to trace my thinking.

For me, the first insight came quickly: the number of runs will be the same as the number of run starts. So if I can identify the run starts, I can count them to get the number of runs. 

The key thing that makes a run is whether it is 0 or not, so what if we map values to booleans by “== 0”? Then 0, 1, 3, 0, -1, 2 becomes F T T F T T.

That seems better, but still doesn’t identify starts of runs.

It occurred to me that if I did a Unix-style uniq, which only keeps one copy of any run of identical values, I’d keep the first T of any run of T’s.

All this went through my head as we were discussing more procedural implementations, and I set it aside for “later”.

The procedural implementations made clear there were two important elements: detecting the transition from 0 to non-zero, and what happens when the sequence starts with a non-zero value. (Our procedural approaches either pre-pended a 0, or initialized values in such a way as it seemed we had.)

A Few Days Later…

Ron published his article, and it reminded me – I wanted to implement a pipeline version, easy to understand and developed using test-driven development.

Counting

I tackled a simpler problem first: the last half of a feasible answer. Given a sequence of F and T, count the number of T’s. I did it this way to show I can choose a chunk of the pipeline for which I can test-drive a solution. I figured if I could detect the run starts as a sequence of booleans, this would solve the rest of the problem.

I solved the counting problem with “map and reduce”. Map() applies a function to each element of a sequence, and forms the results into a new sequence. In this case, I mapped each F to 0 and each T to 1. 

To sum them, I used the reduce() function: it takes a starting value and a combining operator, and combines each element with the previous result. So reduce(0, +) sums the values. I think of reduce as listing the values preceded by the starting value, and sticking the operator between each pair of values. So [1,5,7].reduce(0, +) = 0 + 1 + 5 + 7 = 13.

The routine looks like this:

func countTrues<S: Sequence<Bool>>(_ items: S) -> Int {
  items
    .map { $0 ? 1 : 0 }   // $0 is current item
    .reduce(0, +)
}

Swift uses an implicit return: a method body with a single expression is automatically the return value. 

If we were using Java, it has a sum() method that to add up a sequence; this is more directly expressive than the reduce() I used here.

Starts of Runs

To detect the transitions, I knew I wanted a sequence of each value followed by its successor. To get that, I use the zip2 function. That takes two sequences, and makes a sequence with the first element of each list as a pair, then the second, etc. 

I only have one list, but I can zip it with itself. I started by zipping the original list with the tail (second element on) of that list. That gets me a list of the first element paired with the second, the second with the third, and so on.

Given those pairs, I can do another map: turn the pair into true iff it’s the start of a sequence. This is a new run if the first element is 0 and the second is not. 

The detector function is simple, and has four natural cases: (0,0), (0, non-zero), (non-zero, 0), (non-zero, non-zero). 

func detectRunStarts(_ a: Int, _ b: Int) -> Bool {
    a == 0 && b != 0
}

Here is the pipeline to convert numbers to an array of booleans (true if run starts):

func detectRuns<S: Sequence<Int>>(_ items: S) -> [Bool] {
    zip(items, items.dropFirst(1))
    .map(detectRunStarts)
}

Note that this doesn’t yet handle the case where a run starts with non-zero!

Sequences That Start With a Run

The final challenge is handling runs that start with a non-zero value. From our earlier implementations, I knew that we could use a sequence starting with 0 to force that run to be detected. So, I modified my zip to use [0]+items for the first sequence, and items for the second. 

func detectRuns<S: Sequence<Int>>(_ items: S) -> [Bool] {
    zip([0] + items, items)
    .map(detectRunStarts)
}

A Solution

Given that, here’s the body of the whole solution:

  countTrues(detectRuns(items))

I can build a few test cases that check it, e.g., [], [0], [1], [2, 1, 0, 0, -1, 3]. Those all work. 

From there, I can inline the functions and put it in one pipeline: (Comments show the effects of each line on an example; if you’re experienced, you may not need those).

                            // [1, 0, 10, 7] - example
zip([0] + items, items)     // [(0, 1), (1, 0), (0,10), (10,7)]
    .map(detectRunStarts)   // [T, F, T, F]
    .map { $0 ? 1 : 0 }	    // [1, 0, 1, 0]
    .reduce(0, +)           //  2

This also passes the tests. We can decide which version we prefer.

Improving

The inlined pipeline reveals that we’re flipping back and forth between booleans and numbers using two maps in a row. 

If we were to conceive of our run-start detector as counting the run-starts of a pair, it could produce a 1 or 0 and let us drop a map. We can then feed integers directly into the reduce.

func countRunStarts(_ a: Int, _ b: Int) -> Int {
    a == 0 && b != 0 ? 1 : 0
}

func runCount<S: Sequence<Int>>(_ items: S) -> Int {
                            // [1, 0, 10, 7]  - example input
    zip([0] + items, items) // [(0,1), (1,0), (0,10), (10,7)]
    .map(countRunStarts)    // [1, 0, 1, 0]
    .reduce(0, +)           //  2
}

To me, this version is the best so far. But like many pipeline solutions, I understand it, but don’t think I could (yet:) jump to this solution right away.

Reflection

I used several techniques. I didn’t invent any of these. I think they’re easy enough to understand in isolation.

  • Associativity lets us split apart a pipeline how we choose
  • Zip turns a sequence into pairs
  • Prepending a value simplifies “left edge” cases
  • Map can apply a characteristic function (turning values into booleans)
  • Map can shift domains (boolean → integer)
  • Mapping to 0 or 1 lets us count
  • Reduce computes a combining function (“sum all” in this case).

From the TDD side: our characteristic function (“starts a run?”) was easy to test-drive. When we identify a sub-chain of functions with a simple enough purpose, we can isolate that to a single function we can test-drive it (as we did for “count the T’s”).

Unfortunately, I think it’s easy to create a pipeline that’s too big for me to test-drive directly, even if the function is relatively easy to describe. But if I can test-drive sub-pipelines and combine them into larger functions. If I merge pipelines, I do need to make sure the test cases are sufficient for the bigger pipeline.

Related Work

“Pipelines – Confidence in Design”, by Bill Wake. https://xp123.com/pipelines-confidence-in-design/ – retrieved 2024-05-26.

“Spans”, by Ron Jeffries. https://ronjeffries.com/articles/-y023/spans/ – retrieved 2024-05-26.