4

我正在研究一个更长的问题，该问题让我以列表形式复制一个元素 N 次，我相信使用 append 是解决这个问题的正确方法。微小的谓词理论上应该是这样的：

?- repl(x,5,L).
L = [x, x, x, x, x] ;
false.

我似乎无法在网上找到任何提示，即复制单个元素，但我相信我们需要使用 append，但没有递归解决方案。我来自更多的 Haskell 背景，这个问题会更容易执行。有人可以帮我开始吗？:)

到目前为止我的：

repl(E, N, R) :-
    N > 0, append([E], [], R), writeln(R), repl(E, N-1, R), fail.

这给了我：

?- repl(x,5,L).
[x]
[x]
[x]
[x]
[x]
false.

接近但不完全！

4

3 回答 3

11

递归方法将是直截了当的并且会起作用。我建议弄清楚这一点。但这里有一个有趣的选择：

repl(X, N, L) :-
    length(L, N),
    maplist(=(X), L).

如果N被实例化，那么length(L, N)将生成一个只有“空白”长度N的列表（不关心术语）。然后将 的每个元素与变量maplist(=(X), L)统一起来。LX

这提供了一种很好的关系方法，并在一般情况下产生了合理的结果：

| ?- repl(X, N, L).

L = []
N = 0 ? ;

L = [X]
N = 1 ? ;

L = [X,X]
N = 2 ? ;
| ?- repl(X, N, [x,x,x]).

N = 3
X = x

yes
...

要找出递归案例，请考虑您的基本案例是什么样的（它会repl带有计数0- 那么列表是什么样的？）。在递归的情况下，考虑：

repl(X, N, [X|T]) :- ...

含义：列表[X|T]是元素X重复N次数如果...。弄清楚如果是什么？如果您的基本情况是长度0，那么您的递归可能会根据长度列表来描述repl长度列表。不要忘记在这个递归规则中，以确保避免回溯时无限递归。如果您不需要谓词是纯粹的关系并且假设是实例化的，那么它可以相当简单。NreplN-1N > 0N

如果你制作一个简单的递归版本，你可以将它“包装”在这个谓词中以使其与变量一起使用N：

repl(X, N, L) :-
    length(L, N),
    simple_recursive_repl(X, N, L).

...

因为length/2是关系型的，它比只提供给定列表的长度更有用。当N和L没有被实例化时，它变成一个变量列表的生成器，从 length 开始0。在 Prolog 提示符下键入length(L, N).，看看会发生什么。

于 2014-04-19T23:53:12.420 回答
3

决定论

您给出了您设想的谓词的以下示例：

?- repl(x,5,L).
L = [x, x, x, x, x] ;
false.

请注意，;这里的生产力不是很高。如果你想重复x5 次，那么这可以通过一种方式完成。因此，我会将这个谓词指定为确定性而非非确定性，就像您所做的那样。

重复列表

尽管输出在精神上看起来与设想的结果非常接近，但您的代码实际上与可行的解决方案相去甚远。您尝试同时定义基本情况和递归情况，这是行不通的。

这是基本和递归案例的简单实现（但没有@lurker 给出的有趣:-)）：

repeating_list(_, 0, []):- !.
repeating_list(H, Reps1, [H|T]):-
  Reps2 is Reps1 - 1,
  repeating_list(H, Reps2, T).

从某种意义上说，@lurker 的实现更简单，而且肯定更短。

一些扩展

在实际/生产代码中，您希望捕获类型错误并使用相同的谓词处理不同的实例化。第二个子句检查给定列表是否由重复元素组成（如果是，则存在哪一个以及出现了多少次）。

%! repeating_list(+Term:term, +Repeats:integer, -List:list(term)) is det.
%! repeating_list(?Term:term, ?Repeats:integer, +List:list(term)) is det.

repeating_list(_, 0, []):- !.
% The term and number of repetitions are known given the list.
repeating_list(H, Reps, L):-
  nonvar(L), !,
  L = [H|T],
  forall(
    member(X, T),
    % ==/2, since `[a,X]` does not contain 2 repetitions of `a`.
    X == H
  ),
  length([H|T], Reps).
% Repetitions is given, then we generate the list.
repeating_list(H, Reps1, [H|T]):-
  must_be(nonneg, Reps1), !,
  Reps2 is Reps1 - 1,
  repeating_list(H, Reps2, T).
% Repetitions is not `nonneg`.
repeating_list(_, Reps, _):-
  domain_error(nonneg, Reps).

请注意，如果重复次数为负，我会抛出域错误。这使用errorSWI-Prolog 中的库。如果你的 Prolog 不支持这个特性，那么你可以省略最后一个子句。

PS：与 Haskell 的比较

你不知道如何在 Prolog 中解决这个问题的陈述和你在 Haskell 中更容易解决这个问题的陈述对我来说似乎有点奇怪。我认为只有了解了两种实现的外观后，才能比较它们的难度。

于 2014-04-19T23:56:52.377 回答
1

我确实更喜欢findall /3 来构建列表，并且在/3 之间使用范围：

repl(E, N, L) :- findall(E, between(1, N, _), L).
于 2014-04-20T00:54:49.667 回答