Combinators for breadth-first search

Abstract

Every functional programmer knows the technique of “replacing failure by a list of successes” (Wadler, 1985), but wise programmers are aware also of the possibility that the list will be empty or (worse) divergent. In fact, the “lists of successes” technique is equivalent to the incomplete depth-first search strategy used in Prolog.

At heart, the idea is quite simple: whenever we might want to use a ‘multi-function’ such as ‘f’ [ratio ][ratio ] α [Rarr ] β that can return many results or none, we replace it by a genuine function f [ratio ][ratio ] α → β stream that returns a lazy stream of results, and rely on lazy evaluation to compute the answers one at a time, and only as they are needed. For the sake of clarity, I will distinguish between the types of finite lists (α list) and of potentially infinite, lazy streams (α stream), though both may be implemented in the same way. Following the conventions used in ML, type constructors follow their argument types.