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

Question

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

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]]

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

Answer 1

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

• 没有参数的空列表[]；和
• “缺点”[element|list]。

如第二个选项所示，cons 的第二个参数应该是一个列表。这可能是另一个缺点(因此进一步递归)，或者是一个空列表。尽管如此，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|<b>TFR</b>]|TR]):-
    pack([H|HS], [<b>TFR</b>|TR]).

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

pack([X], <b>[X]</b>).
%%        ^ list of items??

所以我们需要做的是解决错误，将第二个子句重写为:

pack([X], <b>[[X]]</b>).
%%        ^ list of list

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

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

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

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

现在我们得到如下代码:

pack([], []).
pack([X], <b>[</b>[X]<b>]</b>).

pack([H, T|TS], [<b>[</b>H<b>]</b>|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]] .