Combinators for breadth-first search
Combinators for breadth-first search
复制标题
用于广度优先搜索的组合器
DOI：
10.1017/s0956796800003749
复制
发表时间：
2000
影响因子：
1.1
通讯作者：
Michael Spivey
中科院分区：
文献类型：
--
作者：
Michael Spivey
每一个函数式程序员都知道“用成功列表代替失败”的技巧（Wadler，1985），但聪明的程序员也意识到列表可能是空的或（更糟糕的）发散的。事实上，“成功列表”技术相当于Prolog中使用的不完整的深度优先搜索策略。本质上，这个想法很简单：每当我们想使用一个“多函数”，比如“f”[ratio ][ratio ] α [Ratio] β，它可以返回许多结果或不返回任何结果，我们用一个真正的函数f [ratio ][ratio ] α → β stream来代替它，它返回一个懒惰的结果流，并依靠懒惰的计算来一次计算一个答案，并且只在需要的时候计算。为了清楚起见，我将区分有限列表（α列表）和潜在无限惰性流（α流）的类型，尽管两者可以以相同的方式实现。遵循ML中使用的约定，类型构造函数遵循其参数类型。
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.