On the road to functional programming enlightenment, I discovered two beautiful one-liners for depth-first and breadth-first search in Haskell. Here they are:
dfs, bfs :: (a -> [a]) -> a -> [a] dfs succ start = start : concatMap (dfs succ) (succ start) bfs succ start = concat $ takeWhile (not . null) $ iterate (concatMap succ) [start]
Both functions generate the list of states reachable from a starting state in a finite number of steps. The inputs to
dfs are the starting state and a “successors” function taking a state to the list of its “child” states.
What consistently impresses me about Haskell is that algorithms can be expressed in code as concisely as in English, if only you can learn the language to the same level of native fluency. As a native English speaker who’s only been writing Haskell casually for a year, I puzzled over the two one-liners in this post for about an hour before getting them right!
For the simple one-liner versions, I had to assume that the search space was a tree, i.e. no two paths to the same state. This special case is useful in practice, for example in problems that build a sequence of words or letters one step at a time. And since discovering it, I’ve used
dfs exactly as above in a fun and simple palindromes-generation program which I may post here soon.
But for illustration, consider the following crudely rendered test tree in which states are just numbers rather than sequences of words:
1 / | \ 2 3 4 / | \ / | \ / | \ 5 6 7 8 9 10 11 12 13 / \ 14 15
Here it’s intended that 2, 3, and 4 are the successors of 1, and so forth. To represent this tree in a way compatible with the
dfs combinators above, we need to describe successors as an
Int -> [Int] function, e.g.
testSucc 1 = [2,3,4] testSucc 2 = [5,6,7] testSucc 3 = [8,9,10] testSucc 4 = [11,12,13] testSucc 8 = [14,15] testSucc _ = 
With this test data in place, depth-first search is simple to describe: it immediately yields the start node, then recursively calls
dfs (with the same successors function) on each successor of the start node, and concatenates those results, or
dfs :: (a -> [a]) -> a -> [a] dfs succ start = start : concatMap (dfs succ) (succ start)
as we said above. After loading our code into the GHCi REPL, we have
*Main> dfs testSucc 1 [1,2,5,6,7,3,8,14,15,9,10,4,11,12,13]
as we should expect, and
*Main> dfs testSucc 2 [2,5,6,7] *Main> dfs testSucc 3 [3,8,14,15,9,10] *Main> dfs testSucc 4 [4,11,12,13]
which, concatenated, give
tail (dfs testSucc 1). Cool.
I’ll note that the restriction to trees can certainly be patched, in the totally standard way by tracking a set of visited states so that no state is “expanded” more than once. A cost is paid in elegance as our code has ballooned from one line to four!
dfs2 :: (Ord a) => (a -> Set a) -> a -> [a] dfs2 succ start = loop [start] (Set.singleton start) where loop  _ =  loop (x:xs) visited = x : loop (Set.toList new ++ xs) (Set.union visited new) where new = Set.difference (succ x) visited
Breadth-first search can be written nearly identically, by changing the “frontier” (first parameter to
loop) from a stack to a queue, though efficient queues are not entirely trivial to implement in functional programming (whereas Haskell’s immutable linked lists make fine stacks).
And so I was pretty happy to find a functional
bfs one-liner without explicit mention of queues. It’s just slightly more complicated than
dfs, the meat of the definition lying in the expression
iterate (concatMap succ) [start]
which generates a list of all the “levels” of the search space. Here I mean that the singleton list
[start] is level 0, successors of start constitute level 1, successors of level 1 states constitute level 2, and so on. That’s what
concatMap succ does: for a list of nodes in some level
n, it finds all successors of all of them, i.e. it generates the next level
iterate, which has type
(a -> a) -> a -> [a], is a very useful combinator and really a beautiful poster child for Haskell’s lazy semantics. Given a starting value, it generates an infinite list by repeatedly applying a function to the last generated value. Just don’t try to print the whole thing!
*Main> take 10 $ iterate (*2) 1 [1,2,4,8,16,32,64,128,256,512]
Or in the context of
bfs, of course we get the levels of the tree:
*Main> take 10 $ iterate (concatMap testSucc)  [,[2,3,4],[5,6,7,8,9,10,11,12,13],[14,15],,,,,,]
with infinitely many empty levels at the end. This is easily cleaned up to a working implementation of breadth-first search as above:
bfs :: (a -> [a]) -> a -> [a] bfs succ start = concat $ takeWhile (not . null) $ iterate (concatMap succ) [start]
In GHCi, we get
*Main> bfs testSucc 1 [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]