Prolog - Поиск смежных элементов в списке

Я пытаюсь определить предикат adjacent(X, Y, Zs), который является истинным, если X и Y смежны в списке. Мой код в настоящее время:

adjacent(_, _, []).
adjacent(X, Y, [X, Y|Tail]) :-
  adjacent(X,Y, Tail).

Он работает для основного случая adjacent(c, d, [a, b, c, d, e]), но из-за базового случая каждый другой случай также возвращает true, и я застрял на этом.

Другая проблема заключается в том, что если X не равно первой части списка, то она пропускает мимо X и Y и переходит к следующему "X"; например, если c не равно a, то он пропускает как a, так и b и проверяет, c равно c. Это проблематично, если, например, список

[a, c, d, e]

потому что он никогда не проверяет c (я считаю).

Я довольно потерял, как примирить эти два вопроса и повернуть свое логическое понимание того, что должно произойти в коде.

РЕДАКТИРОВАТЬ: Благодаря ответу Христиана Худжера моя ошибка базового случая была исправлена, так что теперь я просто застрял во второй проблеме.

Ответы

Ответ 1

В исходной попытке решения:

adjacent(_, _, []).
adjacent(X, Y, [X, Y|Tail]) :-
    adjacent(X,Y, Tail).

Как указывает @ChristianHujer, первое предложение не должно быть там, потому что это неверно. В пустом списке не должно быть смежных элементов.

Второе предложение также проблематично. Он показывает, что X и Y смежны в списке, но затем повторяются и не просто преуспевают. Правильное предложение должно быть:

adjacent(X, Y, [X,Y|_]).

Что говорит, что X и Y являются смежными в списке, если они являются первыми двумя элементами в списке, независимо от того, что такое хвост. Это также создает правильный базовый случай. Тогда ваша общая, рекурсивная статья должна позаботиться о остальных случаях:

adjacent(X, Y, [_|Tail]) :-
    adjacent(X, Y, Tail).

Это говорит о том, что X и Y смежны в [_|Tail], если они смежны в Tail. Это позаботится о второй проблеме, с которой вы столкнулись.

Таким образом, все решение будет:

adjacent(X, Y, [X,Y|_]).
adjacent(X, Y, [_|Tail]) :-
    adjacent(X, Y, Tail).

Это будет выполняться столько раз, сколько X и Y отображаются вместе, в указанном порядке, в списке.

Это также естественно разрешимо с помощью DCG (хотя решение @repeat append/3 является более кратким):

adjacent(X, Y) --> ..., [X, Y], ... .
... --> [] | [_], ... .

adjacent(X, Y, L) :- phrase(adjacent(X, Y), L).

| ?- adjacent(b, c, [a,b,c,d]).

true ? a

(1 ms) no
| ?-

Ответ 2

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

Ответ 3

В этом ответе мы стараемся сохранить его простым: построив append/3:

<Предварительно > смежные (E0, E1, Es): - append (_, [E0, E1 | _], Es).

Пример запроса:

?- adjacent(X, Y, [a,b,c,d,e]).
X = a, Y = b ;
X = b, Y = c ;
X = c, Y = d ;
X = d, Y = e ;
false.

Ответ 4

Вспомогательный предикат adjacent_/5 всегда "отстает" ровно двумя (элементами списка):

<Предварительно > смежные (X0, X1, [E0, E1 | Es]): - adj_ (Es, E0, E1, X0, X1). смежные _ ([], E0, E1, E0, E1). смежный _ ([E2 | Es], E0, E1, X0, X1): - if_ (E0 + E1 = X0 + X1, правда, смежные_ (Es, E1, E2, X0, X1)).

Используя SWI-Prolog, мы запускаем:

<Предварительно > ? - set_prolog_flag (double_quotes, chars). правда. ? - соседний (a, b, "abab" ). правда. ? - смежные (b, c, "abcd" ). правда. ? - смежные (X, Y, "abcd" ). X = a, Y = b ; X = b, Y = c ; X = c, Y = d.

Изменить

Исправленное определение adjacent_/5 дает правильные ответы на следующие запросы:

?- adjacent(X, X, [A,B,C]).
   X = A, A = B
;  X = B, B = C, dif(f(C,C),f(A,A)).

?- adjacent(a, X, "aab").
   X = a
;  X = b.

?- adjacent(a, b, "aab").
true.

Ответ 5

Вот определение, которое, по моему мнению, в долгосрочной перспективе предпочтительнее для решения @repeat:

adjacent(X0, X1, [E0,E1|Es]) :-
   adjacent_(Es, E0, E1, X0, X1).

adjacent_([],      E0, E1, E0, E1).
adjacent_([E2|Es], E0, E1, X0, X1) :-
   if_(( E0 = X0, E1 = X1 ),
       true,
       adjacent_(Es, E1, E2, X0, X1)).

Используя reified и:

','(A_1, B_1, T) :-
   if_(A_1, call(B_1, T), T = false).

;(A_1, B_1, T) :-
   if_(A_1, T = true, call(B_1, T)).