1

在 SWI-Prolog 中，我有一个列表，其元素是 Key-ValuesList 形式的对。例如，一个这样的列表可能如下所示：

[1-[a,b],2-[],3-[c]]

我想将此列表转换为 Key-[Value] 形式的嵌套对列表，其中 Value 是 ValuesList 中的一个元素。上面的示例将转换为：

[[1-[a],2-[],3-[c]], [1-[b],2-[],3-[c]]]

我目前的解决方案如下：

% all_pairs_lists(+InputList, -OutputLists).
all_pairs_lists([], [[]]).
all_pairs_lists([Key-[]|Values], CP) :-
  !,
  findall([Key-[]|R], (all_pairs_lists(Values,RCP), member(R,RCP)), CP).
all_pairs_lists([Key-Value|Values], CP) :-
  findall([Key-[V]|R], (all_pairs_lists(Values,RCP), member(V,Value), member(R,RCP)), CP).

使用这个谓词，调用形式

all_pairs_lists([1-[a,b],2-[],3-[c]],OutputLists).

将变量 OutputLists 绑定到上面提到的所需结果。虽然看起来是正确的，但当 InputList 有很长的列表作为值时，此实现会导致“全局堆栈外”错误。

有没有更少的堆栈消耗方法来做到这一点？对于这种类型的数据结构，这似乎是一种非常常见的操作。

4

2 回答 2

2

好吧，总结一下，你做错了。

在 Prolog 中，当我们想表达关系而不是函数时（可能有几个结果而不是一个），我们不直接使用findall/3and member/2。我们宁愿陈述关系是什么，然后如果我们需要一个我们使用的结果列表，也许一旦它完成findall/3。

这里的意思是我们要表达以下关系：

获取列表Key-Values并返回列表成员Key-[Value]在哪里Value的Values列表。

我们可以这样做：

% The base case: handle the empty list
a_pair_list([], []).

% The case where the Values list is empty, then the resulting [Value] is []
a_pair_list([Key-[]|List], [Key-[]|Result]) :-
    a_pair_list(List, Result).
% The case where the Values list is not empty, then Value is a member of Values.
a_pair_list([Key-[Not|Empty]|List], [Key-[Value]|Result]) :-
    member(Value, [Not|Empty]),
    a_pair_list(List, Result).

一旦表达了这种关系，我们就可以获得我们想要的所有信息：

?- a_pair_list([1-[a, b], 2-[], 3-[c]], Result).
Result = [1-[a], 2-[], 3-[c]] ;
Result = [1-[b], 2-[], 3-[c]] ;
false.

所需的列表现在只是一个相当直接的findall/3调用：

all_pairs_lists(Input, Output) :-
    findall(Result, a_pair_list(Input, Result), Output).

要记住的重要一点是，最好远离额外的逻辑内容：!/0，findall/3，等等......因为它通常会导致不太通用的程序和/或不太正确的程序。既然我们可以用一种纯粹而干净的方式来表达上述关系，我们就应该这样做。通过这种方式，我们可以将烦人的使用限制findall/3在严格的最低限度。

于 2012-08-07T10:38:54.640 回答
2

正如@Mog 已经清楚地解释了问题可能是什么，这里有一个版本（ab）使用基本的“功能”内置列表处理：

all_pairs_lists(I, O) :-
    findall(U, maplist(pairs_lists, I, U), O).

pairs_lists(K-[], K-[]) :- !.
pairs_lists(K-L, K-[R]) :- member(R, L).

测试：

?- all_pairs_lists([1-[a,b],2-[],3-[c]],OutputLists).
OutputLists = [[1-[a], 2-[], 3-[c]], [1-[b], 2-[], 3-[c]]].
于 2012-08-07T11:03:08.840 回答