list - 插入开放式列表而不绑定(bind)其尾部变量

Question

是否可以在 Prolog 中解决以下问题？

令A 和B 为数字列表，令N 为数字。众所周知，B 是按降序排列的。检查是否可以将 N 插入到 A 中，以便结果为 B，但不要绑定(bind)任何作为尾部出现的变量 A 或 B。

例如

?- insertable(34, [78, 72, 11 | Z], [78, 72, 34, 11 | Z]).
true. 

?- insertable(34, [78, 72, 11 | Z], L).
L = [78, 72, 34, 11 | Z].

谁能帮帮我？ :)

编辑 1:这是我想出的。

insertable(X, List1, List2):- select(X, List2, List1), sorted(List2).

sorted([]).
sorted([_]).
sorted([X, Y | Rest]) :-
  X > Y,
  sorted([Y | Rest]).

然而，即使它在参数被完全实例化时按预期工作，它也会绑定(bind)位于尾部的变量:

?- insertable(11, [5, 3, 2], [11, 5, 3, 2]).
true .

?- insertable(11, [5, 3, 2 | X], [11, 5, 3, 2 | X] ).
X = [] .

?- insertable(11, [5, 3, 2 | X], L ).
X = [],
L = [11, 5, 3, 2] .

编辑 2:这是我尝试过的另一种方法。

in(X, [], [X]).
in(X, [Head | Tail1], [Head | Tail2]) :-
  X =< Head,
  in(X, Tail1, Tail2).
in(X, [Head | Tail], [X, Head | Tail]) :-
  X > Head.

问题依旧:

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

?- in(1, [3, 2], L).
L = [3, 2, 1] ;
false.

?- in(1, [3, 2 | X], L).
X = [],
L = [3, 2, 1] ;
ERROR: =</2: Arguments are not sufficiently instantiated
   Exception: (9) in(1, _G8394089, _G8394190) ? abort
% Execution Aborted
?- in(1, [3, 2 | X], [3, 2, 1 | X]).
X = [] ;
X = [1] ;
X = [1, 1] ;
X = [1, 1, 1] ;
X = [1, 1, 1, 1] ;
X = [1, 1, 1, 1, 1] ;
X = [1, 1, 1, 1, 1, 1] ;
X = [1, 1, 1, 1, 1, 1, 1] .

Answer 1

这个练习的技巧是元逻辑谓词 var/1和 nonvar/1如果参数是否为变量，则为真(另请参阅 ground/1 、 atom/1 和 integer/1 )。区别有点笨拙，因为我们需要保留列表 L1在我们知道它是否是变量之后，在头部并统一。

同样让你困惑的是算术比较的错误信息。为了使它起作用，这两个论点都必须有根据。当您不测试尾部的非变量时，统一会自动使用 [Head|Tail1] 实例化尾部。 .这总是导致比较 number <= Head这会导致您遇到错误。

以下代码假定您还想插入尾部闭合的列表。如果不是，则需要删除第一条规则。

in(X, L1, [X]) :- % terminal case for empty list (i.e. tail is not a variable)
    nonvar(L1),
    L1 = [].
in(X, Xs, [X | Xs]) :- % terminal case if the tail is a variable
    var(Xs).
in(X, L1, [N | Zs]) :- % recursive case X =< N
    nonvar(L1),
    L1 = [N | Ys],
    X =< N,
    in(X, Ys, Zs).
in(X, L1, [X,  N | Ys]) :- % recursive case X > N
    nonvar(L1),
    L1 = [N | Ys],
    X > N.

我们测试的时候可以在一个变量tail前面加1(在第一个结果之后，还有路径要测试，但是都失败了，继续查询后导致false):

?- in(1,Xs,Ys).
Ys = [1|Xs] ;
false.

另外，插入的元素必须是1，所以这个应该会失败:

?- in(1,Xs,[2|Ys]).
false.

似乎递归正确地传播到最后:

?- in(1,[3, 2 | Xs], Zs).
Zs = [3, 2, 1|Xs] ;
false.

中间插入也可以:

?- in(2,[3,1 |Xs],Zs).
Zs = [3, 2, 1|Xs].

最后是您之前尝试解决的测试用例:

?- in(34, [78, 72, 11 | Z], [78, 72, 34, 11 | Z]).
true ;
false.

如果您的列表中出现变量，仍然不起作用:

?- in(2,[3,A,1|Xs],Zs).
ERROR: Arguments are not sufficiently instantiated
ERROR: In:
ERROR:   [10] 2=<_8374
ERROR:    [9] in(2,[_8406,1|_8414],[_8418|_8420]) at ./prolog/so-3.pl:9
ERROR:    [8] in(2,[3,_8458|...],[3,_8470|_8472]) at ./prolog/so-3.pl:10
ERROR:    [7] <user>
   Exception: (9) in(2, [_7488, 1|_7496], _7820) ? a

一个简单的方法是保护与 integer(N) 的比较得到

?- in(2,[3,A,1|Xs],Zs).
false.

但是我们还应该防止插入的元素是非整数，并且列表中的整数降序后跟一个变量尾部。或者，我们可以在这些情况下抛出更好的异常。