列表元素的序言交集

Question

我有一个包含 8 个元素的列表：

[[a], [a], [a, b], [b, c], [c, d, e], [d, f], [f], [f]]

目标是得到一个包含相邻元素交集的列表：

[[a], [a], [b], [c], [d], [f], [f]]

在 Prolog 中最好的方法是什么？

Answer 1

回想一下，Prolog 允许您在列表上使用模式匹配：[X|XS] 匹配一个非空列表，第一个元素 X 和 XS 是剩余列表。您可以将其扩展为 [X,Y|ZS]，它匹配至少包含两个元素 X 和 Y 的列表，而 ZS 是剩余的列表。

标准库提供 intersection/3 来获取两个列表的交集。

merge_adj([],[]).
merge_adj([_],[]) :- !.
merge_adj([X,Y|ZS], [M|MS]) :- intersection(X,Y,M), merge_adj([Y|ZS], MS).

?- merge_adj([[a], [a], [a, b], [b, c], [c, d, e], [d, f], [f], [f]], Z).
Z = [[a], [a], [b], [c], [d], [f], [f]].

第二条规则中的 ! 并不是严格需要的，但是它可以防止 Prolog 尝试（并且失败）在第二条规则之后对仅包含一个元素的列表应用第三条规则。这样，求出唯一解后就不再再求解了。

Prolog intersection of list elements