Pourquoi Prolog répète-t-il la dernière valeur de ma liste après le point-virgule?

Question

Je tente de créer ma propre règle de tri dans Prolog, et après beaucoup de tâtonnements, j'ai réussi à la faire fonctionner, sauf quand j'appuie sur; en swipl, il ajoutera la dernière valeur de ma liste à la liste.

Le code utilisé est le suivant:

min trouve une valeur minimale dans une liste et retourne

min([H|[]],H). 
min([H|T],Min) :- 
    min(T,CurrentMin), 
    H < CurrentMin, 
    Min = H. 
min([H|T],Min) :- 
    min(T,CurrentMin), 
    CurrentMin =< H, 
    Min = CurrentMin. 

supprimer trouve l'élément que vous souhaitez supprimer dans une liste et retourne une liste l'élément a été supprimé

Enfin, sort_inc tente d'utiliser les règles ci-dessus pour créer une liste triée dans l'ordre croissant.

sort_inc([H|[]],[H]). 
sort_inc(UnOrderedList,[H|OrderedTail]) :- 
    min(UnOrderedList,H), 
    remove(H,UnOrderedList,T), 
    sort_inc(T,OrderedTail). 

Le tri fonctionne très bien, mais quand je presse le point-virgule dans swipl après l'exécution de la règle sur une liste, il répétera la dernière valeur dans la liste comme si:

sort_inc([3,6,8,4],List). 
List = [3, 4, 6, 8] ; 
List = [3, 4, 6, 8, 8] ; 
List = [3, 4, 6, 8, 8, 8] ; 
List = [3, 4, 6, 8, 8, 8, 8] ; 
List = [3, 4, 6, 8, 8, 8, 8, 8] ; 
List = [3, 4, 6, 8, 8, 8, 8, 8, 8] ; 
List = [3, 4, 6, 8, 8, 8, 8, 8, 8|...] . 

Pourquoi ne répéter cette dernière valeur au lieu de retourner false lorsque le point-virgule est entré?

Answer 1

Vous avez des problèmes dans votre remove/3 mise en œuvre, essayez ceci:

remove(X, [X|Rest], Result) :- 
    !, remove_sub(X, [X|Rest], Result). 
remove(X, [Y|Rest], Z) :- 
    X \= Y, 
    remove(X, Rest, RestRemoved), 
    Z = [Y|RestRemoved]. 
remove(_, [], []). 

remove_sub(X, [X|Rest], Rest). 
remove_sub(X, [Y|Rest], Z) :- 
    remove_sub(X, Rest, RestRemoved), 
    Z = [Y|RestRemoved]. 

Pour être exact, votre première clause de supprimer/3 génère une solution inadéquate en laissant la liste intacte, même si l'élément à supprimer est son membre:

?- remove(1, [1, 2, 3], L). 
L = [2, 3] ; 
L = [1, 2, 3]. 

aussi, s'il vous plaît garder à l'esprit que de nombreuses implémentations Prolog auront supprimer/3 et/min 2 mises en œuvre (ainsi que le tri, bien sûr) fourni. Par exemple, Swi-Prolog comprend:

• supprimer/3, qui fait presque ce que votre que votre remove/3 était censé faire, sauf qu'il supprime tous les cas de l'élément à la fois
• sélectionner/3, fait presque ce que votre supprimer/3 était censé faire, sauf qu'il ne permet pas la suppression des éléments qui ne sont pas présents dans la liste
• min_list/2 et min_member/2, pour trouver les éléments min de la liste
• sort/2, msort/2, predsort/3, pour faire le tri réel

Même si votre objectif est de créer votre implémentation personnalisée, il est toujours utile de les utiliser pour tester votre propre implémentation, par ex. vous pouvez rapidement remplacer l'appel à votre supprimer/3 avec supprimer/3 pour savoir où le problème est.