Functional Programming: A PragPub Anthology

Breadth-First Searching

What’s next? We can call one_step "lead" to get a list of next steps, and call one_step on any of the new words and so on. But we’re after the shortest path between two words, so we need a controlled way of exploring how steps are related in order to find such a path. The obvious thing is to try all one-step paths, then all two-step paths, then three, etc.

This kind of process is called a “breadth-first search” (BFS). I’ll show you a version of BFS that is phrased in terms of exploring a “state space.” This framework also makes it easier to experiment with other kinds of searching, like best-first search. The parent-to-list-of-children relationship suggests a tree, so let’s program it this way. (More generally, it could ...