prolog - 在嵌套列表中替换（序言）

Question

/* 如果列表 Ys 是用 Y 替换列表 Xs 中所有出现的 X 的结果，则substitute(X,Y,Xs,Ys) 为真。

这是我到目前为止所拥有的：

subs(_,_,[],[]).
subs(X,Y,[X|L1],[Y|L2]):- subs(X,Y,L1,L2).
subs(X,Y,[H|L1],[H|L2]):- X\=H, not(H=[_|_]), subs(X,Y,L1,L2).
subs(X,Y,[H|_],[L2]):- X\=H, H=[_|_], subs(X,Y,H,L2).

我的代码有效，只是它省略了嵌套列表后面的元素。例如：

?- subs(a,b,[a,[a,c],a],Z).
Z = [b, [b, c]] .

我应该在这个程序中添加什么？

Answer 1

以下是使用 (... -> ... ; ...) 编写它的方法：

subs(_, _, [], []).
subs(X, Y, [H1|T1], [H2|T2]) :-
    (H1 == X ->
        H2 = Y
    ; is_list(H1) ->
        subs(X, Y, H1, H2),
        subs(X, Y, T1, T2)
    ;
        H1 = H2,
        subs(X, Y, T1, T2)
    ).

Answer 2

问题是一旦你找到一个嵌套列表，你就会忘记嵌套列表后面的任何内容。相反，在使用嵌套嵌套递归之后，只需像以前一样继续。因此，您应该按如下方式更改最后一个子句：

subs(X,Y,[H|L1],[H2|L2]):- X\=H, H=[_|_], subs(X,Y,H,H2), subs(X, Y, L1, L2).

除此之外，还有几种方法可以改进代码：

1. 使用cut ( !/0) 停止回溯。这样你就不必重复自己了。
2. 你可以is_list/1用来测试一个参数是否是一个列表。
3. 可以使用更多的空间。真的。

因此，另一种解决方案是（现在使用\+/1代替not/1）：

subs(_, _, [], []).
subs(X, Y, [X|T1], [Y|T2]) :- subs(X, Y, T1, T2), !.
subs(X, Y, [H|T1], [H|T2]) :- \+ is_list(H), subs(X, Y, T1, T2), !.
subs(X, Y, [H1|T1], [H2|T2]) :- subs(X, Y, H1, H2), subs(X, Y, T1, T2).

示范：

?- subs(a, b, [a, [a, [d, f, a]], a, b, a, [g]], Z).
Z = [b, [b, [d, f, b]], b, b, b, [g]].