3

我正在阅读 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 匹配，这对我来说似乎很奇怪？

4

3 回答 3

7

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

为什么我们不只是将列表分解为两个列表并检查其中一个列表是否与 S 匹配，这对我来说似乎很奇怪？

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

  • L1是子列表之前的列表（“前缀”），
  • S是子列表本身，并且
  • L3是子列表（“后缀”）之后的列表。

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

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

于 2019-01-25T20:24:58.503 回答
5

这应该会有所帮助；关键词/概念是difference list。

在此处输入图像描述

来自Attila Csenki的“Prolog Techniques” ，第 2 章（带有嵌入广告的免费PDF ）

书中稍晚一点的是这张图片

在此处输入图像描述

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

Attila Csenki的“Prolog 应用” （带有嵌入广告的免费PDF ）

于 2019-01-25T17:48:39.663 回答
2

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

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.

此定义中的一个问题是多次生成空列表解决方案。

于 2019-01-25T19:32:55.337 回答