7

我想检查元素是否在列表中间。我搜索中间元素，然后检查是否是列表的成员，但我得到了无限循环。

我的谓词：

remove_first([_,H1|T], [H1|T]).

remove_last([_],[]).
remove_last([H|T], [H|T2]) :- remove_last(T, T2).

remove_first_and_last([X],[X]).
remove_first_and_last(In, Out) :- 
    remove_first(In, Out1),
    remove_last(Out1, Out).

middle([X], [X]).
middle(In, X) :-
    remove_first_and_last(In, Out),
    middle(Out, X).

member(X, [X|_]).
member(X, [_|T]) :- member(X, T).

is_middle(X, In) :-
    middle(In, Out),
    member(X, Out), !.

当我打电话时，我is_middle(1,[2,1,3])就明白了。但是当我打电话时，我is_middle(1,[2,2,3])没有得到结果。口译员不要中断处理。

4

3 回答 3

9

在你这样的情况下，你有两个选择。正如您在另一个答案中看到的那样，您可以穿过一堵墙的痕迹，或者首先尝试减少您必须理解的内容。我更喜欢后者，因为我不喜欢阅读太多。

但你的主要问题是这个。你说：

当我打电话时，我is_middle(1,[2,1,3])就明白了。

是的，Prolog 找到了解决方案，但它不是一次找到，而是无限多次。只需点击SPACE或;看到这个：

?- is_middle(1,[2,1,3]).
true ;
true ;
true ;
true ;
true ;
true ...

因此，您的第一个查询已经存在问题。观察这一点的最佳方法是添加false到此查询中：

?- is_middle(1,[2,1,3]), false。
** 循环 **

现在，让我们尝试减小查询的大小。我们可以将其缩小到：

?- is_middle(1,[1]), false。
** 循环 **

有了这个，我们现在可以查看您的程序。首先，我将删除切口。反正是放错地方了。

为了了解实际发生的情况，我将通过插入您的程序来缩小范围false。有了这些额外的目标，就可以消除很多不必要的细节。而且，如果它仍在循环中，则称为

remove_first_and_last([X],[X])。
remove_first_and_last(In, Out) :- false ,
     remove_first(In, Out1) ,
     remove_last(Out1, Out)。

中间（[X]，[X]）：-假。
中间（在，X）：-
    remove_first_and_last（输入，输出），
    中间（出，X），假。

is_middle(X, In) :-
    中间（进，出），假，
    成员（X，出）。

将此与您的原始程序进行比较！读书少了很多。要解决问题，您必须修复剩余片段中的某些内容。我建议删除这个事实remove_first_and_last([X],[X]).这个事实表明某些东西被删除了，但是对于这种情况，没有任何东西被删除。

对于直接使用的解决方案：

is_middle(E, Es) :-
   phrase(middle(E), Es).

middle(E) --> [E].
middle(E) --> [_], middle(E), [_].

这是尽可能短的，但它有一个小问题：它不能确定地计算答案。您可以通过查看答案来了解这一点：

?- is_middle(1, [2,1,3]).
true ;
false.

这; false表明 Prolog 无法确定地完成计算。换句话说，留下一些空间。您可能很想使用切割。抵抗！

如果您真的很喜欢速度，请选择最快的版本：

is_middle(X, Xs) :-
   Xs = [_|Cs],
   middle_el(Cs, Xs, X).

middle_el([], [X|_], X).
middle_el([_,_|Cs], [_|Xs], X) :-
   middle_el(Cs, Xs, X).

如果您希望@DanielLyons 的解释允许偶数长度列表具有两个中间元素，请查看采用上述语法定义是多么容易。只需添加以下两条规则：

middle(E) --> [E,_].
middle(E) --> [_,E].

或者，将所有四个规则合二为一：

middle(E) --> [E] | [E,_] | [_,E] | [_], middle(E), [_].

对于最快的解决方案，事情有点复杂......

is_middle_dl(X, Xs) :-
   Xs = [_|Cs],
   middle_el_dl(Cs, Xs, X).

middle_el_dl([], [X|_], X).
middle_el_dl([_|Cs], Xs, X) :-
   middle_el_dl2(Cs, Xs, X).

middle_el_dl2([], [A,B|_], X) :-
   ( X = A ; X = B ).
middle_el_dl2([_|Cs], [_|Xs], X) :-
   middle_el_dl(Cs, Xs, X).

为了检查它，我使用 SICStus，因为它为变量提供了更具可读性的名称：

