[Prolog] Vervangen item in een list

[Verwijderd]

Ik zit een beetje met Prolog te spelen; Ik heb mezelf een paar opgaven gegeven, waaronder lists.

Nu heb ik een stukje code geschreven dat een item X in een lijst vervangt door een item Y, als volgt:

code:

replace_item([], _, _, []). % basisgeval
replace_item([Ah|At], X, Y, [Ah|Bt]) :- Ah \= X,  replace_item(At, X, Y, Bt). % oude houden
replace_item([_|At], X, Y, [Y|Bt]) :- replace_item(At, X, Y, Bt). % X vervangen door Y

Nu geeft Prolog in principe het juiste antwoord:

code:

replace_item([1,2,3,4,5], 5, a, Z).
Z = [1, 2, 3, 4, a] ;

Maar, Prolog geeft er nog veel meer:

code:

Z = [1, 2, 3, a, a] ;
Z = [1, 2, a, 4, a] ;
Z = [1, 2, a, a, a] ;
Z = [1, a, 3, 4, a] ;
Z = [1, a, 3, a, a] ;
Z = [1, a, a, 4, a] ;
Z = [1, a, a, a, a] ;
Z = [a, 2, 3, 4, a] ;
Z = [a, 2, 3, a, a] ;
Z = [a, 2, a, 4, a] ;
Z = [a, 2, a, a, a] ;
Z = [a, a, 3, 4, a] ;
Z = [a, a, 3, a, a] ;
Z = [a, a, a, 4, a] ;
Z = [a, a, a, a, a].

Nu kan ik dit wel voorkomen door een cut te gebruiken:

code:

replace_item([], _, _, []).
replace_item([Ah|At], X, Y, [Ah|Bt]) :- Ah \= X,  !, replace_item(At, X, Y, Bt).
replace_item([_|At], X, Y, [Y|Bt]) :- replace_item(At, X, Y, Bt).

code:

144 ?- replace_item([1,2,3,4,5], 5, a, Z).
Z = [1, 2, 3, 4, a].

Maar kan ik mijn definitie dusdanig verbeteren dat ik geen cut nodig heb?
Waarom gaat Prolog de andere getallen ook aanpassen? De X verandert verder toch niet?

[ Voor 3% gewijzigd door Verwijderd op 06-03-2011 10:22 ]

[m-m]

Omdat Prolog alweer een tijdje geleden voor me was heb ik het ook eens geprobeerd om te kijken of ik uit de opgave kon komen.

Ik kom hierop (sorry, ik heb wat slechtere variable-namen gebruikt ):

code:

replace_item([], _, _, []).
replace_item([A|B], X, Y, [A|C]) :- A \= X, replace_item(B, X, Y, C).
replace_item([A|B], X, Y, [Y|C]) :- A = X, replace_item(B, X, Y, C).

die lijkt het wel goed te doen:

code:

?- replace_item([1,2,3,4,5], 5, a, Z).
Z = [1, 2, 3, 4, a] ;
false.

Waarom jouw implementatie doet wat 'ie doet, weet ik niet zeker. Maar ik denk dat het komt omdat je 3e regel ook als alternatief toepasbaar is op de 2e en hij dus backtrackt. I.t.t. functioneel programmeren is het bij prolog immers niet zo dat hij de eerste matchende rule pakt, maar hij gebruikt alles dat een resultaat geeft om alle mogelijkheden te geven.

Hij maakt dus niet een keuze voor een bepaalde rule, maar bouwt een boom op. Na het geven van een eindantwoord gaat hij terug die boom in om te kijken of er nog andere paden zijn om tot een (alternatief) eindantwoord te komen.

[ Voor 11% gewijzigd door m-m op 06-03-2011 10:46 ]

[RayNbow]

m-m schreef op zondag 06 maart 2011 @ 10:42:

code:

replace_item([], _, _, []).
replace_item([A|B], X, Y, [A|C]) :- A \= X, replace_item(B, X, Y, C).
replace_item([A|B], X, Y, [Y|C]) :- A = X, replace_item(B, X, Y, C).

De 3e clause kun je ook zo opschrijven:

Prolog:

replace_item([X|B], X, Y, [Y|C]) :- replace_item(B, X, Y, C).

Maar ik denk dat het komt omdat je 3e regel ook als alternatief toepasbaar is op de 2e en hij dus backtrackt. I.t.t. functioneel programmeren is het bij prolog immers niet zo dat hij de eerste matchende rule pakt, maar hij gebruikt alles dat een resultaat geeft om alle mogelijkheden te geven.

Dat doet Prolog idd.

[m-m]

RayNbow schreef op zondag 06 maart 2011 @ 10:44:
[...]

De 3e clause kun je ook zo opschrijven:

Prolog:

replace_item([X|B], X, Y, [Y|C]) :- replace_item(B, X, Y, C).

Gelijk heb je, dat is mooier

[Verwijderd]

Ik begrijp het, even backtracking nog wat beter bestuderen dus
Thanks

[Soultaker]

Om de duplicatie van de recursie-regels te voorkomen kun je overwegen om een predicate voor het vervangen van het karakter af te splitsen (DRY) :

Prolog:

replace(X, X, Y, Y) :- !.
replace(A, _, _, A).

replace_item([], _, _, []).
replace_item([A|B], X, Y, [C|D]) :- replace(A, X, Y, C), replace_item(B, X, Y, D).

Je kunt de boel ook inlinen als je dat liever hebt:

Prolog:

replace_item([], _, _, []).
replace_item([A|B], X, Y, [C|D]) :- (A=X -> C=Y; C=A), replace_item(B, X, Y, D).

Punt is dat je in beide gevallen precies één predicaat hebt voor de basis en één predicaat voor de recursiestap.