Pretty image
Paul has been debating functional programming and test-driven development with “Uncle Bob” Martin. Here he shares the result of that conversation.

In January, we published an engaging essay by “Uncle Bob” Martin on functional programming (or FP). Bob has since continued his exploration of FP on his blog, and we recommend it to anyone interested in the functional paradigm. One person who has been following Bob’s series is Paul Callaghan, who has been writing a series on FP for us. This led to Bob and Paul having a spirited and productive back-and-forth about FP, and that led to Paul’s current article, in which he explores some of the points raised in a recent post in Bob’s series. –ms

Taking the Uncle Bob Challenge

Episode 3 of Bob Martin’s series on Functional Programming Basics is a very readable investigation into use of TDD ideas in FP and how TDD-grown code compares with more “idiomatic” functional code. It raises several interesting points, and what you are reading now attempts to address some of these and carry them forward. It also contains some Haskell.

The starting point is a small programming exercise: formatting a string into block of lines according to certain rules. Bob’s description of the problem took the form of an informal overview, a motivating example and some test cases. Here is the example, using a maximum line width of 10.

 # input string
 inp = "Four score and seven years ago our fathers brought " +
  "forth upon this continent a new nation conceived in " +
  "liberty and dedicated to the proposition that all men " +
  "are created equal"
 # resulting output
 out = "Four score\nand seven\nyears ago\nour\nfathers\n" +
  "brought\nforth upon\nthis\ncontinent\na new\n" +
  "nation\nconceived\nin liberty\nand\ndedicated\n" +
  "to the\npropositio\nn that all\n" +
  "men are\ncreated\nequal"
 # start of the printed output
 Four score
 and seven
 years ago