| ?- length(Xs, N), N mod 2 =:= 0, is_middle_dl(X, Xs).
Xs = [X,_A],
N = 2 ? ;
Xs = [_A,X],
N = 2 ? ;
Xs = [_A,X,_B,_C],
N = 4 ? ;
Xs = [_A,_B,X,_C],
N = 4 ? ;
Xs = [_A,_B,X,_C,_D,_E],
N = 6 ? ;
Xs = [_A,_B,_C,X,_D,_E],
N = 6 ? ;
Xs = [_A,_B,_C,X,_D,_E,_F,_G],
N = 8 ? ;
Xs = [_A,_B,_C,_D,X,_E,_F,_G],
N = 8 ? ;
Xs = [_A,_B,_C,_D,X,_E,_F,_G,_H,_I],
N = 10 ? ;
Xs = [_A,_B,_C,_D,_E,X,_F,_G,_H,_I],
N = 10 ? ...
于 2017-06-07T07:00:27.820 回答
6 
is_middle(Item,List) :-
    append(Left,[Item|Right],List),
    length(Left,X),
    length(Right,X).

复杂的解决方案是不好的解决方案，我的朋友。

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

完全可逆的谓词：

?- is_middle(3,L).
L = [3] ;
L = [_G13, 3, _G19] ;
L = [_G13, _G19, 3, _G25, _G28] ;
于 2017-06-07T08:39:00.233 回答
6

调试 Prolog 需要一些不同的技能，所以让我们走很长的路。

首先，让我们注意您的两个示例查询的一些有趣之处。第一个成功了，它应该；第二个应该失败，但它会循环。这个花絮是一个线索：它表明我们正在尝试处理一个虚假案件。这是在其他语言之后使用 Prolog 的人们的常见错误。在 Prolog 中，明确说明成功案例并让失败通过失败的统一发生就足够了。

调试 Prolog 的标准工具是trace/0. 这个想法是，您激活跟踪模式，然后运行您的查询，如下所示：

?- trace,  is_middle(1,[2,2,3]).

问题trace/0在于它可能需要一些努力才能理解它发生了什么。每行都以以下四个动词之一开始：调用、退出、重做或失败。然后有一个数字表示调用的嵌套级别。call 和 redo 动词告诉你你正在进入一个计算；exit 和 fail 告诉您计算正在停止并且嵌套级别即将降低。调用/退出是正常情况，失败/重做是 Prolog 的特殊之处，即非确定性。一般来说，无限循环看起来像是有意义工作（或可能不是）的前缀，后跟来自trace. 我们在这里看到了这一点。字首：

Call: (8) is_middle(1, [2, 2, 3]) ? creep
Call: (9) middle([2, 2, 3], _G1194) ? creep
Call: (10) remove_first_and_last([2, 2, 3], _G1194) ? creep
Call: (11) remove_first([2, 2, 3], _G1194) ? creep
Exit: (11) remove_first([2, 2, 3], [2, 3]) ? creep
Call: (11) remove_last([2, 3], _G1197) ? creep
Call: (12) remove_last([3], _G1190) ? creep
Exit: (12) remove_last([3], []) ? creep
Exit: (11) remove_last([2, 3], [2]) ? creep
Exit: (10) remove_first_and_last([2, 2, 3], [2]) ? creep

重复块：

Call: (10) middle([2], _G1200) ? creep
Exit: (10) middle([2], [2]) ? creep
Exit: (9) middle([2, 2, 3], [2]) ? creep
Call: (9) member(1, [2]) ? creep
Call: (10) member(1, []) ? creep
Fail: (10) member(1, []) ? creep
Fail: (9) member(1, [2]) ? creep
Redo: (10) middle([2], _G1200) ? creep
Call: (11) remove_first_and_last([2], _G1200) ? creep
Exit: (11) remove_first_and_last([2], [2]) ? creep

现在您可以看到仅使用以下查询触发不良行为会容易得多：

[trace]  ?- is_middle(2,[3]).
   Call: (7) is_middle(2, [3]) ? creep
   Call: (8) middle([3], _G398) ? creep
   Exit: (8) middle([3], [3]) ? creep
   Call: (8) member(2, [3]) ? creep
   Call: (9) member(2, []) ? creep
   Fail: (9) member(2, []) ? creep
   Fail: (8) member(2, [3]) ? creep
   Redo: (8) middle([3], _G398) ? creep
   Call: (9) remove_first_and_last([3], _G398) ? creep
   Exit: (9) remove_first_and_last([3], [3]) ? creep
   Call: (9) middle([3], _G401) ? creep
   Exit: (9) middle([3], [3]) ? creep
   Exit: (8) middle([3], [3]) ? creep
   Call: (8) member(2, [3]) ? creep
   Call: (9) member(2, []) ? creep
   Fail: (9) member(2, []) ? creep
   Fail: (8) member(2, [3]) ? creep
   Redo: (9) middle([3], _G401) ? creep

