8 
?- permutation([A,B,C],Z).
Z = [A, B, C] ;
Z = [A, C, B] ;
Z = [B, A, C] ;
Z = [B, C, A] ;
Z = [C, A, B] ;
Z = [C, B, A] ;
false.

说得通。我可以处理 的排列，[A,B,C]并且该排列包含与 中相同的元素[A,B,C]，因此我对这些元素所做的一切都将适用于我的原始列表。

现在：

?- findall(X, permutation([A,B,C], X), Z).
Z = [[_G1577, _G1580, _G1583], [_G1565, _G1568, _G1571], [_G1553, _G1556, _G1559], [_G1541, _G1544, _G1547], [_G1529, _G1532, _G1535], [_G1517, _G1520, _G1523]].

为什么？？为什么findall/3给我包含完全不相关变量的列表，而不是A,B,C？中的列表Z甚至没有相互关联，所以我得到的结果实际上只是 6 个长度为 3 的随机列表，这完全不是我查询的。

通过这种行为，我们会得到如下荒谬的结果：

?- findall(X, permutation([A,B,C],X), Z), A = 1.
A = 1,
Z = [[_G1669, _G1672, _G1675], [_G1657, _G1660, _G1663], [_G1645, _G1648, _G1651], [_G1633, _G1636, _G1639], [_G1621, _G1624, _G1627], [_G1609, _G1612, _G1615]].

从逻辑的角度来看，这没有任何意义。

我知道这findall/3不是一个真正的关系，纯逻辑谓词，但我不明白这如何证明这里显示的行为是合理的。

因此，我的问题是：

  • 为什么为谓词选择这种行为？

  • 是否存在这种行为实际上比我想要的行为更可取的常见情况？

  • 如何实现具有findall/3我想要的行为的版本？

4

3 回答 3

10

为什么为谓词选择这种行为？

findall/3是一个高度原始的内置谓词，相对容易实现，并且不能解决您感兴趣的所有细节。至少它是可重入的 - 因此可以递归使用。

从历史上看，DEC10 Prolog 没有记录findall/3. 也就是说，1978 年和 1984 年都没有。但是 1984 年的版本确实提供setof/3了在内部使用类似 findall 的谓词。在 ISO-Prolog（没有findall/3）中实现它是相对棘手的，因为您必须处理错误和嵌套。许多实现依赖于实现特定的原语。

是否存在这种行为实际上比我想要的行为更可取的常见情况？

如果没有解决方案，Findall 成功，而两者都setof/3失败bagof/3了。这可能是喜欢它的原因。至少有一些比所需要的更复杂的结构，这些结构很可能是基于 findall 构建的。

在存在约束的情况下它会变得非常混乱。事实上，它是如此混乱，以至于截至目前我仍然不知道在这种情况下会以合理的方式处理 clpfd-constraints 的实现。考虑到：

?- findall(A, (A in 1..3 ; A in 5..7), As).

在这里，SWI 复制约束，而 SICStus 不会复制它们，因此您可以将其用作更复杂实现的构建块。

如何实现具有我想要的行为的 findall/3 版本？

首先，考虑setof/3和bagof/3（这里）。也许您已经对它们感到满意-只要不涉及任何限制...

于 2017-06-23T19:47:22.177 回答
4

您最后一个问题的解决方案。

?- setof(X,permutation([A,B,C],X),Z).
Z = [[A, B, C], [A, C, B], [B, A, C], [B, C, A], [C, A, B], [C, B, A]].

如果我们查看 sicstus 上对 findall 的描述，我们会看到

findall(?Template,:Goal,?Bag) ISO Bag 是 Prolog 找到的所有 Goal 证明中 Template 实例的列表。列表的顺序对应于找到证明的顺序。该列表可能是空的，并且所有变量都被认为是存在量化的。这意味着 findall/3 的每次调用只成功一次，并且没有绑定 Goal 中的变量。避免管理普遍量化的变量可以节省大量时间和空间。

所以我猜存在量化会造成 findall 这种不受欢迎的行为。

于 2017-06-23T19:31:03.440 回答
3 
?- findall(X, permutation([A,B,C],X), Z), A = 1.

在这个查询中，Prolog 将找到列表 [A,B,C] 中元素的所有排列，但由于 Prolog 无法实例化变量 A、B、C，因此结果将是您得到的匿名变量：

Z = [[_G1669, _G1672, _G1675], [_G1657, _G1660, _G1663], [_G1645, _G1648, _G1651], [_G1633, _G1636, _G1639], [_G1621, _G1624, _G1627], [_G1609, _G1612, _G1615]].

另一方面，如果你先实例化变量 A、B 和 C，你会得到不同的结果：

?- A=1, B=2, C=3, findall(X, permutation([A,B,C],X), Z).
A = 1,
B = 2,
C = 3,
Z = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

这在您的查询中以前没有发生过，findall(X, permutation([A,B,C],X), Z), A = 1.因为 Prolog 将首先尝试解决条件findall(X, permutation([A,B,C],X), Z)，然后A = 1

于 2017-06-23T19:30:47.657 回答