在Prolog中实现一组目标

Question

在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).

请注意，我的问题不涉及列表相关的约束条件，即使是用于约束的参数也不能总是轻松生成为列表以传递到像上面使用的相对简单的帮助谓词中。实际上，我发现这个辅助谓词是一个相当笨拙的谓词，每次都需要编写：

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

我正在寻找的是一种类似于“findall”等的谓词，它将按顺序满足一组目标。例如：

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

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

我所需要的答案并不一定是这种形式。事实上，回溯一个目标和维护由此产生的每个绑定集之间可能存在矛盾。

我希望我已经解释清楚了我的问题，因此可以帮助到我。如果没有，请告诉我。提前为冗长的问题道歉！

更新（两年后）

我会在今天晚些时候试一下，并更新我的问题！

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

@CapelliC指导了我正确的方向，我找到了一个似乎运作良好的模式：

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

- Edmund

---

lambda.pl 可以帮助，但我认为你应该使用 findall/3。 - CapelliC

@DanielLyons：我想我批评得太多了，没有建设性。但我只是在报告我的经验（有时候最好闭嘴……） - CapelliC

我可能过度解读这个问题，但它似乎涉及到两个有趣的想法。一个是使用部分绑定结构（您的模板）来表示单个约束的结果。另一个是一个包装器，对一系列参数化约束进行全部量化，并以串行方式应用于部分绑定结构。 - hardmath

@hardmath - 听起来正是我想要的。请注意，这不是计算某些东西的问题，而只是希望以比我的特定递归谓词更简洁的方式实现它的愿望。 - Edmund

apply(G,[T])已经过时了！请使用call(G,T)。 - false

Answer 1

您描述的问题情况与您提供的谓词的签名略有不同。在示例中，至少与流出的变量相关联没有回溯。在子目标满足方面可能存在“小型回溯”，但整体目标不会失败，同时保持绑定完好。

一个陈词滥调且可能无用的解决方案是使用。例如，您的示例可以轻松实现此方式：

?- 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会有帮助的原因。你不需要helper谓词，只需写成这样即可：

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

(未测试)

如果您真的想绕过变量绑定和解除绑定，我认为您会为自己创造一个调试噩梦，但是SWI-Prolog有一个全局变量功能，您可以使用。我模糊地记得在某个地方读到asserta/retract对于此任务不足。

我越想越觉得，从实质上区别于maplist/2的satisfyall/1没有意义，但我期待被证明错误。

- Daniel Lyons

---

我不熟悉lambda.pl，之前也不知道maplist，但是maplist似乎可以让我达到80%的目标。我今天稍后会尝试一下并更新我的问题！ - Edmund

我希望@hardmath或其他人能够想出satisfyall/1的方法，让你走得更远。除了简单地依赖于通常的统一过程之外，我没有看到利用模板结构的直接方法。希望其他人有更好的想象力，并能找到前进的方法。 :) - Daniel Lyons

应该在全局范围内声明 Animals：maplist(Animals+\Animal^member(Animal, Animals), L)。 - false

Answer 2

你肯定知道回溯需要撤销已完成的工作。这是Prolog算法的核心，也是Prolog强大的源泉。

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

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

现在，停止哲学辩论，让我们看看Prolog专家为我们提供了什么：SWI-Prolog提供库(aggregate)，其中包含foreach，我认为它可以做到你想要的大部分功能。

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

学习这样复杂的内置函数可以为您的实现提供一些想法（使用?- edit(foreach)从控制台检查源代码）。

请注意，它将生成器和目标分开，而在您的问题中它们无望地合并在一起。当然，这是必要的，以便仅在生成器部分上进行回溯。

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

希望对您有所帮助

- CapelliC

---

嘿，抱歉回复晚了。我认为你已经让我找对了方向。 - Edmund