1

SWI-Prolog には、要素が Key-ValuesList 形式のペアであるリストがあります。たとえば、そのようなリストの 1 つが次のようになります。

[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

@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 に答える
2

要するに、あなたのやり方は間違っています。

Prolog では、関数の代わりに関係を表現したい場合 (1 つではなく複数の結果が可能)、findall/3and をmember/2直接使用しません。むしろ、関係が何であるかを述べてから、使用する結果のリストが必要な場合は、それが完了したら可能性がありますfindall/3。

ここで意味するのは、次の関係を表現したいということです。

のリストを取得し、がリストのメンバーである場所Key-Valuesのリストを返します。Key-[Value]ValueValues

次のように行うことができます。

% 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 に答える