10

我做了一个 Prolog 谓词posAt(List1,P,List2)来测试位置 和 的元素P是否List1相等List2：

posAt([X|Z], 1, [Y|W]) :-
   X = Y.
posAt([Z|X], K, [W|Y]) :-
   K > 1,
   Kr is K - 1,
   posAt(X, Kr, Y).

测试时： 

?- posAt([1,2,3], X, [a,2,b]).

我期望输出，X = 2但我收到以下错误：

ERROR: >/2: Arguments are not sufficiently instantiated

为什么我会收到此错误？

4

5 回答 5

9

Prolog 谓词是参数之间的关系，你的陈述

List1 和 List2 的位置 P 处的元素相等

显然是一个可以有多种解决方案的例子。

?- posAt([1,2,3],X,[1,5,3,7]).
X = 1.

因此，sharky 的回答虽然清楚地解释了为什么会出现技术错误，但需要稍作修正：

posAt([X0|_], Pos, Pos, [X1|_]) :-
    X0 == X1.

现在它按预期工作。

?- posAt([1,2,3],X,[1,5,3,7]).
X = 1 ;
X = 3 ;
false.

为列表处理编写简单的谓词是一种非常有价值的学徒实践，也是有效学习语言的主要方式。如果您也倾向于研究可用的库谓词，这里是使用库中的 nth1/3 的版本（列表）

posAt(L0, P, L1) :-
   nth1(P, L0, E),
   nth1(P, L1, E).

这输出：

?- posAt([1,2,3],X,[1,5,3,7]).
X = 1 ;
X = 3.

尝试理解为什么在这种情况下 SWI-Prolog“顶级”解释器能够推断出解决方案的确定性可能会很有趣。

于 2012-03-20T08:18:25.537 回答
7

这是因为，当K > 1Prolog 评估子目标时，K它仍然是一个未绑定的变量而不是一个数字。标准 Prolog 不能（不会）评估数值范围限制的真/假值，例如当它们不接地时（与 CLP 等约束求解器相反，它允许这样做但工作方式不同）。

考虑这个解决方案：

posAt(L0, Pos, L1) :- 
    posAt(L0, 1, Pos, L1).

posAt([X0|_], Pos, Pos, [X1|_]) :-
    X0 == X1.    
posAt([_|X0s], CurrPos, Pos, [_|X1s]) :-
    NextPos is CurrPos + 1,
    posAt(X0s, NextPos, Pos, X1s).

第一个谓词posAt/3设置初始条件：列表为位置 1，并调用posAt/4迭代列表。

的第一个子句posAt/4是匹配条件：两个列表中相同位置的元素相等。在这种情况下，当前位置变量与Pos结果统一。

如果上述子句由于列表元素X0和X1不相等而失败，则列表位置CurrPos增加一，并且递归调用posAt/4再次开始处理下一对项目。

编辑：删除了第一个子句中的不正确剪切posAt/4（感谢@chac 的拾音器）

于 2012-03-20T05:23:25.487 回答
2

此类问题的一般解决方案是约束。

使用进行适用于所有方向的整数运算：

:- use_module(library(clpfd)).

posAt([X|_], 1, [X|_]).
posAt([_|X], K, [_|Y]) :-
   K #> 1, 
   Kr #= K - 1,
   posAt(X,Kr,Y).

通过这些简单的更改，您的示例完全按预期工作：

?- posAt([1,2,3], X, [a,2,b])。
X = 2 ;
错误的。
于 2015-12-02T18:06:51.917 回答
2

（这只是在我的仪表板上弹出，因此答案很晚......）

我查看了这个问题，并在考虑是否可以提供接近原始问题的解决方案。正如已经解释的那样，问题是关系>需要实例化它的参数。其实类似的is。但是，这可以通过重新排序目标轻松解决：

posAt([X|_], 1, [X|_]).
posAt([_|X], K, [_|Y]) :-
   posAt(X, Kr, Y),
   K is Kr+1,
   K > 1.

这个解决方案是运行时在两个列表的长度上是线性的，只要K是接地的。但是，如果列表中的第一个元素确实匹配，则存在一个问题，如重复答案中很好地说明的那样。

事实上，最后一个元素是多余的，因此是等价的。

posAt([X|_], 1, [X|_]).
posAt([_|X], K, [_|Y]) :-
   posAt(X, Kr, Y),
   K is Kr+1.

然而，正如@repeat 所证明的那样，这段代码非常慢。这可能是因为代码破坏了尾递归。

