substitut dans une liste imbriquée (prolog)

Question

/*

C'est ce que j'ai jusqu'à présent:

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

Mon code fonctionne, sauf qu'il omet les éléments suivants de la liste imbriquée. Par exemple:

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

Que devrais-je ajouter à ce programme?

Answer 1

Le problème est qu'une fois que vous trouvez une liste imbriquée, vous oubliez ce qui est derrière cette liste imbriquée. Au lieu de cela, après avoir récuré avec le nid imbriqué, continuez simplement comme avant. Ainsi, vous devez changer la dernière clause comme suit:

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

En dehors de cela, il y a deux façons dont vous pouvez améliorer le code:

1. Utilisez cuts (!/0) à arrêter de faire marche arrière. De cette façon, vous n'avez pas à vous répéter.
2. Vous pouvez utiliser is_list/1 pour tester si un argument est une liste.
3. Il est correct d'utiliser plus d'espaces. Vraiment.

Ainsi, une solution alternative est (maintenant à l'aide \+/1 au lieu de 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). 

Démonstration:

?- 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

Voici comment vous pouvez écrire à l'aide (... - > ...; ...):

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