Вставить в открытый список без привязки его хвостовой переменной - PullRequest
Новая
       30

Вставить в открытый список без привязки его хвостовой переменной

0 голосов
/ 29 ноября 2018

Возможно ли решить следующую проблему в Prolog?

Пусть A и B будут списками чисел, а N будет числом.Известно, что B отсортировано по убыванию.Проверьте, можно ли вставить N в A, чтобы получить результат B, но не связывайте никакие переменные, которые встречаются как хвост, ни в 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]).

Однако, даже если он работает должным образом, когда аргументы полностью созданы, он связывает переменные, расположенные в хвостах:

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

1 Ответ

0 голосов
/ 29 ноября 2018

Уловка для этого упражнения - это металогические предикаты 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.

Когда мы тестируем, мы можем вставить 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.

Но тогда мы должны также следить за тем, чтобы вставленный элемент не был целочисленным, а списки имели целые убывающие целые, за которыми следовал переменный хвост.В качестве альтернативы мы могли бы выбросить лучшее исключение в этих случаях.

...