一个合乎逻辑的干净解决方案将解决这个问题。在这里，我们将使用 Peano 公理（s/1 后继或关系）表示自然数，解决方案将变为

posAt([X|_], zero, [X|_]).
posAt([_|X], s(K), [_|Y]) :-
   posAt(X, K, Y).

然而，这很难计时，因此，一个黑客解决方案大致相当于

  posAt([X|_], [a], [X|_]).
  posAt([_|X], [a|L], [_|Y]) :-
      posAt(X, L, Y).

计时此解决方案给出

N=8000,numlist(1,N,_Zs), length(_LN,N),time(posAt(_Zs,_LN,_Zs)).
 7,999 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 7342035 Lips)
N = 8000
于 2016-02-09T07:08:48.120 回答
2

TL;DR：@CAFEBABE、@CapelliC、@mat和@sharky 的答案都达不到要求！

那么......之前提出的答案的缺点到底是什么？

  • @CAFEBABE 说：

    这个解决方案的好处是运行时间在两个列表的长度上是线性的。

    让我们来测试一下这个说法！

    ?- numlist(1,1000,Zs), time(posAt__CAFEBABE1(Zs,1000,Zs))。
% 999,001推理，0.090 CPU 在 0.091 秒内（100% CPU，11066910 Lips）
Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ;
% 4 次推理，0.000 秒内 0.000 CPU（97% CPU，66738 唇）
错误的。

    无赖！其他人做得很好：

    ?- numlist(1,1000,Zs), time(posAt__CapelliC1(Zs,1000,Zs))。
% 671推理，0.000 CPU 在 0.000 秒内（98% CPU，3492100 唇）
Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...]。

?- numlist(1,1000,Zs), time(posAt__mat1(Zs,1000,Zs))。
% 3,996 次推理，0.001 秒内 0.001 CPU（99% CPU，3619841 唇）
Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ;
% 5 次推断，0.000 CPU 在 0.000 秒内（89% CPU，154703 唇）
错误的。

?- numlist(1,1000,Zs), time(posAt__sharky1(Zs,1000,Zs))。
% 1,000 次推理，0.000 CPU 在 0.000 秒内（100% CPU，2627562 唇）
Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ;
% 4 次推理，0.000 CPU 在 0.000 秒内（82% CPU，97109 唇）
错误的。

  • @CapelliC used nth1/3，它可以（并且确实）导致通用终止问题：

    ?-时间((posAt__CapelliC1(_,N,[a,b,c]), false))。
**循环**

    哦！其他人都做得很好：

    ?-时间((posAt__CAFEBABE1(_,_,[a,b,c]), false))。
% 14 次推论，0.000 CPU 在 0.000 秒内（88% CPU，1098470 唇）
假的。

?-时间((posAt__mat1(_,_,[a,b,c]), false))。
% 2,364 次推理，0.001 秒内 0.001 CPU（100% CPU，2764075 唇）
假的。

?-时间((posAt__sharky1(_,_,[a,b,c]), false))。
% 6 次推理，0.000 秒内 0.000 CPU（89% CPU，207247 唇）
假的。

  • @mat 的代码存在复杂性问题。@CAFEBABE 和 @CapelliC 做得“好一点” ——它们的代码更快，因为它们使用依赖于较低级别的原语(is)/2和nth1/3.

    ?- numlist(1,1000,Zs), time((posAt__mat1(Zs,_,_), false))。
% 33,365,972推理，1.643 CPU 在 1.643 秒内（100% CPU，20304661 嘴唇）
错误的。

?- numlist(1,1000,Zs), time((posAt__CAFEBABE1(Zs,_,_), false))。
% 1,001,002次推断，0.083 秒内 0.083 CPU（100% CPU，12006557 唇）
错误的。

?- numlist(1,1000,Zs), time((posAt__CapelliC1(Zs,_,_), false))。
% 171,673推理，0.030 CPU 在 0.030 秒内（100% CPU，5810159 唇）
错误的。

    @sharky 的代码在这方面显然是最好的：

    ?- numlist(1,1000,Zs), time((posAt__sharky1(Zs,_,_), false))。
% 1,003次推理，0.001 秒内 0.001 CPU（100% CPU，1605658 唇）
错误的。

  • @sharky 的代码使用元逻辑内置谓词(==)/2，当与未充分实例化的术语一起使用时，它会失去逻辑可靠性。此查询应该成功：

    ?- posAt__sharky1([a], 1, Xs)。
