插入开放式列表而不绑定其尾部变量

Question

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

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

例如

?- 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]).

但是，即使它在参数完全实例化时按预期工作，它也会绑定位于尾部的变量：

?- 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.

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

插入开放式列表而不绑定其尾部变量

Insert into open-ended list without binding its tail variable

list

prolog

instantiation-error