3

嘿，我正在尝试创建一个谓词，用于在 PROLOG 中的嵌套列表上生成深度反向。

目前我得到了这个谓词

reverse(L,A) :- rev(L,[], A).
rev([],A,A).
rev([H|L],R,A) :- rev(L,[H|R],A).

结果如下所示：

reverse([1,2,3],A).
A = [3, 2, 1].

reverse([[0,1],2,3],A).
A = [3, 2, [0, 1]].

问题是，内部列表没有反转。它应该如下所示：

reverse([[0,1],2,3],A).
A = [3, 2, [1, 0]].

reverse([1,2,[3,4,5,[6,7],8],[9,10],11,12],A).
A = [12,11,[10,9],[8,[7,6],5,4,3],2,1].

谢谢你的帮助。

4

3 回答 3

4

表示数据的方式称为defaulty，因为在推理时需要默认情况：

  • 是清单吗？→ 东西成立
  • 否则→ 其他东西成立。

这种表示是麻烦的丰富来源。例如my_reverse/2，从另一个答案中考虑。它的主要问题是它过早且错误地 提交了其中一种情况，尽管这两种情况仍然可能：

?- my_reverse([X], Ls)。
Ls = [X]。

但是这个答案只适用于X不是列表的情况！此问题导致谓词出现以下奇怪行为：

?- my_reverse([X], Ls), X = [1,2,3]。
Ls = [[1, 2, 3]],
X = [1, 2, 3]。

这意味着即使X是一个列表，它的元素也不会反转！

您应该始终以更清晰的表示为目标，以区分可能出现的情况。

例如，您对以下表示数据的方式有何看法：

  • list(Ls)表示列表 Ls
  • n(N)代表数字 N。

有了这样的表示，我们就可以象征性地区分这些情况。我将此作为更具声明性的解决方案的起点。

于 2016-07-28T09:17:07.623 回答
1

为了让事情尽可能简单，我们可以添加一个测试，如果当前被检查的元素是一个列表或不是一个列表。如果它确实是一个列表，那么它的元素也应该颠倒过来。所以在代码中：

my_reverse(L,R) :- rev(L,[],R).

rev([],A,A).
rev([H|T],A,R) :-
    ( is_list(H) ->        % If H is a list
      rev(H,[],X),         %   then reverse H as well
      rev(T,[X|A],R)
    ;
      rev(T,[H|A],R)
    ).

另外，这并不重要，只是为了避免混淆，请注意我是如何分别使用A和和的。在您的代码中，它们当前被交换，这 - 对我个人而言 - 可能有点令人困惑，尤其是当谓词变得更长和更复杂时。RAccumulatorResult

无论如何，让我们看看您提供的查询：

?- my_reverse([[0,1],2,3],R).
R = [3, 2, [1, 0]].

?- my_reverse([1,2,[3,4,5,[6,7],8],[9,10],11,12],R).
R = [12, 11, [10, 9], [8, [7, 6], 5, 4, 3], 2, 1].

以及一些一般性查询：

?- my_reverse(L,R).
L = R, R = [] ;
L = R, R = [_G2437] ;
L = [_G2437, _G2443],
R = [_G2443, _G2437] ;
L = [_G2437, _G2443, _G2449],
R = [_G2449, _G2443, _G2437] ;
L = [_G2437, _G2443, _G2449, _G2455],
R = [_G2455, _G2449, _G2443, _G2437] 
...

?- my_reverse([[X,Y]|T],R), member(a,T), length(X,2).
X = [_G2588, _G2591],
T = [a],
R = [a, [Y, [_G2588, _G2591]]]
;
X = [_G2594, _G2597],
T = [a, _G2588],
R = [_G2588, a, [Y, [_G2594, _G2597]]]
;
X = [_G2594, _G2597],
T = [_G2582, a],
R = [a, _G2582, [Y, [_G2594, _G2597]]]
...

但是请注意，使用此谓词，在找到查询的第一个答案后不会发生终止：

?- my_reverse(X,[X]).
X = [X] ;
...

但由于这不是 OP 问题中的要求/要求，我认为这没问题。

编辑：

请阅读@mat 的答案作为此问题的后续行动。

于 2016-07-28T07:10:59.990 回答
0

您的问题的另一个解决方案是使用 cut 和内置谓词“is_list/1”来检查您是否在当前调用中处理简单术语或列表。这是代码：

deepReverse(List,R):-deepReverseTail(List,[],R).

deepReverseTail([],Acc,Acc).

deepReverseTail([H|T],Acc,R):-             % when H is a list
     is_list(H),                           % check if it's a list.
     !,                                    % cut the process if not. 
     deepReverseTail(H,[],Hrev),           % reverse this current list
     deepReverseTail(T,[Hrev|Acc],R).      % continue the general recursion

deepReverseTail([H|T],Acc,R):- deepReverseTail(T,[H|Acc],R). % when H is a simple term

第三行中的“cut”确保您在此定义中仅处理列表，而处理简单术语将在下一个定义中。

输出示例：

7 ?- deepReverse([a,[d,f],[],[[k],g]],R)
R = [[g, [k]], [], [f, d], a].
于 2018-05-08T11:57:41.247 回答