假的。

    其他代码都给出了合乎逻辑的答案：

    ?- posAt__CAFEBABE1([a], 1, Xs)。
Xs = [a|_G235] ;
错误的。

?- posAt__CapelliC1([a], 1, Xs)。
Xs = [a|_G235]。

?- posAt__mat1([a], 1, Xs)。
Xs = [a|_G235] ;
错误的。

  • 超越第一个答案，@CAFEBABE 的代码变得有点效率低下：

    ?- numlist(1,1000,Zs), time(posAt__CAFEBABE1(Zs,1,Zs))。
% 0 推理，0.000 CPU 在 0.000 秒内（93% CPU，0 Lips）
Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ;
% 999,004 次推理，0.076 秒内 0.076 CPU（100% CPU，13121058 唇）
错误的。

    @sharky 的代码显示了类似的问题——但要小一个数量级：

    ?- numlist(1,1000,Zs), time(posAt__sharky1(Zs,1,Zs))。
% 1 推理，0.000 CPU 在 0.000 秒内（75% CPU，31492 唇）
Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ;
% 1,003次推理，0.001 秒内 0.001 CPU（100% CPU，1078556 唇）
错误的。

    @CapelliC 和 @mat 的代码都很好：

    ?- numlist(1,1000,Zs), time(posAt__CapelliC1(Zs,1,Zs))。
% 7次推断，0.000 CPU 在 0.000 秒内（85% CPU，306802 唇）
Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...]。

?- numlist(1,1000,Zs), time(posAt__mat1(Zs,1,Zs))。
% 0 次推断，0.000 CPU 在 0.000 秒内（80% CPU，0 Lips）
Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ;
% 5次推断，0.000 秒内 0.000 CPU（84% CPU，345662 唇）
错误的。

那么我们该怎么办？为什么不遵循这种方法并结合@mat 和@sharky 的代码呢？

:- 使用模块（库（clpfd））。

posAt__NEW(L0, Pos, L1) :-
    posAt__NEW_(L0, 1, Pos, L1)。

posAt__NEW_([ X |_], Pos, Pos, [ X |_])。
posAt__NEW_([_|X0s], CurrPos, Pos, [_|X1s]) :-
    CurrPos #< Pos, 
    NextPos #= CurrPos + 1,
    posAt__NEW_(X0s, NextPos, Pos, X1s)。

让我们重新运行上面的示例查询posAt__NEW/3：

?- numlist(1,1000,Zs), time(posAt__NEW(Zs,1000,Zs))。
% 4,997 次推理，0.000 CPU 在 0.000 秒内（100% CPU，18141619 唇）
Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ;
% 9 次推理，0.000 CPU 在 0.000 秒内（71% CPU，122877 唇）
错误的。

?-时间((posAt__NEW(_,_,[a,b,c]), false))。
% 440 次推理，0.001 秒内 0.001 CPU（98% CPU，803836 唇）
假的。

?- numlist(1,1000,Zs), time((posAt__NEW(Zs,_,_), false))。
% 154,955 次推理，0.014 秒内 0.014 CPU（100% CPU，11067900 唇）
错误的。

?- posAt__NEW([a], 1, Xs)。
Xs = [a|_G229] ;
错误的。

?- numlist(1,1000,Zs), time(posAt__NEW(Zs,1,Zs))。
% 1 推理，0.000 CPU 在 0.000 秒内（93% CPU，121818 唇）
Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ;
% 7次推断，0.000 秒内 0.000 CPU（86% CPU，266748 唇）
错误的。

好吧！最后，我们确保上面第三个查询中使用的目标具有线性复杂度：

?- numlist(1,100,Zs), time((posAt__NEW(Zs,_,_), false))。
% 15,455 次推断，0.004 秒内 0.004 CPU（100% CPU，3545396 唇）
错误的。

?- numlist(1,1000,Zs), time((posAt__NEW(Zs,_,_), false))。
% 154,955 次推理，0.016 CPU 在 0.017 秒内（98% CPU，9456629 唇）
错误的。

?- numlist(1,10000,Zs), time((posAt__NEW(Zs,_,_), false))。
% 1,549,955推理，0.098 CPU 在 0.099 秒内（99% CPU，15790369 唇）
错误的。

?- numlist(1,100000,Zs), time((posAt__NEW(Zs,_,_), false))。
% 15,499,955 次推理，1.003 个 CPU 在 1.007 秒内（100% CPU，15446075 个嘴唇）
错误的。
于 2016-02-09T10:56:06.113 回答