Prolog子列表关系

Question

我正在阅读 Ivan Bratko 的 Prolog Programming for Artificial Intelligence 一书，但我之前没有使用 Prolog 的经验。在书中，列表的子列表关系被表述为：

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

这应该有帮助；关键 word/concept 是 difference list.

来自 "Prolog Techniques"，作者 Attila Csenki, Chapter 2 (Free PDF，带有嵌入式广告）

书后一点就是这张图

本书的第二部分实际上是一本单独的书，

"Applications of Prolog" Attila Csenki (Free PDF 嵌入广告）

Answer 2

为了比较，Logtalk库中使用的sublist/2谓词的定义是：

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，这是一个常见的 definition.Some 示例调用可能是：

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

我觉得你写的时候很亲近：

It seems odd to me why we don't just decompose list into two lists and check whether one of the lists matches with S?

只需将列表 L 分解为三个个列表即可：

L1是子列表("prefix")之前的列表，
S 是子列表本身，
L3 是子列表 ("suffix") 之后的列表。

由于 conc/3 只能连接（或分解）两个列表，而不是三个列表，因此需要两个 conc/3 目标的结合。

conc(L1,L2,L), conc(S,L3,L2)表示以上关系

Prolog子列表关系

Prolog sublist Relation

list

prolog

sublist

difference-lists