Пролог

Question

Я читаю книгу Ивана Братко "Программирование для искусственного интеллекта" и у меня нет опыта работы с Прологом. В книге отношение подсписка для списка сформулировано как:

S is a sublist of L if:
1) L can be decomposed into two lists, L1 and L2, and
2) L2 can be decomposed into two lists, S and some L3.

И отношение дается как:

sublist(S, L) :-
    conc(L1, L2, L),
    conc(S, L3, L2).

conc([], L, L).
conc([X|L1], L2, [X|L3]) :-
    conc(L1, L2, L3).

Мне кажется странным, почему мы не просто разбиваем список на два списка и проверяем, совпадает ли один из списков с S?

Answer 1

Для сравнения, определение предиката sublist/2, используемого в библиотеке Logtalk:

sublist(List, List).
sublist(Sublist, [Head| Tail]) :-
    sublist(Tail, Head, Sublist).

sublist(Sublist, _, Sublist).
sublist([Head| Tail], _, Sublist) :-
    sublist(Tail, Head, Sublist).
sublist([Head| Tail], Element, [Element| Sublist]) :-
    sublist(Tail, Head, Sublist).

IIRC, это общее определение. Некоторые примеры вызовов могут быть:

?- list::sublist(Sublist, [1,2,3]).
Sublist = [1, 2, 3] ;
Sublist = [2, 3] ;
Sublist = [3] ;
Sublist = [] ;
Sublist = [2] ;
Sublist = [1, 3] ;
Sublist = [1] ;
Sublist = [1, 2].

?- list::sublist([1,2], List).
List = [1, 2] ;
List = [_1376, 1, 2] ;
List = [_1376, _1382, 1, 2] ;
List = [_1376, _1382, _1388, 1, 2] ;
...

?- list::sublist(Sublist, List).
Sublist = List ;
List = [_1172|Sublist] ;
List = [_1172, _1178|Sublist] ;
List = [_1172, _1178, _1184|Sublist] .
...

Обновление

Заметил, что определение в вопросе и определение в моем ответе не имеют одинаковую семантику.Определение в вопросе подразумевает последовательные элементы.Например,

?- sublist(Sublist, [1,2,3]).
Sublist = [] ;
Sublist = [1] ;
Sublist = [1, 2] ;
Sublist = [1, 2, 3] ;
Sublist = [] ;
Sublist = [2] ;
Sublist = [2, 3] ;
Sublist = [] ;
Sublist = [3] ;
Sublist = [] ;
false.

Одна из проблем в этом определении заключается в том, что решение пустого списка генерируется несколько раз.

Answer 2

Мне кажется, что вы очень близки, когда пишете:

Мне кажется странным, почему мы не просто разбиваем список на два списка и проверяем, совпадает ли один из списков с S?

Просто разложите список L на три списка, и вы там:

• L1 - список, предшествующий подсписку («префикс»),
• S - это сам подсписок, а
• L3 - список, следующий за подсписком («суффикс»).

Поскольку conc/3 может объединять (или разлагать) только два списка, а не три, требуется соединение двух conc/3 целей.

conc(L1,L2,L), conc(S,L3,L2) выражает вышеуказанное отношение.

Answer 3

Это должно помочь;ключевое слово / концепция: difference list.

Из "Prolog Techniques" Attila Csenki , глава 2 (бесплатно PDF со встроенной рекламой)

Немного позже в книге приведено это изображение

---

Вторая часть книги на самом деле представляет собой отдельную книгу,

«Приложения Пролога» Аттилы Ченки (бесплатно PDF со встроенной рекламой)