2

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

让AandB成为数字列表，让N成为一个数字。已知B是递减排序的。检查是否N可以插入A，以便结果为B，但不要绑定任何作为尾部出现的变量Anor 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]).

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

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

1 回答 1

2

这个练习的诀窍是元逻辑谓词var/1，nonvar/1如果参数是一个变量，它们是真的（也看看ground/1,atom/1和integer/1）。做出区别有点笨拙，因为我们需要将列表保留L1在头部并在我们知道它是否是变量之后进行统一。

还可能让您感到困惑的是算术比较的错误消息。为此，两个论点都必须有依据。当您不测试尾部的非 var 时，统一会自动将尾部实例化为[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（在第一个结果之后，还有路径可以测试但是都失败了，导致falseafter继续查询）：

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

但是我们也应该防止插入的元素是非整数，并且列表具有递减整数后跟可变尾部。或者，我们可以在这些情况下抛出更好的异常。

于 2018-11-29T14:07:23.660 回答