只使用两个参数，能否将一个列表反转？

Question

在Prolog中，只使用两个参数是否可能将列表反转？例如：

reverse_list(List, Reversed).

这不是作业，我在阅读《七周七语言》一书时感到好奇。使用三个参数，你可以使用累加器（类似于函数式编程）：

reverseList([], Accumulator, Accumulator).
reverseList([Head|Tail], Accumulator, Solution) :-
  reverseList(Tail, [Head|Accumulator], Solution).
reverseList(List, Solution) :-
  reverseList(List, [], Solution).

澄清：我看到有一个使用append的解决方案，我想知道能否在不使用其他Prolog函数的情况下实现。

- CamelCamelCamel

---

请不要在标题中放置伪标签，这就是标签的作用。 - user229044

Answer 1

当然：

reverseList([[], Accumulator, Accumulator]).
reverseList([[Head|Tail], Accumulator, Solution]) :-
  reverseList([Tail, [Head|Accumulator], Solution]).
reverseList([List, Solution]) :-
  reverseList([List, [], Solution]).

编辑：实际上只有一个 :b

一种非作弊的方法：

reverse([],[]).
reverse([H|T],L):-
    reverse(T,R),
    append(R,[H],L).

问题在于性能会非常差：您将递归遍历列表，并针对每个元素执行一次append/3操作。 使用time/1和一个包含1,000,000个元素的随机列表：

accumulator:    % 2,000,003 inferences, 0.652 CPU in 0.652 seconds (100% CPU, 3066292 Lips)
arity-2         % 1,000,003 inferences, 0.178 CPU in 0.178 seconds (100% CPU, 5602426 Lips)

- Thanos Tintinidis

Answer 2

您可以编写一个带有两个参数的 rev_list 函数：

rev_list([], []).
rev_list([Head|Tail], Reversed) :- rev_list(Tail, TailReversed), 
                                       append(TailReversed, [Head], Reversed).

也许如果这个函数在函数式编程中，你会更加熟悉它：

rev x::xs = rev xs @ [x]

然而，您应该注意到，3个参数的版本是首选，因为它是尾递归的。

- pad

---

我看到了一个使用append的解决方案，不知道你是否可以不使用其他Prolog函数来实现。 - CamelCamelCamel

Answer 3

我知道我来晚了，但是有一种方法可以在不“作弊”或使用append的情况下完成这个任务：

rev([], []).
rev([Head], [Head]).
rev([Head|Tail], [RHead|RTail]) :-
  rev(Tail, [RHead|RMid]),
  rev(RMid, Mid),
  rev([Head|Mid], RTail).

虽然它的时间复杂度为 O(3^n)，效率不是很高，但这种方法十分优雅，甚至在定理证明中也有用处。

- Matt

---

@repeat 因为它不使用任何外部函数，所以非常容易看出它的作用。我上过一门使用 ACL2 的课程，记得我们让 ACL2 证明这个版本与追加版本和尾递归版本等效。然后我们可以在程序中使用高效的尾递归版本，但在证明程序正确性时，ACL2会将其替换为这个版本或者追加版本（取决于哪个更方便）。 - Matt