复制列表中第n个值

Question

我对Prolog比较陌生，现在想实现一个递归规则duplicate_nth(N,L1,L2)，该规则可以接受一个从1开始的索引N，一个列表L1，并将L1的第N个值复制一份，并返回到一个列表L2中。

使用示例：

?- duplicate_nth(1, [2,3,4], X).
X = [2,2,3,4].                  % expected result

我的当前代码如下：

duplicate_nth(N,[H|T],L2) :- 
    N = 1,                      % Is `N` equal to 1?    
    append([H],[H|T],L2).       % If so, prepend `H` to `[H|T]`
duplicate_nth(N,H|T,L2) :-
    N > 1, 

如果N = 1，这个方法是有效的。但是，如果N > 1，我不确定该如何继续。

- user969416

---

你的第一个子句中实际上不需要使用append。任何时候当你看到append([X], List, Result)时，它等同于Result = [X|List]。在这种情况下，[H] append [H|T] 就是 [H|[H|T]]，也就是 [H,H|T]。 - lurker

Answer 1

不需要担心如何正确地实现递归谓词！

只需将“递归部分”委托给same_length/2、append/3和length/2：

duplicate_nth(N,Xs0,Xs1) :-                    % index `N` is 1-based
   same_length([_|Xs0],Xs1),
   Suffix = [X|_],
   append(Prefix,Suffix,Xs0),
   length([_|Prefix],N),
   append(Prefix,[X|Suffix],Xs1).

示例查询：

?- N   = 1, 
   Xs0 = [a,b,c,d], 
   duplicate_nth(N,Xs0,Xs1).
  N = 1, Xs0 = [a,b,c,d], Xs1 = [a,a,b,c,d]    % 只有一个解
; false.

让我们将上面的查询泛化并看到解决方案集增长！

?- Xs0 = [a,b,c,d],
   duplicate_nth(N,Xs0,Xs1).
  N = 1, Xs0 = [a,b,c,d], Xs1 = [a,a,b,c,d]    % （与之前相同的解决方案）
; N = 2, Xs0 = [a,b,c,d], Xs1 = [a,b,b,c,d]    % （新的解决方案）
; N = 3, Xs0 = [a,b,c,d], Xs1 = [a,b,c,c,d]    % （新的解决方案）
; N = 4, Xs0 = [a,b,c,d], Xs1 = [a,b,c,d,d]    % （新的解决方案）
; false.

请注意，duplicate_nth/3在“另一个方向”上使用时也有效。

?- Xs1 = [a,b,b,c,d,d,e],
   duplicate_nth(N,Xs0,Xs1).
  N = 2, Xs1 = [a,b,b,c,d,d,e], Xs0 = [a,b,c,d,d,e]
; N = 5, Xs1 = [a,b,b,c,d,d,e], Xs0 = [a,b,b,c,d,e]
; false.

最后，让我们运行最通用的查询！

?- duplicate_nth(N,Xs0,Xs).
  N = 1, Xs0 = [_A],          Xs = [_A,_A]
; N = 1, Xs0 = [_A,_B],       Xs = [_A,_A,_B]
; N = 2, Xs0 = [_A,_B],       Xs = [_A,_B,_B]
; N = 1, Xs0 = [_A,_B,_C],    Xs = [_A,_A,_B,_C]
; N = 2, Xs0 = [_A,_B,_C],    Xs = [_A,_B,_B,_C]
; N = 3, Xs0 = [_A,_B,_C],    Xs = [_A,_B,_C,_C]
; N = 1, Xs0 = [_A,_B,_C,_D], Xs = [_A,_A,_B,_C,_D]
...

想要快速实现公平的枚举？没问题！

- repeat

Answer 2

几乎所有列表函数都具有相同的结构。一个基本情况：

function(FixedValues,List1,List2) :-
    !.

其中List2是基于List1函数编写的，而FixedValues是一组已确定的参数。

还有一个归纳情况：

function(Values,[H|T],[H2|T2]) :-
    other_function(H,H2), %transform H into H2
    ValuesNext is Values-1, %or some other function
    function(ValuesNext,T,T2).

! 是一个“剪切符号”，如果第一个谓词的条件被满足，它会阻止Prolog执行其他谓词定义。

---

针对这个问题，尝试如下：

duplicate_nth(1,[H|T],[H,H|T]) :- %base case
    !.

duplicate_nth(N,[H|T],[H|T2]) :- %inductive case
    N1 is N-1,
    duplicate_nth(N1,T,T2).

---

在大多数情况下，您需要使程序更安全，因为N可能超出范围（小于或等于零，或大于列表的长度）。

在这种情况下，请添加：

duplicate_nth(_,[],[]).

- Willem Van Onsem

---

如果在递归（“归纳”）步骤中添加“N > 1”，则无需进行切割。 - lurker

是的，但这会降低谓词的性能。因为Prolog从上到下调用谓词时，它已经知道在调用第一个谓词时不应该调用第二个谓词。但这种方法确实没有问题。 - Willem Van Onsem

非常好的答案，代码可行并且您解释了一些概念，比一些书籍讲得更好。 - user969416