从列表中删除给定值并存储在累加器中

Question

到目前为止我有：

remove(_,[],R,R).

remove(X,[H|T],[],R) :- X =\= H, remove(X,T,[_|H],R).

但我不太明白为什么它不起作用。第一个是列表已用尽时的基本情况，累加器被复制到 R。

第二个定义head一定不等于X，然后递归到tail，把Head加到累加器

Answer 1

首先，=\=是算术表达式的值不相等。它不是一般的 "unequal" 谓词。例如，这不能很好地工作：

?- a =\= b.
ERROR: =\=/2: Arithmetic: `a/0' is not a function

所以你的谓词没有希望用于任何不是数字列表或其他算术表达式的东西。如果您的 Prolog 系统有 dif/2，请使用：

?- dif(a, b).
true.

仅当上述方法不起作用时，才使用\= 表示不等式：

?- a \= b.
true.

（两者的区别在于dif能正确处理变量，而\=则不能。）

现在，您代码中的一个直接问题是您将列表模式匹配为 [H|T]，然后尝试为递归调用构造一个新列表 [_|H]。这引发了一个危险信号：如果 H 是第一个列表的 head，那么通常它不会是列表本身。但是 non-lists 不应在列表构造函数中显示为 tail。例如，如果我们匹配列表 [1, 2, 3]:

?- [H|T] = [1, 2, 3].
H = 1,
T = [2, 3].

... 然后尝试用这个 H 作为它的尾巴构造一个新列表：

?- [H|T] = [1, 2, 3], Xs = [42 | H].
H = 1,
T = [2, 3],
Xs = [42|1].

...结果不会是列表：

?- [H|T] = [1, 2, 3], Xs = [42 | H], is_list(Xs).
false.

您可能希望将 H 作为新累加器的 head，如下所示：

remove(X, [H|T], R0, R) :-
    dif(X, H),
    remove(X, T, [H|R0], R).

我从你的第二个条款中改变的另一件事是累加器 R0 不需要是 []，如你的定义。在您的定义中，递归调用将立即失败，因为新的 non-empty 累加器不会与 [].

统一

这已经适用于某些情况：

?- remove(a, [b, c, d], [], Result).
Result = [d, c, b] ;
false.

但不适合其他人：

?- remove(a, [a], [], Result).
false.

到目前为止您只有两个子句：一个用于空列表（此处不适用），另一个用于要删除的元素不等于列表头部的情况（不适用）也不要在这里申请！）。如果列表的头部是要删除的元素，则需要第三个子句：

remove(X, [X|T], R0, R) :-
   ... %  fill in here

编辑： 正如评论中所指出的，上面概述的解决方案颠倒了结果列表中的元素列表。这通常用于 accumulator-based 递归列表谓词：later 列表元素变为 earlier 累加器元素。

但是，这里不需要累加器。结果可以直接构建。这是一个实现：

remove(_X, [], []).
remove(X, [Y|Xs], [Y|Ys]) :-
    dif(X, Y),
    remove(X, Xs, Ys).
remove(X, [X|Xs], Ys) :-
    remove(X, Xs, Ys).

这对正面和负面测试用例都有效：

?- remove(a, [b, a, c], Result).
Result = [b, c] ;
false.

?- remove(a, [b, c, d], Result).
Result = [b, c, d] ;
false.

在一般情况下有效：

?- remove(X, Xs, Ys).
Xs = Ys, Ys = [] ;
Xs = Ys, Ys = [_G4794505],
dif(X, _G4794505) ;
Xs = Ys, Ys = [_G4794601, _G4794604],
dif(X, _G4794604),
dif(X, _G4794601) ;
Xs = Ys, Ys = [_G4794697, _G4794700, _G4794703],
dif(X, _G4794703),
dif(X, _G4794700),
dif(X, _G4794697) ;
Xs = Ys, Ys = [_G4794793, _G4794796, _G4794799, _G4794802],
dif(X, _G4794802),
dif(X, _G4794799),
dif(X, _G4794796),
dif(X, _G4794793) ;
Xs = Ys, Ys = [_G4794889, _G4794892, _G4794895, _G4794898, _G4794901],
dif(X, _G4794901),
dif(X, _G4794898),
dif(X, _G4794895),
dif(X, _G4794892),
dif(X, _G4794889) ;
Xs = Ys, Ys = [_G4794985, _G4794988, _G4794991, _G4794994, _G4794997, _G4795000],
dif(X, _G4795000),
dif(X, _G4794997),
dif(X, _G4794994),
dif(X, _G4794991),
dif(X, _G4794988),
dif(X, _G4794985) .

但是上面的列举并不公平！它只执行第二个子句，而不执行第三个子句。我们可以通过 Xs:

的长度分组来获得公平的枚举

?- length(Xs, N), remove(X, Xs, Ys).
Xs = Ys, Ys = [],
N = 0 ;
Xs = Ys, Ys = [_G4794582],
N = 1,
dif(X, _G4794582) ;
Xs = [X],
N = 1,
Ys = [] ;
Xs = Ys, Ys = [_G4794678, _G4794681],
N = 2,
dif(X, _G4794678),
dif(X, _G4794681) ;
Xs = [_G4794585, X],
N = 2,
Ys = [_G4794585],
dif(X, _G4794585) ;
Xs = [X, _G4794588],
N = 2,
Ys = [_G4794588],
dif(X, _G4794588) ;
Xs = [X, X],
N = 2,
Ys = [] ;
Xs = Ys, Ys = [_G4794774, _G4794777, _G4794780],
N = 3,
dif(X, _G4794774),
dif(X, _G4794780),
dif(X, _G4794777) .

我们也可以以有限的方式使用这个 "backwards"：通过保留第二个参数 Xs 并为第三个参数 Ys 指定一个具体列表，我们得到一个谓词将给定的元素插入Ys所有可能的位置，给出Xs:

?- remove(a, Xs, [b, c, d]).
Xs = [b, c, d] ;
Xs = [b, c, d, a] ;
Xs = [b, c, d, a, a] ;
Xs = [b, c, d, a, a, a] .

同样，这不公平，但同样可以解决：

?- length(Xs, N), remove(a, Xs, [b, c, d]).
Xs = [b, c, d],
N = 3 ;
Xs = [b, c, d, a],
N = 4 ;
Xs = [b, c, a, d],
N = 4 ;
Xs = [b, a, c, d],
N = 4 ;
Xs = [a, b, c, d],
N = 4 ;
Xs = [b, c, d, a, a],
N = 5 .  % etc.

从列表中删除给定值并存储在累加器中

Removing given value from list and storing in accumulator

list

debugging

prolog

accumulator