prolog, changing atoms in expression

Question

my task is to write a predicate subst(T,A,V,R) that changes all occurences of atom A in expression T to atom V and the result is presented as R.

For instance:

subst(object(one, two),one,three,R). //R=object(three,two).
susbt(a+1,a,2,R). //R=2+1.

It could be easy with the approach: I change the expression to list using T=..L, then I compare every element of L with A and if they're the same, I can change it to V. In the end, I can reverse the very first action (to get the expression again), but I don't know how to deal with situation like: subst((a+1)*(b+3),a,2,W). // ?

Starting with something like T=..L I can get [*,a+1,b+3], but now if I would like to change a to 2, I can't check every consecutive item of L because some of them are not simple atoms/numbers. Now my question is, is there any built-in predicate to check if the element in a list is like: a, 1, etc., but not a+1? I mean if I wouldn't like to check first if it's atom or not and later if it's number of not.

Or maybe there is some easier approach to that matter?

EDIT1: Thanks for comments. I have so far:

subst(T,A,V,R):-T=..L,make_simple(L,L1),replace(L1,A,V,L2),to_exp(L2,R).

make_simple([],[]).
make_simple([H|T],[H|W]):-atom(H),make_simple(T,W),!.
make_simple([H|T],[H|W]):-number(H),make_simple(T,W),!.
make_simple([H|T],[W1|W2]):- \+atom(H),\+number(H),H=..H1,make_simple(H1,W1),make_simple(T,W2).

replace([],_,_,[]).
replace([A|T],A,V,[V|W]):- replace(T,A,V,W),!.
replace([H|T],A,V,[H|W]):- H\=A,\+is_list(H),replace(T,A,V,W),!.
replace([H|T],A,V,[W1|W2]):-H\=A, is_list(H),replace(H,A,V,W1),replace(T,A,V,W2),!.

to_exp([],[]).
to_exp([H|T],[H|W]):- \+is_list(H),to_exp(T,W),!.
to_exp([H|T],[W1|W2]):- is_list(H), (what next?)

Unfortunately, I don't know how to put ap those pieces together now in to_exp part. Especially, when it's like:

to_exp([*,[+,a,1],[-,3,b]]).

or even worse:

to_exp([*,[+,[*,4,2],1],[-,3,b]]).

What I mean, if an element of an outer list is a list, I don't know how to identify that it's exactly list of three elements, where each of them is an atom/number. Any tips?:)

EDIT2

Okay, I was told that it's getting far too complicated. Maybe, but I'm new in Prolog and I'm using only tools/techniques that I've learned so far, because the tasks I am supposed to do are constructed this way. Of course, there must be simpler ways, like that one suggested by @mat, yet I haven't learned about dif or maplist predicates so far. This is why I've decided to continue this one this way.

I've found out that there is no need to check for atom and number separately. There's atomic/1 that returns true if a term is number, atom, or en empty list (so the problem mentioned by @mat about SWI-Prolog doesn't seem to matter that much). Following that, I've changed previous predicates and I've finished to_exp as:

subst(T,A,V,R):-T=..L,make_simple(L,L1),replace(L1,A,V,L2),to_exp(L2,R).

make_simple([],[]).
make_simple([H|T],[H|W]):-atomic(H),make_simple(T,W),!.
make_simple([H|T],[W1|W2]):- \+atomic(H),H=..H1,make_simple(H1,W1),make_simple(T,W2),!.

replace([],_,_,[]).
replace([A|T],A,V,[V|W]):- replace(T,A,V,W),!.
replace([H|T],A,V,[H|W]):- H\=A,\+is_list(H),replace(T,A,V,W),!.
replace([H|T],A,V,[W1|W2]):-H\=A, is_list(H),replace(H,A,V,W1),replace(T,A,V,W2),!.

to_exp([],[]).
to_exp([Z,H1,H2],L):-atomic(H1),atomic(H2),L=..[Z,H1,H2],!.
to_exp([Z,H1,H2],L):- \+atomic(H1),atomic(H2),to_exp(H1,W1),L=..[Z,W1,H2].
to_exp([Z,H1,H2],L):- atomic(H1),\+atomic(H2),to_exp(H2,W1),L=..[Z,H1,W1].
to_exp([Z,H1,H2],L):- \+atomic(H1),\+atomic(H2),to_exp(H1,W1),to_exp(H2,W2),L=..[Z,W1,W2].

Now, it works both for functors and arguments, simple and nested ones. Anyway, thanks for the influence, I definitely will consider using dif and maplist in the future. Cheers:)

You are on the right track. You can use atom/1: True if its argument is an atom. Beware: It's a non-monotonic predicate, so use it only when the argument is sufficiently instantiated. See for example ?- atom(X), X = a. vs. ?- X = a, atom(X).. — mat
Why not recursively break it down using =..? So (a+1)*(b+3) leads to [*,a+1,b+3] and each of those elements leads to [*], [+,a,1], and [+,b,3]. At the lowest level, you can find your atoms to replace. You can use mat's idea of using atom to know when you've "hit bottom". number(X) is true if X is a number. — lurker
How would you want subst(foo(a, b), foo, bar, R). to work? Should it fail? Should it succeeds with R = foo(a, b)? Or should it succeed with R = bar(a, b)? — lurker
=.. applies to expressions also, since expressions are just terms: ?- 1+2 =.. [+,1,2]. — CapelliC
Thanks for all your comments. I've edited my question, can you look at it?:) — Paweł Poręba

mat mat · Accepted Answer · 2015-11-24T08:40:44

Please take into account the complete regularity of Prolog terms.

substitution(A0, A0, A, A).    
substitution(T0, A0, A, T) :-
        dif(T0, A0),
        T0 =.. [F|Args0],
        maplist(subst_(A0, A), Args0, Args),
        T =.. [F|Args].

subst_(A0, A, T0, T) :- substitution(T0, A0, A, T).

Example query and its result:

?- substitution(a+b+[c,d,a], a, 2, R).
R = 2+b+[c, d, 2] ;
false.

prolog, changing atoms in expression

2 Answers