5

在 Prolog 中，我经常通过提供模板（包含变量的结构）然后满足一组约束来解决问题。一个简单的例子可能是：

go(T) :-
    T = [_, _, _],
    member(cat, T),
    member(dog, T),
    member(mouse, T).

在实践中，约束集是通过其他方式生成的，而不是固定的，我必须编写一个递归谓词来依次满足每个约束：

go(T) :-
    T = [_, _, _],
    findall(A, animal(A), As),
    % satisy member(A, T) for each A in As
    fill_in_animals(T, As)

fill_in_animals(T, []).
fill_in_animals(T, [A|Rest]) :-
    member(A, T),
    fill_in_animals(T, Rest).

请注意，我的问题与列表相关的约束无关，甚至约束的参数也不能总是很容易地生成为要传递给上面使用的相对简单的辅助谓词的列表。在实践中，我发现 helper 是一个我每次都写的相当笨拙的谓词，它：

  1. 接受一个模板，用于约束的几个参数（因此用于将模板的变量绑定到有用的值），以及一个用于指示它取决于哪个约束的变量。
  2. 生成要在此迭代中满足的约束，并将其应用于模板。
  3. 递归调用自身，以便满足剩余的约束。

我正在寻找的是一个类似于findall, etc 的谓词，它将一个接一个地满足一组目标。就像是：

% satisfyall(:Goal)
% backtracks on Goal but keeps all bindings from each fully satisfied goal.

satisfyall((animal(A), member(A, T)))

我正在寻找的答案不一定是这种形式。事实上，在回溯目标和维护由此产生的每组绑定之间可能存在矛盾。

我希望我已经解释了我的问题，以便清楚地知道什么会有所帮助。（如果不让我知道。）提前为这个冗长的问题道歉！

更新（2年后）

我将在今天晚些时候尝试并更新我的问题！

请注意，我从未说过我会在尝试的同一天更新问题。;-)

@CapelliC 引导我朝着正确的方向前进，我发现了一种似乎运作良好的模式：

?- Gs = [member(red),member(blue)], T = [_,_], foreach(member(G, Gs), call(G, T)).
T = [red, blue] ;
T = [blue, red] ;
4

2 回答 2

3

satisfyall/1您在问题中描述的情况与您给出的谓词签名略有不同。示例中没有涉及回溯fill_in_animals，至少对于流出go/1. 子目标的满足可能存在“小回溯”，但总体目标不会失败，同时保持绑定完好无损。

一个陈旧且可能无用的解决方案是使用maplist/2. 例如，您的示例很容易以这种方式实现：

?- length(L, 3), maplist(animal, L).
L = [cat, cat, cat] ;
L = [cat, cat, dog] ;
L = [cat, cat, mouse] ;
L = [cat, dog, cat] ;
...
L = [mouse, mouse, dog] ;
L = [mouse, mouse, mouse].

您可以通过仅添加一个谓词来继续使用物化数据库：

% just flips the arguments of member/2
memberof(L, A) :- member(A, L).

然后我们可以使用findall/3来做这项工作：

?- findall(A, animal(A), Animals), 
   length(L, 3), 
   maplist(memberof(Animals), L).

Animals = [cat, dog, mouse],
L = [cat, cat, cat] ;
Animals = [cat, dog, mouse],
L = [cat, cat, dog] ;
Animals = [cat, dog, mouse],
L = [cat, cat, mouse] ;
...
Animals = [cat, dog, mouse],
L = [mouse, mouse, dog] ;
Animals = [cat, dog, mouse],
L = [mouse, mouse, mouse].

这应该清楚为什么 lambda.pl 会有所帮助。你不需要辅助谓词，你可以简单地写：

?- findall(A, animal(A), Animals), 
   length(L, 3), 
   maplist(\Animal^member(Animal, Animals), L).

（未经测试）

如果您真的打算规避变量绑定和解除绑定，我认为您将为自己制造一个调试噩梦，但是 SWI-Prolog 有一个您可以使用的全局变量工具。我隐约记得在某处读过asserta/retract不足以完成这项任务。

我想得越多，我就越觉得不会有一个有意义的实现，satisfyall/1它与maplist/2.

于 2013-06-19T15:11:37.327 回答
1

您肯定知道回溯需要撤消所做的更改才能正常工作。这就是 Prolog 算法的核心，也是 Prolog 力量的源泉。

当涉及到更常见的计算时，这也是一个弱点，例如那些必然涉及副作用或循环的计算。

找到正确的方法来强制我们的规则沿着确定的路径工作可能很困难，可能是因为这不是 Prolog 应该工作的方式。

好吧，现在，停止哲学咆哮，让我们看看 Prolog 的大师为我们提供了什么：SWI-Prolog 提供库（聚合），您可以在其中找到foreach，我认为它可以满足您的大部分需求：

?- foreach(animal(X), member(X,L)).
L = [cat, dog, mouse|_G10698] .

研究如此复杂的内置函数可以为您的实现提供一些想法（?- edit(foreach).从控制台使用来检查源代码）。

请注意，它将生成器和目标分开，而在您的问题中，它们毫无希望地团结在一起。这当然需要能够仅在生成器部分上回溯。

顺便说一句，尝试了解文档页面中的小示例列表。dif/2 过于复杂，但您确实需要掌握绑定的行为才能泛化您的递归谓词。

高温高压

于 2013-06-20T10:12:38.890 回答