Let’s see, we’re generating and filtering, right? So let’s consider the operation that generates potential words for later filtering. Type-wise, we want generate_candidates :: String -> [String], so that from a given word we get all possible next steps.
It’s always good to start with some concrete examples, especially if the operation doesn’t seem obvious.
From generate_candidates "", we expect no candidates, since there’s no way to change a single character in an empty string.
From generate_candidates "a", we expect ["b", "c", ... "z"], because we change the character to every other character except "a".
From generate_candidates "ba", we expect ["aa", "ca", "da", ... "za", "bb", "bc", ... "bz" ], which is the list from changing the first character, plus the list from changing the second character.
There’s a bit of a pattern here (which we should look to exploit in the code), but it’s not obviously a map or a filter or a fold, so what do we do now? The functional programmer’s next tactic is usually to start thinking about the main cases of the input. (The editor, who learned Lisp at a tender age at the feet of the legendary Dan Friedman, waves his hand and says, “Ooh, ooh, I know this one!”) Uh, yes. This means thinking about (a) the empty list case and (b) the cons case.
One benefit of thinking via patterns is that we can think about the cases independently, and looking at the preceding examples, we’ve already done the first case (there are no candidates) so let’s fill it in. This leaves:
| | generate_candidates [] |
| | = [] |
| | generate_candidates (c:cs) |
| | = error "don't know" |
Progress!
OK, the cons case requires some thought. It is highly likely to involve recursion somewhere, and the trick of writing recursive code is to think about possible recursive calls and what they give you, and from the results think of how to construct what you actually want. In this case, we can call generate_candidates on any string we like, but it’s likely to be the tail of the input (or maybe a substring of it). Let’s guess a call to generate_candidates cs (to produce all candidates from the tail string) and see where it gets us, specifically thinking about how we can use c, cs, and the result from generate_candidates cs to build the result.
But let’s also think about the concrete examples for "ba" and "a" from the preceding code. The latter will be the result from the recursive call when processing "ba", so can we do something to ["b", "c", ... "z"] to get (part of) the overall result? Well, if we put character b at the front of each of the strings, we get the last part of the result list. Let’s fill this in.
| | generate_candidates [] |
| | = [] |
| | generate_candidates (c:cs) |
| | = error "don't know" |
| | ++ [ c : xs | xs <- generate_candidates cs ] |
Syntax [ expr | pattern <- list ] indicates a “list comprehension,” also seen in CoffeeScript, Python, and certain branches of set theory. It is a very convenient shorthand for combinations of maps and filters on lists, and it translates to a combination of map, filter, and list concatenation. The preceding code produces a new list by looping through the elements produced by the recursive call and sticking head character c on the front of each—it’s a map, in other words.
The first case isn’t too hard either: it’s the result of putting any letter except for c at the front of the list tail cs. We can use a list comprehension here too, with a filtering step that skips the original character.
| | generate_candidates [] |
| | = [] |
| | generate_candidates (c:cs) |
| | = [ x : cs | x <- ['a'..'z'], x /= c ] -- new at front |
| | ++ [ c : xs | xs <- generate_candidates cs ] -- old at front |
Observe that when we’re dealing with a one-character string, the recursive call will return an empty list, and mapping over it also produces an empty list, which is safe to append to the rest of the result. In short, we don’t have to handle this situation as a special case—it just naturally slots into place.
We can test generate_candidates on the concrete examples and confirm that we get the expected outcome.
But our purpose here is understanding, not just correctly executing code. So let’s pause a bit to consider whether the code makes sense, and whether it gives a clear enough view of how this part of the program works. I don’t give cut-and-dried answers here, and I encourage you to think about what you want from the code and not just to accept current limitations on our understanding!
We’ve reached this version of the code by a few careful steps of reasoning, filling in pieces at a time, and we did understand each step. Are we therefore confident that the code is correct, with or without testing? Is confidence alone enough? On the other hand, how can we be confident that our tests are sufficient?
What about alternative coding approaches? This is a book on functional programming, and I have been cheerleading functional thinking, but let’s ask: what would an imperative or OO programmer do here? Would we be happier with an imperative or OO version? One possibility is an outer loop on the string position and an inner loop on the replacement letters, generating a new candidate word on each iteration. Here’s a version of the code that works along such principles.
| | generate_v2 w = [ before ++ d : tail after |
| | | (before, after) <- all_splits_of w |
| | , not (null after) |
| | , d <- ['a' .. 'z'] |
| | , d /= head after ] |
| | all_splits_of :: [a] -> [([a], [a])] |
| | all_splits_of w = zip (inits w) (tails w) |
The all_splits_of function returns all ways of splitting a list into two while keeping the original element order; for example, all_splits_of "lead" will give [("","lead"),("l","ead"),("le","ad"),("lea","d"),("lead","")]. We then loop over this list, replacing the head of the second part with a different character and rebuilding the string (except when the second part is empty). Is this clearer? Or can you find another version that does make more sense?
In the words of the immortal Tim Toady, TMTOWTDI.
It’s worth noting that this version touches on recent FP research on views: the idea is that we choose a view of the data that simplifies the code, rather than always working with a particular physical representation. (It has some relationship with the concept of views in databases.) So we view a list as the join of two lists, and then loop through the various ways of splitting the list to get our answer. The FP work in views started with Philip Wadler, and has been expanded significantly by Conor McBride in the context of dependently typed programming (for example, in Epigram).[13]