在特定位置插入元素

Question

我开始使用 Prolog（只是为了我自己），但我正在为递归而苦苦挣扎。

我想要一个 "method"，它可以在列表中的特定位置插入一个元素。到目前为止我尝试的是：

insertAt(Element,Position,List,ResultList)

insertAt(Element,0,L,[Element|L]).
insertAt(Element,Pos,[E|L],ZL):-
    Pos1 is Pos-1,
    insertAt(Element,Pos1,L,ZL),
    append(E,ZL1,ZL).

我觉得我很复杂，因为我无法理解递归究竟是如何工作的...

也许有人可以帮助我。

Answer 1

您的代码有几个特点让初学者难以理解。特别是，在以有趣（实际上也是严肃）的方式与程序交互时，使用模式化的低级算术是一个严重的障碍。

例如，要了解关系，从最一般的查询开始很有用。这只问 "Is there any solution at all, and if so, what does a solution look like?"。在您的具体示例中，最一般的查询如下所示：

?- insertAt(E, Pos, Ls0, Ls).

由于您使用的是非声明性算术谓词，这几乎立即产生 instantiation error：

?- insertAt(E, Pos, Ls0, Ls).
Pos = 0,
Ls = [E|Ls0] ;
ERROR: insertAt/4: Arguments are not sufficiently instantiated

此外，您使用命令式名称 ("insert...") 阻碍了良好的声明式阅读。这使得培养对关系编程的感觉变得不必要地困难。

因此，我建议您：(1) 使用更具声明性的谓词名称，以及 (2) 使用自然数的符号表示，使谓词更易于理解和更通用。

我将使用数字 0 来表示零，用 s(X) 来表示数字 X 的后继。有关此表示的更多信息，请参阅 successor-arithmetics。

进行这些更改后，代码变为：

element_at(E, 0, [_|Ls], [E|Ls]).
element_at(E, s(X), [L|Ls0], [L|Ls]) :-
        element_at(E, X, Ls0, Ls).

为了理解这个程序，我们声明式地读它：第一个子句是true if位置是0，最终列表的头部是 E，尾部......等等。第二个子句是 true if element_at(E, X, Ls0, Ls) holds, head of ...等

很好，最通用的查询现在工作得更好了：

?- element_at(E, Pos, Ls0, Ls).
Pos = 0,
Ls0 = [_G1071|_G1072],
Ls = [E|_G1072] ;
Pos = s(0),
Ls0 = [_G1073, _G1079|_G1080],
Ls = [_G1073, E|_G1080] ;
Pos = s(s(0)),
Ls0 = [_G1073, _G1081, _G1087|_G1088],
Ls = [_G1073, _G1081, E|_G1088] .

请注意这里有一些不公平的地方：剩余位置的答案在哪里？为了更公平的枚举，我们使用length/2，预先说明我们正在考虑的列表的长度：

?- length(Ls0, _), element_at(E, Pos, Ls0, Ls).
Ls0 = [_G1124],
Pos = 0,
Ls = [E] ;
Ls0 = [_G1124, _G1127],
Pos = 0,
Ls = [E, _G1127] ;
Ls0 = [_G1124, _G1127],
Pos = s(0),
Ls = [_G1124, E] .

现在更清楚了不同参数如何相互作用，因为您已经看到谓词描述的术语的各种示例。

事实上，为了减少我们需要跟踪的参数和变量名的数量，我在描述列表时经常使用DCG notation，我也想向您展示这个替代版本：

element_at(Element, 0, [_|Ls]) -->
        [Element],
        list(Ls).
element_at(Element, s(X), [L|Ls]) -->
        [L],
        element_at(Element, X, Ls).

list([]) --> [].
list([L|Ls]) --> [L], list(Ls).

?- length(Ls0, _), phrase(element_at(E, Pos, Ls0), Ls).
Ls0 = [_G1148],
Pos = 0,
Ls = [E] ;
Ls0 = [_G1148, _G1151],
Pos = 0,
Ls = [E, _G1151] ;
Ls0 = [_G1148, _G1151],
Pos = s(0),
Ls = [_G1148, E] .

一旦您阅读了 dcg 符号，您就会清楚这个版本。

最后，您可能会说 "Well, that's nice, but s(X) notation still seems quite strange"，并且您可能希望在程序中对整数使用更广泛使用的印度-阿拉伯语表示法。

为此，我们可以简单地采用上面的任一版本，并用具有 CLP(FD) 约束的声明性整数算法替换 s(X) 符号。例如，第一个版本：

:- use_module(library(clpfd)).

element_at(E, 0, [_|Ls], [E|Ls]).
element_at(E, X, [L|Ls0], [L|Ls]) :-
        X #> 0,
        X #= X0 + 1,
        element_at(E, X0, Ls0, Ls).

这也适用于所有方向，正如我们对声明性一般的谓词所期望的那样：

?- length(Ls0, _), element_at(E, Pos, Ls0, Ls).
Ls0 = [_G2095],
Pos = 0,
Ls = [E] ;
Ls0 = [_G2095, _G2098],
Pos = 0,
Ls = [E, _G2098] ;
Ls0 = [_G2095, _G2098],
Pos = 1,
Ls = [_G2095, E] .

请参阅 clpfd 了解更多信息，我希望这篇 post 能鼓励您更相关地思考您的 Prolog 代码，从各个方面尝试它，并以声明的方式阅读它。（描述的是什么？）

Answer 2

Prolog 的一个特性是模式匹配，即基于谓词参数的规则选择。这种特性是 Prolog 符号的关键，允许对关系进行紧凑的描述，特别是对于递归术语，如列表。请注意，列表只是 'syntactic sugar' 用于递归术语，带有常规函子（术语名称，在日常用语中）。

insertAt(Element,0,L,[Element|L]). % ok
insertAt(Element,Pos,[E|L],[E|ZL]):- % you forgot to cons back E
    Pos1 is Pos-1,
    insertAt(Element,Pos1,L,ZL). % done, append is useless
    %append(E,ZL1,ZL).

SWI-Prolog有nth1/4和nth0/4，可以执行插入：

?- nth0(1,L,x,[1,2,3]).
L = [1, x, 2, 3].

Answer 3

让same_length/2, append/3, and length/2处理递归！

insertAt(E,N,Xs,Ys) :-
   same_length([E|Xs],Ys),
   append(Before,Xs0,Xs),
   length(Before,N),
   append(Before,[E|Xs0],Ys).

示例查询：

?- insertAt(X, N, [a,b,c,d,e], Ys).
(  N = 0, Ys = [X,a,b,c,d,e]
;  N = 1, Ys = [a,X,b,c,d,e]
;  N = 2, Ys = [a,b,X,c,d,e]
;  N = 3, Ys = [a,b,c,X,d,e]
;  N = 4, Ys = [a,b,c,d,X,e]
;  N = 5, Ys = [a,b,c,d,e,X]
;  false
).

在特定位置插入元素

insert Element at specific position

list

prolog