The test cases from Bob’s article are below, expressed as a list of assertions on some input function wrap to be tested (I’ll want to test several versions).

 tests wrap
  = [ wrap 1 "" == ""
  , wrap 1 "x" == "x"
  , wrap 1 "xx" == "x\nx"
  , wrap 1 "xxx" == "x\nx\nx"
  , wrap 1 "x x" == "x\nx"
  , wrap 2 "x x" == "x\nx"

We’ll explore various ideas about coding techniques, comprehension, testing, verification, and validation. A key notion for me throughout is confidence. Whatever we do while developing code to solve some problem is about improving confidence that it’s the “right” code (whatever that means). Testing provides one kind of confidence. Code reviews give another kind. Various proof-related techniques yet another. It’s always debatable how much confidence any particular technique can give, though we can consider what kind or level of confidence we want in some situation, and select appropriate methods.

Missing a Trick

Before we launch into functional programming, here’s a solution that is arguably better than the others we’re considering. Why? Because it uses a domain-specific language (DSL) specifically designed for this kind of problem, and it’s enviably short! What more could we want?

 # this is perl!
 # $n is the max line length
 s/([\w ]{1,$n}) /$1\n/g;

The idea is to use regular expressions, matching relevant patterns and replacing them with certain strings.

Regexps allow us to say exactly which patterns we want to match, and the replacement facility provides an easy way to modify the string.

The first substitution expression splits all long words down to size, adding a newline after each N-character chunk—as long as there’s a word character following the potential break. (The (?=\w) is Perl syntax for a lookahead assertion, which tests for an expression but doesn’t consume it—that is, the match still ends where the lookahead starts.) The g suffix means it is applied throughout the string, with the next match attempt starting after the end of the previous match (not including the lookahead), hence the overall effect is to split all applicable words.

The second expression handles the line-packing functionality, matching between 1 and N word or space characters followed by a space, and then changing the final space into a newline. Again, it’s applied globally so is applied as many times as possible, starting from after the previous match. Note that regexp matching (in most implementations) is “greedy,” so in the second case it will always try to match the longest sequence (up to N characters) before splitting a line.

This is great until we reach the last line, where greediness means we break too early (because there’s no space at the end of the string so it backtracks to the last space seen). One sneaky way around this is to add a space to the string, do the matching, and then remove the final character. Maybe it’s a bit too sneaky though.

 $_ .= " ";
 # now do the substitutions as above

Here’s another idea for you to try: we can code this up as a state machine, consuming one character at a time and deciding to emit zero or more character(s) on each step. This could start the wrapping process while you were still feeding in text, even if the text was huge or potentially infinite. This version should be achievable with one of the Unix lex variants, or a simple state machine library in your favorite language. (Incidentally, this “convert as we go” functionality comes for free in Haskell because of the laziness. Check out the interact function too.)

We can run the tests and observe a set of passes. But questions to leave hanging: are we sure it’s right, and how are we sure it’s right? And how sure are we?

Bob’s TDD-Grown Solution

Below is the code Bob derived using a TDD process, translated into Haskell. I’m including it for interest, and for comparison with the other Haskell versions.

I’ll stick my neck out and suggest that the Haskell version, with its more “modern” syntax, is easier to read and to follow. Take a look and decide for yourself. But it’s not the key point of this article, so let’s save that discussion for another time. Plus, the ideas covered in this article apply in most other FP languages too, not just Haskell, so this isn’t purely an ad for one language.

Notice that I’m also relying on Haskell’s version of strings as a list of characters, rather than a Java-ish array of characters. This allows me a bit more flexibility by using basic list functions like take and drop instead of substr. Does it change the nature of the exercise though? I think not, because both lists and arrays are sequences and the basic operations are fairly similar. However, it does maybe encourage me to split a long string into words sooner, that is, to work with more convenient forms of the data—and to make some further simplifications.

 wrap s n
  | length s <= n = s
  | otherwise = let (start,end) = find_start_and_end s n
  head = take end s
  tail = drop start s
  in head ++ "\n" ++ wrap tail n
 find_start_and_end s n
  = (line_start, line_end)
  space_before_end = last_index_in ' ' n
  line_end | space_before_end < 0 = n
  | otherwise = space_before_end
  trailing_space = ' ' == s !! line_end
  line_start | trailing_space = 1 + line_end
  | otherwise = line_end

This code passes all of the tests, and that was the original goal. You can see how it works—basically looking for the last space within N characters and determining the end point for the current line and the start point for the following line. Next, one would normally refactor, but it’s not too clear what refactorings should apply. From a “smells” viewpoint, there are a few points that would be good to address. I’ll let you decide for yourselves what these are.

My initial reaction though, as a somewhat seasoned functional programmer with a fetish for data structures, was “it shouldn’t be this complex!” The rest of the article will explore this reaction.

Last detail here: Bob’s Clojure code calls a method from Java’s String class to find the last index of a character in a string (optionally up to a certain maximum position). Here’s one way to do it in Haskell. find_last reverses the input string and then looks for the first occurrence of the character. Since we are dealing with plain lists, though, it doesn’t have to be a character—this operation is OK with a list of anything as long as we can test for equality.

 find_last :: Eq a => c -> [c] -> Int
 find_last c s
  = case elemIndex c (reverse s) of
  Nothing -> -1
  Just i -> length s - 1 - i

The maximum position aspect is handled by trimming the string argument before the call to find_last, remembering to add 1 because we’re converting from a position to a length. (And yes, that’s a maximum position not a maximum length—it caught me out too. So much easier for lists to talk offsets and lengths, rather than start and end points! That is, easier to split a string into the actual pieces you want, rather than work out the indices to target the corresponding slice.)

 last_index_in :: Eq a => c -> Int -> [c] -> Int
 last_index_in c n s
  = find_last c (take (n+1) s)

Some TDD in Haskell

Let’s try TDD-ing directly in Haskell, just to see where we get. There are several XUnit adaptations available for Haskell, plus more advanced tools like QuickCheck (or see RushCheck for a Ruby port), but we don’t need anything sophisticated, and rolling my own version below allows coverage of a few more programming ideas.

We’ll write the tests as a list of boolean-valued assertions, where each case indicates what is expected from each input string. The test list below takes a function to test as a parameter because we’ll want to play with different versions. So, assuming the code above is defined as wrap_bm, then evaluating tests (\n s -> wrap_bm s n) will perform the assembled tests on the translation of Bob’s TDD-grown code. (The lambda handles the difference in argument order. I could also use Haskell’s flip function for this.) The outcome will be a list of booleans, of course.

 tests foo
  = [ foo 1 "" == ""
  , foo 1 "x" == "x"
  , foo 1 "xx" == "x\nx"
  , foo 1 "xxx" == "x\nx\nx"
  , foo 1 "x x" == "x\nx"
  , foo 2 "x x" == "x\nx" -- Bob's six tests end here
  , foo 3 "x xxxx" == "x\nxxx\nx" -- A new test case

It helps to dress this up a bit, so why not number the tests and show “ok” or “not” depending on each test result. The following is something I will rerun at each step of TDD-ing the Haskell code directly, passing in the latest version of the function to test. Literally, it generates a list of raw booleans by applying the tests to the given function, converts each to “ok” or “not” depending on the test result, then zips them with a list of numbers (so pairing 1 with the first, 2 with the second, ... until either side runs out of values) and creates an appropriate string from each result. This is a list of strings, but we want them printed out one to a line and the combination putStr (unlines STUFF) does this in Haskell. As a style thing, note the use of . to compose functions and the general lack of parentheses, which leaves the overall operation looking like a pipeline of simple steps. Which it is...

 check = putStrLn
  . unlines
  . zipWith (\n s -> show n ++ " " ++ s) [1..]
  . map (\t -> if t then "ok" else "not")
  . tests

To cut a long story short, here’s some code that passes all seven tests. You can see the progression of versions on this github gist. Seven tests? Well, I found another test case (foo 3 "x xxxx" == "x\nxxx\nx") that failed on the code I’d reached after the first six tests. Here’s my code after seven passes. There’s at least one other case where this version fails. See if you can find one!

 wrap_7 n "" = ""
 wrap_7 n (' ':x) = wrap_7 n x
 wrap_7 n x
 | null rest
 = line
 | otherwise
 = case break (== ' ') $ reverse line of
  (no_space, []) -> line ++ "\n" ++ wrap_7 n rest
  (tl, ' ':hd) -> reverse hd ++ "\n"
  ++ wrap_7 n (reverse tl ++ rest)
  where (line,rest) = splitAt n x

It was an interesting—and for me a slightly discomforting—experience. I did do it blind, several days after seeing Bob’s article and not looking at his answer. It was tempting to do too much on each step, like inadvertently using parts of my preferred solution.

The key idea above is to take slices of N at a time and decide how to handle them based on whether there’s a space near the end of the slice or not. Haskell’s splitAt function has type Int -> [a] -> ([a], [a]), so splits a list of anything into two pieces with the first piece being length N or less, and the second piece being the remainder of the string.

The function break :: (a -> Bool) -> [a] -> ([a], [a]) is similar, where the first part of the result is the prefix (beginning) of the list that failed the test and the second part is the rest of the list— starting with this first hit. So, break (== ' ') "foo bar" gives ("foo", " bar"). So, break can be used to find a space (or not). I’m interested in the last space so I reverse the current line chunk before hunting for it.

I’m using a bit of pattern matching to determine which case I have, namely (a) no space found—which makes the post-break list empty, so the result should be the current slice then a newline then the result of wrapping the rest; else (b) there was a space, and the result is the before-space chunk then a newline and then the result of wrapping the remaining text. Because the after-space text is unconsumed, we add it to the front of the text to process.

One big difference between this code and Bob’s code is how it’s using data structures a lot more, splitting a string into pieces and manipulating them rather than juggling with string indexes. As mentioned before, I think this is a key aspect of modern functional programming—using the rich data structures and their tools to help simplify our programs. It does help to avoid certain classes of error.

Do you have to memorize the language’s libraries to do this, though? I hope not. My claim is that if you start to think in terms of data structures, and think about the transformations, then you’ll start to realize what you might need and have a clearer idea of what to look for. To be more concrete, if you think about splitting a long string into pieces, then you can start asking, does it feel like an obvious library function, or does it feel like something that should be decomposed into smaller pieces? Even if you can’t find something, the smaller pieces tend to be simple enough for you to write yourself. For example, splitAt n xs can be defined as (take n xs, drop n xs).

To consider that point another way: I don’t think it’s about memory, but more about being able to think through a problem and having some confidence in your thoughts. So, if your ideas make sense then have faith to chip away at the hard bits to get to the easy bits. (This point reminds me of many former students who took “Computer said no” too personally and didn’t try to work out why the computer rejected their code, often because they didn’t trust their instincts enough, so instead tried to add more complexity...)

Anyway, is this good code? Depends what “good” means. It passes all of the tests, which says something, but are we sure that those tests are enough? It’s debatable. I made a mistake in the sixth iteration—missed a call to reverse—which the original six tests didn’t catch. My new test was on wrap 3 "x xxxx", though perhaps using a mixture of letters in the original tests might have worked too, by explicitly excluding any permutation of the input. There’s at least one more test case that fails. I am still not sure whether further test cases are needed.

Anyway, there are several functional smells in this code, like why the strange case for wrap_7 n (' ':x), and the null rest case feeling like a premature end case. Can these be refactored out, and some better structure recovered? It’s not obvious how. But most significantly, it’s also not too clear how the code works, particularly in the sense of having confidence that it does what we intended (other than by tests). Can we do it in a transformational style, as a pipeline of simpler stages? That’s the next thing to discuss.

Thinking About It

The old me thinks he sees a pattern. It looks like a splitting and packing problem, and that kind of thing can be done in a pipeline. (Actually, a lot of computation can be done as a pipeline! And if it can’t, then why not? Or why not as a pipeline plus some monadic wrapping?) Intuitively, we can split the input into words, then split the long words into a list of chunks no longer than N and concatenate the results into a single list of word fragments. Next, we assemble this list of fragments into a list of lines, where we pack as many words into a line as possible without exceeding the length limit. Then, we just join the lines together.

Why not try to visualize this? For example, draw a picture for how the input data gradually gets transformed, perhaps adding some concrete examples to illustrate finer detail or help understand the abstract view. This technique really helps understanding, so I do recommend it. (I used to have great fun in lectures, drawing such diagrams out on large blackboards 30 feet wide, then in a cloud of chalk dust gradually converting sections of the diagram to straightforward code. Whiteboards just aren’t the same!)

Let’s write this down as code. For “obvious” things, we’ll write down the usual library functions. For non-obvious things, we’ll put in a placeholder to come back to later.

 wrap n i = intercalate "\n"
  $ makeUpTo n
  $ concat
  $ map (chunksOf n)
  $ words i

This clearly makes sense, and we can square it with our visualization, that is, it says what we were thinking. Next, fill in the gaps, working on one piece at a time. The first task is to split long words into the smaller chunks. Considering the input and output, we can expect chunksOf to have type Int -> [a] -> [[a]], so given a size limit it converts a list of things into a list of lists of such things, for example a long word into pieces of word. There is much that the type doesn’t say—but we’ll return to that later.

Hang on! Is this defined in a library or package (that is, a standard library or an optional gem-like entity)? It seems like something that is pretty useful, so let’s search a bit. Turns out yes: a package called split provides a module called Data.List.Split that contains function chunksOf One way to find such functions is just to use a google search, for example haskell library split list and look through the various library pages from or use Haskell’s specialist search tool Hoogle—although the current version doesn’t seem to index the package we found.

You don’t have to use this package (and as with ruby gems you should check that the code is OK before you import it—and that it’s from a secure server(!)), or you could just copy the definition into your own code—with a reference to its source, of course. The package definition is however slightly optimized so let’s see a simpler definition. First, iterate (drop n) repeatedly removes N elements from a list, returning a list of the diminishing results, for example, iterate (drop 3) [1..10] will give [[1..10], [4..10], [7..10], [10..10], [], [], ...]—and empty lists until infinity. The takeWhile only keeps passing results from iterate while the result is not empty—hence stopping when it sees the first empty list and so also avoiding the infinite part. Finally, it takes the first N items from each of the iterate results to end up with the required result.

 chunksOf n
  = map (take n)
  . takeWhile (not . null)
  . iterate (drop n)

This pattern is sometimes called an “unfold,” since it is kind of a fold in reverse— useful for converting some value into a list of results. Hence chunksOf n = unfold (take n) (not . null) (drop n). As an exercise for you, see if you can use unfold to convert an integer to its string representation by repeatedly dividing by 10.

 unfold :: (a -> b) -> (a -> Bool) -> (a -> a) -> a -> [b]
 unfold h p t = map h . takeWhile p . iterate t

The tricky bit is packing words into a line. It’s not immediately obvious, but one good technique is to use an “accumulator” to build up the result before emitting it when some condition is met. This is a standard pattern in FP, and often the first thing to try when the obvious things don’t seem to be relevant. (As another exercise, try to write map in an accumulator style and then compare to the standard definition. You agree which is simpler?)

The real work of packing is done with a local function mlu hidden inside the main function. Line 1 says, when there are no more words to process, return what’s in the accumulator. When the accumulator is empty, line 2 puts the next word into it. Line 3 tests whether the next word can be added to the accumulator to still give a string less than the target length, and if so, it goes on to process the remaining words with a new accumulator. The local definition on line 5 just names the expression pre ++ " " ++ w so we can use it twice without repeating ourselves. Line 4 handles the case when the accumulator can’t accept the next word, and causes the accumulator to be emitted and then the recursive call starts the next line with an empty accumulator.

 makeUpTo :: Int -> [String] -> [String]
 makeUpTo n = mlu []
  mlu pre [] = [pre] -- 1
  mlu [] (w:ws) = mlu w ws -- 2
  mlu pre (w:ws) | length new_pre <= n = mlu new_pre ws -- 3
  | otherwise = pre : mlu [] (w:ws) -- 4
  where new_pre = pre ++ " " ++ w -- 5

We’ve written this as a function for packing strings, but inserting a space is the only detail that ties it to strings. It can be used for packing lists of anything if we pass in the separator element as a parameter, which will give us a useful function that can be used in other contexts (subject to certain assumptions or restrictions).

Let’s recap the main points. The key thing in my view is to think about the data being manipulated and to split complex operations into simpler pieces. It helps if you know the libraries, but I contend that being more aware of the shape of the data at each stage makes it easier to identify missing pieces and to have some idea what to look for— or whether you might need to fill in those pieces with new code. Put another way, it’s about the confidence to think about the higher level and leave the lower level details for later.

What about testing? What do we think we need? At this point, I feel fairly confident that the code is OK. (Testing in the context of maintenance is a different issue, and will be discussed later on.) My intuitive understanding of the spec makes sense and there are no awkward corners that stand out for special treatment. The code seems to follow fairly naturally from this intuitive understanding, and the bit that seemed complex (line packing) is safely isolated in a short function which itself makes pretty good sense. Plus, this short and independent function could be further analyzed or tested quite easily if I wanted more confidence.

Now, is this naive? Or over-confident? Another smug functional programmer? Possibly. I think a little bit of smugness is allowable, though (but staying mindful of the dangers of too much confidence). Generally, functional programmers do understand how to use the language to sidestep obstacles and to break big problems into simpler ones to a point where most of the code becomes more obvious, and from experience we know how to spot complexity and put in relevant effort. For example, the tricky part of the code above is the line packing, so it helps to isolate the tricky bit and keep the rest as simple as we can make it. Then, we come up with line packing code that we’re happy with or else do our best and start testing or proving it in various ways. We don’t test all the things, just the ones where the effort is worth it, and we manage the complexity to limit how much needs that effort.

Though to put it in real terms, would I bet my motorbike on it? Almost yes, though a small sliver of doubt remains. The code leaves certain details implicit, like the assumptions on the input to line packing (for example fragments should not be larger than N) or that the long words are split to one or more fragments of size N followed by zero or one fragments of size less than N. If these assumptions somehow become incorrect, it’s not certain that the code will still work. So, it would be nice to be more sure, as long as it didn’t get too tedious. We’ll see later how far dependent types can help to strike a workable balance.

Bob’s Pipeline Code

Bob then compared his TDD-grown code to a more conventional FP style of coding. The top level function should look familiar, but difficulties arose for him in the intermediate steps—leading to some interesting discussion that will be addressed in the next section. Bob doesn’t claim to be an expert on FP, and this section is certainly not a criticism of his code. Instead, let’s explore how to go from this code towards a more polished version, as a way of explaining the programming style and to help recognize and avoid certain patterns.

Quite a few of you might go through this stage of learning, so hopefully it will help you get to the following stages a little bit more easily.

Again, I’m using Haskell: first because I can and I like it, but more seriously because I think it’s easier to spot certain patterns and features when the code is expressed in the sparser syntax.

 wrap s n
  = intercalate "\n"
  $ make_lines_up_to n
  $ break_long_words n
  $ words s

That’s the top-level function above. It should be understandable by now. Breaking long words happens like this:

 break_long_words n [] = []
 break_long_words n (word:words)
  | n >= length word
  = word : break_long_words n words
  | otherwise
  = take n word : break_long_words n (drop n word : words)

The code is quite straightforward, looping through the words, letting words through if they are short else taking N off the front of the word and looping again with the rest of the word at the head of the other words. No if-expressions in this Haskell version, you notice—it’s doing everything with pattern matching and guards.

But thinking about the data structures involved, and the kind of transformation required, you might realize that it shouldn’t be this complex. Looking more closely, you might start to see that this code is doing several orthogonal things, and that you can tease these apart. You might say, the above code is not exactly following FP’s “single responsibility principle”...

The most important point is that splitting one word is independent of splitting any other, and this independence often means we can use map. Recall how mapping works— applying a function to each element in a list.

 map f [] = []
 map f (x:xs) = f x : map f xs

We can see a shadow of this pattern in break_long_words, though it’s not immediately obvious how to refactor. The obstacle is the detail of actual word splitting. Rather than burn brain cells wondering about the refactoring, let’s just try to isolate the code for single word splitting. It looks like this.

 break_long_words_aux n word
  | length word <= n
  = [word]
  | otherwise
  = take n word : break_long_words_aux n (drop n word)

This is simpler, and clearly does something that could be used for other things. (It’s not tied to words, so can split up lists of anything—its type is Int -> [a] -> [[a]], that is, list of something to a list of lists of something.)

In case you’re wondering, it is a form of loop but not a map or a fold. If anything, it’s kind of a fold in reverse, that is, the same unfold introduced a few pages ago. Notice that the loop is not completely arbitrary or random—there is a structure to it and sometimes it helps to identify which structure. For one thing, it saves having to read a longer definition and then getting annoyed that it is actually not worth the extra code...

One detail remains, which is to ensure we generate a list of fragments after splitting a list of words, given that splitting one word produces a list of fragments and we’re applying this to a list of words to give us a list of lists of fragments. The answer is to use concat :: [[a]] -> [a], which flattens a list of lists by appending the inner lists together— for example concat [[1,2,3],[],[4,5,6]] is equal to [1,2,3] ++ [] ++ [4,5,6] and hence [1,2,3,4,5,6]. Notice how the empty list disappears, much like for 0 in 2 + 0 + 3.

The combination concat with map, typically as concat (map f xs), occurs quite frequently when some function f is used to generate zero or more results (as a list) and mapped over a list of things, and you want to simplify the result. It’s worth getting to know this pattern well. Putting it all together—and using $ to avoid one set of parentheses—we arrive at this:

 break_long_words n ws = concat $ map (break_long_words_aux n) ws

If you yet don’t trust this rewriting, you can expand the definitions of concat and map and end up with code very close to the original version. This is one way to have confidence that your new code does the same thing as the old, and something that is often easier to do in a functional language. Finally, notice also how the new code says something useful about how the code works. It’s not just a collection of symbols that happens to pass the tests.

Next up, the line packing. The auxiliary function does the real work, using two extra arguments to hold the current line being packed and the lines already completed. One easy simplification is to remove the width parameter n from the aux function: it’s bound as a parameter of the main function and doesn’t change throughout the aux function calls, so can be left out.

 make_lines_up_to n words
  = aux_fn n words [] []
  aux_fn n [] line lines
  = lines ++ [unwords line]
  aux_fn n (word:words) line lines
  | n >= length (unwords new_line)
  = aux_fn n words new_line lines
  | otherwise
  = aux_fn n (word:words) [] (lines ++ [unwords line])
  new_line = line ++ [word]

As before, thinking about the data structures and visualizing the transformation as a pipeline suggests various simplifications. The input is a list of fragments and the output is a list of (packed) lines. When packing, we put as many fragments as possible into the current line before spitting it out and going onto the next line, just like a hay baling machine on a farm. This suggests we can simplify the (already processed) “lines” accumulator. Once this detail is factored out, the code starts to look like my simpler version.

So, you might have followed the discussion and agreed with the code changes, but the important question is, can you “internalize” these ideas and start applying them successfully yourself? Here’s what I suggest:

  • always think about the data structures and look for a straightforward way to do the transformations

  • know and understand how to use the key operations like mapping, folding, and filtering, and to a lesser degree other patterns like unfolding and accumulators, and always look for opportunities to use them in an appropriate way (but don’t over-use them)

  • always review your code and ask whether it is doing orthogonal things

  • think about whether you can split complex operations into (pipelines of) simpler stages, possibly by introducing new data structures for an intermediate phase

Talking About It

After presenting his second version, Bob mentions the difficulties encountered when developing the code in an unfamiliar style, and says “it’s hard for me to believe that my [TDD] solution to the word wrap is inferior to the [second version].” In the context, it is a fair point, though it does depend on a few assumptions.

Rather than argue about these assumptions (which could take some time), let’s consider what we’ve seen here. I’ve shown an alternative way to approach the problem that has a stronger functional flavor, namely being more up front about the data structures being manipulated and using the language features to simplify some of the code. Tests have not played a significant role in the code’s development, though they have been useful as a check on functionality.

What do you think? Now the approach and the technique have been explained, does my alternative seem more understandable, or less? Do you have more confidence in its correctness, or less? Which version would you prefer to maintain? And how would you like to program this kind of problem, imagining if you could use any language—past, present, or future? We’d welcome your views on the PragPub forum!

Combining TDD and Functional Thinking

As Bob demonstrated, TDD is indeed possible in a functional setting. I’ve argued for being able to think about the wider problem and use that insight in the coding process. Can we have our cake and eat it, that is, combine the strengths of these approaches? Here are two ideas to ponder.

First, on how to get more mileage out of existing tests when we decompose some operation into a pipeline. For example, if we decide that wrap should start off with a word-splitting stage (as done above), what can we do about testing the rest of the stages? Do we lose our tests? Or do we have to make up new ones? Happily, no. We can instead apply the first parts of the pipeline to the test input to get the input to be tested in the later stages. For example:

 -- suppose that 'wrap' can be decomposed into three parts
 wrap n s = stage3 $ stage2 n $ stage1 n s
 -- and we decide that stage1 is this
 stage1 n s = concat $ map (chunksOf n) $ words s
 -- and given this test case
 (Test7) wrap 3 "x xxxx" == "x\nxxx\nx"

Then we can use what we know about stage1 to derive a new test case automatically that indicates how stage3 plus stage2 should behave, and we do this by running stage1 on the original input to get the resulting input that stage2 will get. That is, stage1 3 "x xxxx" will give ["x", "xxx", "x"] hence we get a new test case of

 -- replacing 'stage1 3 s' with its output
 (Test7a) stage3 $ stage2 3 ["x", "xxx", "x"] == "x\nxxx\nx"

We can do a similar trick on the other end of the pipeline in certain cases—specifically when the final stage(s) (here stage3) are functions that can be run in reverse, so we can work out what the input was given their output. (In technical terms, when stage3, etc., is a bijection. Bijections got a bit of fame on Twitter recently...) So in the wrap example, if stage3 is intercalate "\n" then—assuming the input didn’t contain any newlines—we can do the inverse operation by splitting on newlines. Hence with our example, we can work out the resulting test for just stage2.

 -- using 'stage3' in reverse
 (Test7b) stage2 3 ["x", "xxx", "x"] == ["x", "xxx", "x"]

So a simple way to get more mileage out of existing tests, but still requiring a bit of manual work.

Second, some of the newer programming environments actually automate some of the manipulations above, and allow new possibilities. Specifically, the proof assistant style of interface pioneered in dependent types (especially the more advanced interfaces in Agda and Epigram) allow programs to be developed interactively and run or tested before they are complete, even showing the partial results on various test cases using the code that has been filled in. For example, if we defined wrap to have three stages but only gave actual code for the first stage (leaving the rest as “undefined”), and tried to run a test case, it would do as much as it could using the code for stage one and then show what it was left with—which would be the expected input for stage two, etc. These are powerful and exciting tools, opening up new and interesting ways to develop code. I aim to demonstrate more of this next month.

Time for some Types

There’s not too much opportunity to use complex types in this code, but note that types were always there in the background, supporting what we were doing.

They help to manage the transformation from a single string to a list of words, to a list of word fragments, then the packaging of these into a list of strings. We’re using the String type for fragments and for lines, but there’s nothing to stop us adding synonyms or abbreviations (for example type Word = String) if it helps remind us what is going on where.

A further step is to wrap up the various strings inside new types that allow firm distinctions between (for example) fragments and lines. Then, the line packing code would have a type Int -> [Fragment] -> [Line], and the type checker would be able to protect against another potential class of errors. Is this overkill? Maybe. It partly depends on the importance placed on a code component being correct, and the confidence that we have in the techniques or design we are using. (Consider the risk of confusing different units, like cm vs inches, and the various real consequences that pop up in the news... It’s the same kind of situation.)

Note that adding such new types in Haskell takes little effort, usually much less effort than setting up a new class in OO languages, and the cost of such techniques may be an acceptable given the potential added confidence.

There’s a lot that Haskell-style types still can’t say, and that tests don’t really help with either. Like, are we sure that the line packing code (any version) always generates a line that fits inside the given width? For how much are we still assuming things or crossing our fingers? Fortunately, we have the technology to do better, and it doesn’t involve pen & paper.

Dependent Types

Dependent types were introduced in an earlier article in this series as a richer language to explain what a program was doing, encoding both structural information and proofs about properties.

In closing, here are some hints on how the additional capabilities of dependent types might be used to improve confidence in the code:

  • does long word splitting always produce the right size and order of fragments?

  • will line packing never overflow, assuming that the input is valid?

  • guarantee that the output doesn’t add or delete or permute non-space characters

Next month I’ll discuss how to write this word-splitting program in Idris. Idris is being developed by Edwin Brady (of WhiteSpace fame) as a practically-oriented dependently-typed programming language. It now also compiles to Javascript, thus opening up many more interesting possibilities for browser programming! I’m excited about it, anyway.

Dr Paul Callaghan has been programming with Haskell for a while. Bits of his bio can be seen on earlier articles. Paul also flies big traction kites and can often be seen being dragged around inelegantly on the beaches of North-east England, much to the amusement of his kids. He blogs at and tweets as @paulcc_two.

Send the author your feedback or discuss the article in the magazine forum.

Paul Callaghan thanks Bob Martin for the interesting discussions.