现在应该清楚问题与 和 的相互作用middle/2有关。你的定义正是标准定义，所以它可能不是罪魁祸首。现在，有趣的是，您同时调用了自身和. 并且两者都有一个相同的子句：.remove_first_and_last/2member/2member/2middle/2remove_first_and_last/2middle/2remove_first_and_last/2m([X], [X])

这种事情是无限递归的伟大生成器，因为middle/2在它的第二个子句中所做的第一件事正是它刚刚尝试做的事情，但它自己的第一个子句失败了。因此，它可以发现自己进入第二个子句中的递归调用，其状态与之前对自身的失败调用完全相同。

解决方案是查看remove_first_and_last/2并意识到您的第一个子句实际上并没有删除第一个和最后一个元素。删除remove_first_and_last([X], [X])子句修复代码：

[trace]  ?- is_middle(2,[3]).
   Call: (7) is_middle(2, [3]) ? creep
   Call: (8) middle([3], _G398) ? creep
   Exit: (8) middle([3], [3]) ? creep
   Call: (8) member(2, [3]) ? creep
   Call: (9) member(2, []) ? creep
   Fail: (9) member(2, []) ? creep
   Fail: (8) member(2, [3]) ? creep
   Redo: (8) middle([3], _G398) ? creep
   Call: (9) remove_first_and_last([3], _G398) ? creep
   Call: (10) remove_first([3], _G398) ? creep
   Fail: (10) remove_first([3], _G398) ? creep
   Fail: (9) remove_first_and_last([3], _G398) ? creep
   Fail: (8) middle([3], _G398) ? creep
   Fail: (7) is_middle(2, [3]) ? creep
false.

您的两个测试现在也可以工作：

?- is_middle(1,[2,1,3]).
true.

?- is_middle(1,[2,2,3]).
false.

我认为你在这里添加了基本案例是出于一种责任感。但现实情况是，如果你有一个元素的列表，它remove_first_and_last/2在任何情况下都应该无法统一。这与使用 Prolog 显式处理错误情况非常相似，后者往往会干扰机器的工作。

现在，缺少的一件事是，您想如何处理偶数长度的列表？无论有没有我的改变，你现在所拥有的都不会。偶数列表没有中间元素；那是你的意图吗？我怀疑不是，因为 in 的member/2出现is_middle/2。

评论is_middle/2

你在这里所拥有的可以像这样重组：

is_middle(X, In) :- middle(In, [X]).

的使用member/2不会给你带来任何好处，因为middle/2它的第二个参数永远不会产生非单例列表。但是，如果确实如此，因为您有偶数长度的列表，它将是有利可图的。您甚至可以通过将第三个子句添加到以下内容来使此代码以这种方式工作middle/2：

middle([X,Y], [X,Y]).

现在查看middle/2偶数长度列表上的作品，如下所示：

?- middle([2,1,3,4], X).
X = [1, 3] ;
false.

现在削减让你陷入困境。例如， 1 和 3 都是is_middle/2：

?- is_middle(1, [2,1,3,4]).
true.

?- is_middle(3, [2,1,3,4]).
true.

不幸的是，如果您要求中间元素，您只需1：

?- is_middle(X, [2,1,3,4]).
X = 1.

怎么了3？你阻止它通过你的剪辑生成。我不知道为什么剪在这里。我认为您必须尝试控制无限递归，但它对您没有帮助，所以摆脱它。

通过随机添加剪切进行调试通常不是一个好主意。更好的方法是使用 Ulrich Neumerkel 的故障切片方法（请参阅本文或搜索标签以获取更多信息）。

DCG奖金

您可以改写remove_first_and_last/2为 DCG 规则：

remove_first_and_last --> remove_first, remove_last.

很酷吧？:) 那是因为您在该规则中所做的输入/输出线程正是 DCG 规则转换为的类型。

变更摘要

remove_first_and_last(In, Out) :- 
    remove_first(In, Out1),
    remove_last(Out1, Out).

middle([X], [X]).
middle([X,Y], [X,Y]).
middle(In, X) :-
    remove_first_and_last(In, Out),
    middle(Out, X).
于 2017-06-07T04:46:00.863 回答