PROLOG：递归保留列表

Question

所以，我花了很多时间试图解决这个问题，但几乎没有任何进展。希望你能帮助我。目标是采用这样的列表（我们称之为基本列表）：[[[feesc,11],[podshare,11]],[[feesc,11]],[]]. And make it become this: [[feesc,22],[podshare,11]].

我有一个谓词负责对结果列表进行添加或求和。这是代码：

place_key([Key,Value], [], [Key,Value]).
place_key([Key,Value], [[Key,V]|Rest], [[Key,V1]|Rest]) :- V1 is V+Value.
place_key([Key,Value], [[K,V]|Rest], [[K,V]|List2]) :- Key \= K, place_key([Key,Value], Rest, List2)."

如果我手动调用这个方法来模拟递归，它完全符合我的要求。示例：

 place_key([feesc,11], [], R), place_key([feesc,11],R,J). 
So J is = [[feesc,22]].

预期结果正确。问题在于递归。

所以基本上我需要做的是：遍历基本列表，当到达每个 key/par 列表时，调用 place_key 并将其保存在堆栈中，以便递归将其保存到最后一个。只是要指出，我不想追加，我只需要 place_key.

的最新结果

到目前为止我做了什么：

fe([HO|T],NL,R) :- write(HO), place_key(HO,NL,RESULT), fe(T,RESULT,R).
fe(S,R):- fe(S,[],R).
fe([],[]).
feg([HO,T],R) :- fe(HO,RESULT), feg(T,RESULT), R = RESULT.
feg([],[]).

当我运行：

[trace] 57 ?- feg([[[feesc,11]],[[feesc,11]]],R).
   Call: (6) feg([[[feesc, 11]], [[feesc, 11]]], _G21384) ? creep
   Call: (7) fe([[feesc, 11]], _G21484) ? creep
   Call: (8) fe([[feesc, 11]], [], _G21485) ? creep
   Call: (9) place_key([feesc, 11], [], _G21485) ? creep
   Exit: (9) place_key([feesc, 11], [], [[feesc, 11]]) ? creep //Until here, I think this is correct.
   Call: (9) fe([], [[feesc, 11]], _G21494) ? creep 
   Fail: (9) fe([], [[feesc, 11]], _G21494) ? creep
   Redo: (9) place_key([feesc, 11], [], _G21485) ? creep
   Fail: (9) place_key([feesc, 11], [], _G21485) ? creep
   Fail: (8) fe([[feesc, 11]], [], _G21485) ? creep
   Fail: (7) fe([[feesc, 11]], _G21484) ? creep
   Fail: (6) feg([[[feesc, 11]], [[feesc, 11]]], _G21384) ? creep
false.

我做错了什么？

Answer 1

您的问题是您没有为 fe/3 定义基本情况。如您所见，除了您的 place_key 谓词外，您还有以下内容：

fe([HO|T],NL,R) :- write(HO), place_key(HO,NL,RESULT), fe(T,RESULT,R).
fe(S,R):- fe(S,[],R).
fe([],[]).
feg([HO,T],R) :- fe(HO,RESULT), feg(T,RESULT), R = RESULT.
feg([],[]).

我会尽量使它更具可读性，这样您就可以看到发生了什么：

% fe/3 cases
fe([Head|Tail],Current,Result) :- write(Head), place_key(Head,Current,TempResult), fe(Tail,TempResult,Result).
% fe/2 cases
fe(S,R):- fe(S,[],R).
fe([],[]).
%% this case above is never used, as the first case always matches
% recursive and base cases for feg
feg([HO,T],R) :- fe(HO,RESULT), feg(T,RESULT), R = RESULT.
feg([],[]).

你应该改写如下：

fe([],Result,Result).

这是您的基本情况，如果列表为空，则中间结果等于最终结果。 Prolog 总是首先尝试第一个可能的匹配项，因此请始终将您的基本情况放在首位。

fe([Head|Tail],Current,Result) :- write(Head), place_key(Head,Current,TempResult), fe(Tail,TempResult,Result).

这是你的递归案例，就像你之前所做的那样，我们将把它放在我们的基本案例下面。

我们可以删除第二个 fe/2 案例，因为第一个案例总是匹配，我们重写为 fe/3 无论如何，它可以处理所有案例。

fe(S,R):- fe(S,[],R).

以下是您现有的 feg/2 个案例。这里也是一个错误，因为在你的第一个 fe/2-predicate 之后，RESULT-variable 有一个值，但它仍然需要能够与调用 feq(T,RESULT) 统一，这将产生不同的值.我会把它留作练习。

feg([HO,T],R) :- fe(HO,RESULT), feg(T,RESULT), R = RESULT.
feg([],[]).

Answer 2

将您的 key/pairs 保留为元组，一个简单的术语，元数为 2。例如 K-V 或 K:V 甚至tuple(K,V) 优于 [K,V]。原因很简单：

K-V、K:V 和 tuple(K,V) 都映射到简单结构：-(K,V)、:(K,V) 和 tuple(K,V)分别，而...
[K,V] 是更复杂结构的语法糖 .(K,.(V,[])).

此外，您可能会意识到您的 key/value 对很难与嵌套的列表列表区分开来。将 Key/Value 对保留为元组可以清楚地区分这一点。

因此，让我们假设您的 key/value 对表示为 K:V。在我看来，您本质上想要做的是遍历嵌套的列表列表（本质上是一棵树），枚举它包含的 key/value 对并生成 set（唯一）。这是一种方法。

首先，一个识别非空列表的简单谓词：

nonnempty_list( L ) :- nonvar(L) , L = [_|_] .

然后，一个简单的谓词遍历列表的嵌套列表并枚举它找到的每个 key/value 对：

visit( [ K:R | Ls ] , K:R ) . % succeed if the head of the list is a key/value pair.
visit( [ L | Ls ] , KVP ) :-  % otherwise...
  nonempty_list(L) ,          % - if the head is a non-empty list ,
  visit( L , KVP )            % - visit it.
  .                           %
visit( [_|Ls] , KVP ) :-      % finally...
  visit( Ls , KVP )           % - recurse down on the tail.
  .                           %

那你就可以使用setof/3的魔力得到你想要的东西了：

flattened_set( LoL , KVPs ) :-
  setof( KVP , visit(LoL,KVP) , KVPs )
  .

PROLOG：递归保留列表

PROLOG: Keep list in recursion

recursion

list

prolog

key-pair