listes.pl : test de prolog / P. TRAU
/* listes.pl : test de prolog /P. TRAU janvier 2001 */
/* on trouvera ici 5 paragraphes :
- les prédicats listes prédéfinis (en SWI Prolog)
- des règles générales sur les listes
- l'application des listes aux ensembles
- listes ordonnées (avec relation d'ordre, ce qui permet par exemple de trier)
- listes d'entiers
*/
/* prédicats prédéfinis (d'apres help(3-24) *************************
*
* member(Elem,Liste) dit si Elem appartient à la Liste, ou en ressort les éléments
* append(Liste1,Liste2,ListeResult) concatène deux listes (ou coupe si les premières sont libres et result lié)
* delete(ListeAvecDesX,X,ListeResultSansAucunX) enlève tous les X d'une liste
* select(ListeAvecAuMoinsUnX,X,ListeResultAvecUnXDeMoins) enlève UN seul X de la liste
* (faux s'il y en avait aucun). Peut aussi servir à insérer X si 1er arg libre et dernier lié
* reverse(Liste,ListeDansLOrdreInverse)
* last(DernierElemDeLaListe,Liste)
* nth1(CombienTieme,Liste,ElemDeLaListe) le 1er est noté 1
* nth0(CombienTieme,Liste,ElemDeLaListe) le 1er est noté 0
* length(Liste,NbDElementsDeLaListe)
* sort(ListeMelangee,ListeTriee) les doublons ne sont pris qu'une fois
* msort(ListeMelangee,ListeTriee) les doublons sont gardés
*
*/
/********************************************************************
* règles générales sur listes */
/* member(Elem,Liste) est prédéfini et fait la même chose
* Si Elem est libre, rendra successivement tous les éléments de la liste */
membre(Elem,[Elem|_]).
membre(Elem,[_|Suivants]):-membre(Elem,Suivants).
/* étendons le à plusieurs membres (pas nécessairement contigus)
* membres(PetiteListe,GrandeListe) : les deux listes doivent être liées ! */
membres([Elem|AutresElem],Liste):-membre(Elem,Liste),membres(AutresElem,Liste).
membres([],_).
/* append est prédéfini et fait la même chose. Mais j'aime bien tout réécrire
* ceci permet de coller deux listes l'une derrière l'autre, en une troisième.
* un but rigolo : colle(X,Y,[a,b,c]). (il y a en tout 4 solutions) */
colle([X|SuiteDesX],ListeDesY,[X|SuiteDesXpuisLesY]) :- colle(SuiteDesX,ListeDesY,SuiteDesXpuisLesY).
colle([],Liste,Liste).
/* colle peut également servir à isoler le dernier d'une liste, et récupérer
* la liste restante : */
coupe_dernier(ListeRestante,Dernier,ListeInitiale):-colle(ListeRestante,[Dernier],ListeInitiale).
/* ou vérifier si une sous-liste est au début ou la fin d'une liste : */
debut(SousListe,Liste):-colle(SousListe,_,Liste).
final(SousListe,Liste):-colle(_,SousListe,Liste).
/* pour ajouter un élément en tête de liste
* append([X],Liste,ListeResult) peut être utilisé aussi */
ajoute(X,Liste,[X|Liste]). /* le troisième arg est la liste augmentée de X */
/* ma version de reverse qui inverse l'ordre */
inverse([Prem|Reste],Resultat) :- inverse(Reste,Tampon),colle(Tampon,[Prem],Resultat).
inverse([],[]).
/* dit si tous les éléments de la liste sont différents */
tous_differents([]). %ou même tous_differents([_]).
tous_differents([T|Q]):- not(membre(T,Q)),tous_differents(Q).
/* celui-là rend une liste (plus courte) où tous sont différents */
virer_doublons([Tete|Queue],ResultSansDoublons):-
membre(Tete,Queue),virer_doublons(Queue,ResultSansDoublons).
virer_doublons([Tete|Queue],[Tete|ResultSansDoublons]):-
not(membre(Tete,Queue)),virer_doublons(Queue,ResultSansDoublons).
virer_doublons([],[]).
/* supprime(ElemXASupprimer,ListeInitiale,ListeSansX)
* si l'elem à supprimer n'était déja pas présent, la liste est retournée telle quelle */
supprime(X,[X|ResteListeInitiale],ListeSansX) :-
supprime(X,ResteListeInitiale,ListeSansX).
supprime(X,[PasX|ResteListeInitiale],[PasX|ListeSansX]) :-
X\=PasX,supprime(X,ResteListeInitiale,ListeSansX).
supprime(_,[],[]).
/* supprime_plusieurs(ListeElemASupprimer,ListeInitiale,ListeRacourcie) */
supprime_plusieurs([Prem|Autres],ListeInitiale,ListeRacourcie) :-
supprime(Prem,ListeInitiale,ListeUnPeuRacourcie),
supprime_plusieurs(Autres,ListeUnPeuRacourcie,ListeRacourcie).
supprime_plusieurs([],ListeInitiale,ListeInitiale).
/* permutation(ListeInitiale,LesMemesDansUnAutreOrdre).
* si le deuxière arg est libre, donne toutes les permutations possibles.
* Attention la listeinitale est aussi une des solutions */
permutation(ListeInitiale,[T|Result]):-select(ListeInitiale,T,Tmp),permutation(Tmp,Result).
permutation([],[]).
/* write écrit : [a, b, c, d], writef écrit : abcd et aff_liste écrit : [ a b c d ] */
aff_elements_de_liste([T|Q]) :- write(T), write(' '),aff_elements_de_liste(Q).
aff_elements_de_liste([]).
aff_liste(L) :- write('[ '),aff_elements_de_liste(L),write(']'),nl.
/*************************************************************************
* version ensembles */
appartient_a(X,Ensemble):-membre(X,Ensemble).
inclus(PetitEns,GrandEns):-membres(PetitEns,GrandEns).
/* union existe déjà et fait pareil */
unir(E1,E2,E1uE2):-colle(E1,E2,Temp),virer_doublons(Temp,E1uE2).
complement(Ens,Espace,Cmplt):-supprime_plusieurs(Ens,Espace,Cmplt).
inter([T1|Q1],E2,[T1|Result]):-appartient_a(T1,E2),inter(Q1,E2,Result).
inter([T1|Q1],E2,Result):-not(appartient_a(T1,E2)),inter(Q1,E2,Result).
inter([],_,[]).
/*************************************************************************
* cas des listes ordonnées (avec les opérateurs =< et >) */
/* je définis la relation d'ordre (si on veut traiter autre chose que des entiers) */
superieur(X,Y):-X>Y.
inferieur_ou_egal(X,Y):-not(superieur(X,Y)). /* ou alors =< (et pas <=) */
/* vérifie si la liste est triée */
est_trie([_]).
est_trie([X,Y|Suite]):- inferieur_ou_egal(X,Y),est_trie([Y|Suite]).
/* une solution pour trier est de tester toutes les permutations et de ne garder
* que celles bien triées (évidement pas très efficace comme solution,
* ne pas dépasser une dizaine d'éléments). */
tri_debile(Liste,Resultat):-permutation(Liste,Resultat),est_trie(Resultat).
/* autre tri : par insertion : je sors le 1er, je trie le reste (récursivement)
* puis je l'insère au bon endroit (devant le 1er plus grand).
* Avant tout, je définis : insertion(Elem,SuiteOrdonnée,SuiteOrdonnéeAvecElem) */
insertion(Elem,[Prem|Suite],[Elem,Prem|Suite]):-inferieur_ou_egal(Elem,Prem).
insertion(Elem,[Prem|Suite],[Prem|Resultat]):-superieur(Elem,Prem),insertion(Elem,Suite,Resultat).
insertion(Elem,[],[Elem]).
tri_insertion([Prem|Suite],Resultat):-tri_insertion(Suite,Tmp),insertion(Prem,Tmp,Resultat).
tri_insertion([],[]).
/* trier la liste : je prends le premier, je coupe la liste en ceux plus petits et ceux
* plus grands que je trie, puis je recolle les deux. (algorithme QuickSort)
* Les 3 premières règles (clauses) sont pour couper.
* exemple de test : trier([1,4,6,2,8,4,3,6,1,0,9],X). */
couper_liste([Prem|Reste],Seuil,[Prem|ListeDesPetits],ListeDesGrands) :-
inferieur_ou_egal(Prem,Seuil),
couper_liste(Reste,Seuil,ListeDesPetits,ListeDesGrands).
couper_liste([Prem|Reste],Seuil,ListeDesPetits,[Prem|ListeDesGrands]) :-
superieur(Prem,Seuil),
couper_liste(Reste,Seuil,ListeDesPetits,ListeDesGrands).
couper_liste([],_,[],[]).
trier([Prem|Reste],Resultat) :-
couper_liste(Reste,Prem,ListeDesPetits,ListeDesGrands),
trier(ListeDesPetits,PetitsEtTries),
trier(ListeDesGrands,GrandsEtTries),
colle(PetitsEtTries,[Prem|GrandsEtTries],Resultat).
trier([],[]).
/* fusionner deux listes déja triées par ordre croissant */
fusion([T1|Q1],[T2|Q2],[T1|Qres]):-inferieur_ou_egal(T1,T2),fusion(Q1,[T2|Q2],Qres).
fusion([T1|Q1],[T2|Q2],[T2|Qres]):-superieur(T1,T2),fusion([T1|Q1],Q2,Qres).
/* cas ci-dessous inutile si j'ai prévu l'égalité plus haut ( =< au lieu de < )
* mais l'écriture me plaisait (tête à deux éléments)
* fusion([Tidem|Q1],[Tidem|Q2],[Tidem,Tidem|Qres]):-fusion(Q1,Q2,Qres). */
fusion([],L2,L2).
fusion(L1,[],L1).
/* rechercher le plus grand : max(Liste,X) */
max([Prem|Suite],X) :- max(Suite,X),superieur(X,Prem).
max([Prem|Suite],Prem) :- max(Suite,X),not(superieur(X,Prem)).
max([X],X).
min([Prem|Suite],X) :- min(Suite,X),not(superieur(X,Prem)).
min([Prem|Suite],Prem) :- min(Suite,X),superieur(X,Prem).
min([X],X).
/***************************************************************************************
* cas particulier des listes d'entiers */
/* pour commencer, rappel sur les opérateurs arithmétiques :
* attention : bien faire la différence entre is, = et =:=
* - is calcule la valeur à droite (toujours liée) et instancie le résultat à la variable (libre)
* à gauche, ou la compare à la val liée de gauche. par ex X is 10+15 met 25 dans X, ou dit True
* si X vaut 25 (parce que avant on a dit X is 30-5 ou même X=25)
* - = recopie l'équation avec les variables instanciées : Y=10,X=Y+15,write(X). affiche 10+15
* mais on pourra toujours tester X par =:= (ou même is, si il est à droite du is).
* Au moins un des arguments doit être lié.
* - =:= évalue à droite et à gauche et regarde si les résultats sont égaux (les deux arguments doivent être liés)
* les opérateurs de comparaison (qui évaluent à droite et à gauche) sont :
* =:= =\= < > =< >= , les autres opérateurs sont + - * / mod ** , sin,cos,log .... (voir help(3-22).) */
/* evalue([1,2,3,4],X) retourne X=1234. */
evalue(ListeChiffres,Resultat) :-
append(TousSaufDernier,[Dernier],ListeChiffres),
evalue(TousSaufDernier,X),
Resultat is Dernier + 10*X.
evalue([X],X).
somme([T|Q],Result):-somme(Q,Tmp),Result is T+Tmp.
somme([],0).
