substitute in a nested list (prolog)

Question

/* substitute(X,Y,Xs,Ys) is true if the list Ys is the result of substituting Y for all occurrences of X in the list Xs.

This is what I have so far:

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).

My code works except it omits the elements following the nested list. For example:

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

What should I add to this program?

Answer 1

The problem is that once you find a nested list, you forget about whatever is behind that nested list. Instead, after recursing with the nested nest, simply continue as before. Thus, you should change the last clause as follows:

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

Aside from that, there are a couple of ways in which you can improve the code:

1. Use cuts (!/0) to stop backtracking. In this way you don't have to repeat yourself.
2. You can use is_list/1 to test whether an argument is a list.
3. It's okay to use more spaces. Really.

So, an alternative solution is (now using \+/1 instead of 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).

Demonstration:

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

Answer 2

Here is how you could write it using (... -> ... ; ...):

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 3

I'm your instructor ... :)