list - 为什么在SWI Prolog中，我得到带有`|`符号的结果？

我有以下代码将等效对象的序列分组在一起:

pack([], []).
pack([X], [X]).

pack([H, T|TS], [H|TR]):-
    H \= T,
    pack([T|TS], TR).

pack([H, H|HS], [[H|TFR]|TR]):-
    pack([H|HS], [TFR|TR]).

我的输入是:

pack([1,1,1,1,2,3,3,1,1,4,5,5,5,5], X).

结果，我得到:

[[1,1,1|1],2,[3|3],[1|1],4,[5,5,5|5]]

您是否注意到每个列表中最后一个元素之前的|符号？我不知道为什么会出现以及如何解决它。有任何想法吗？

最佳答案

列表是一种具有两种函子/常数的数据类型:

没有参数的空列表[]；和

“缺点” [element|list]。

如第二个选项所示，缺点的第二个参数应该是列表。这可以是另一个缺点(因此可以递归进一步)，也可以是一个空列表。但是，Prolog并不是真正的类型，因此您可以使用整数，字符...作为第二项，但是它不是列表。

所以现在的问题是，“我们如何构建这样的怪异列表”。在此答案中，我使用了一个较小的示例来重现该错误，因为它使事情变得更容易:

?- trace.
true.

[trace]  ?- pack([1,1], X).
   Call: (7) pack([1, 1], _G1066) ? creep
   Call: (8) 1\=1 ? creep
   Fail: (8) 1\=1 ? creep
   Redo: (7) pack([1, 1], _G1066) ? creep
   Call: (8) pack([1], [_G1144|_G1141]) ? creep
   Exit: (8) pack([1], [1]) ? creep
   Exit: (7) pack([1, 1], [[1|1]]) ? creep
X = [[1|1]] .

如果我们这样包含两个元素，就会出问题。首先我们称为pack([1,1],X)。

首先，第三个子句被触发，但是H \= T项失败。因此，Prolog重做了调用，但是现在使用了last子句。在最后一个子句中，我们看到了一些奇怪的东西:

pack([H, H|HS], [[H|TFR]|TR]):-
    pack([H|HS], [TFR|TR]).

我们看到的是，我们使用pack/2对[TFR|TR]执行了递归调用。因此，这意味着[TFR|TR]应该是列表的列表。但是第二个子句不会生成列表列表，而只会生成一个项目列表。因此错误在于:

pack([X], [X]).
%%        ^ list of items??

因此，要解决该错误，我们需要将第二个子句重写为:

pack([X], [[X]]).
%%        ^ list of list

现在我们已经解决了这个问题，但是我们还没有解决:第三子句中还存在类型错误:

pack([H, T|TS], [H|TR]):-
    %%           ^ item instead of a list?
    H \= T,
    pack([T|TS], TR).

同样，我们可以简单地使它成为项目列表:

pack([H, T|TS], [[H]|TR]):-
    %%           ^ list
    H \= T,
    pack([T|TS], TR).

现在，我们获得以下代码:

pack([], []).
pack([X], [[X]]).

pack([H, T|TS], [[H]|TR]):-
    H \= T,
    pack([T|TS], TR).

pack([H, H|HS], [[H|TFR]|TR]):-
    pack([H|HS], [TFR|TR]).

然后，我们获得:

?- pack([1,1,1,1,2,3,3,1,1,4,5,5,5,5], X).
X = [[1, 1, 1, 1], [2], [3, 3], [1, 1], [4], [5, 5, 5|...]] [write]
X = [[1, 1, 1, 1], [2], [3, 3], [1, 1], [4], [5, 5, 5, 5]] .

编辑:

如果只有一个元素，您显然不想构造一个列表。这使问题更加棘手。有两种选择:

我们修改代码，以便在发生此类元素时，不将其添加到列表中。或

我们执行一些后期处理，在这里我们用一个元素“取消列出”列表。

最后一个是微不足道的，所以让我们做第一个。在这种情况下，第二个子句确实应为:

pack([X],[X]).

现在第二个子句应显示为:

pack([H, T|TS], [H|TR]):-
    H \= T,
    pack([T|TS], TR).

也一样但是最后一个子句更难:

pack([H, H|HS], [[H|TFR]|TR]):-
    pack([H|HS], [TFR|TR]).

这里有两种可能性:

TFR是项目列表，在这种情况下，我们只需添加到该列表的前面即可；或

TFR不是列表，在这种情况下，我们将构建一个列表。

为了解决这个问题，我们可以定义一个谓词:

prepend_list(H,[HH|T],[H,HH|T]).
prepend_list(H,X,[H,X]) :-
   X \= [_|_].

然后使用:

pack([H, H|HS], [HTFR|TR]):-
    pack([H|HS], [TFR|TR]),
    prepend_list(H,TFR,HTFR).

现在，我们获得:

pack([], []).
pack([X], [X]).

pack([H, T|TS], [H|TR]):-
    H \= T,
    pack([T|TS], TR).

pack([H, H|HS], [HTFR|TR]):-
    pack([H|HS], [TFR|TR]),
    prepend_list(H,TFR,HTFR).

prepend_list(H,[HH|T],[H,HH|T]).
prepend_list(H,X,[H,X]) :-
   X \= [_|_].

但是请注意，如果您要pack/2列出自身，则该程序将失败。在这种情况下，无论如何最好还是使用后处理步骤。

现在构造:

?- pack([1,1,1,1,2,3,3,1,1,4,5,5,5,5], X).
X = [[1, 1, 1, 1], 2, [3, 3], [1, 1], 4, [5, 5, 5|...]] [write]
X = [[1, 1, 1, 1], 2, [3, 3], [1, 1], 4, [5, 5, 5, 5]] .