liste1([a,b,c,b,c,e,a]). liste2([c,c,b,a,b,e,e]). % voici une correction du tp sur les listes en prolog % pour vous aider a preparer le controle de TP. % ce fichier fonctionne tel quel, % si vous souhaitez le tester, le modifier etc. % ============================================================ % LE PREDICAT appartient(X,L) % QUI EST VRAI LORSQUE L'ELEMENT X % APPARTIENT A LA LISTE L % X appartient a une liste commencant par X appartient(X,[X|L]). % si X appartient a une liste L, % alors X appartient a toute liste commencant par Y % et suivi de L % --- cette clause recouvre la precedente % pour ne pas avoir plusieurs moyens d'obtenir % la reponse "yes" lors d'un appel appartient(toto,L) % on peut rajouter Y\==X a cette clause. appartient(X,[Y|L]):- appartient(X,L). % ============================================================ % LE PREDICAT non_appartient(X,L) % QUI EST VRAI LORSQUE L'ELEMENT X % APPARTIENT A LA LISTE L % pour tout X % X n'appartient pas a la liste vide. non_appartient(X,[]). % si X n'est pas Y % et si X n'appartient pas a L % alors X n'appartient pas a la liste de tete Y et de reste L non_appartient(X,[Y|L]):-X\==Y,non_appartient(X,L). % ============================================================ % LE PREDICAT sans_repetition(L) % QUI EST VRAI LORSQUE L NE CONTIENT PAS DEUX OCCURENCES D'UN MEME ELEMENT % la liste vide est sans repetition sans_repetition([]). % si X ne figure pas dans L % et si L est sans repetition % alors la liste de tete X et de reste L est sans repetition sans_repetition([X|L]):-non_appartient(X,L),sans_repetition(L). % ============================================================ % LES PREDICATS SUIVANTS SONT EN FAIT DES FONCTIONS, % C'EST A DIRE QUE LORSQUE TOUS LES ELEMENTS SONT FIXES SAUF % LE DERNIER IL N'Y A QU'UNE SEULE VALEUR % DU DERNIER ARGUMENT QUI RENDE LE PREDICAT VRAI. % ============================================================ % LE PREDICAT ajout_tete(X,L1,L2) % QUI EST VRAI LORSQUE L2 EST LA LISTE OBTENUE A PARTIR % DE L1 PAR AJOUT DE X EN TETE DE L1 % la liste [X|L] est le resultat de l'ajout % de X en tete de L ajout_tete(X,L,[X|L]). % ============================================================ % LE PREDICAT ajout_fin(X,L1,L2) % QUI EST VRAI LORSQUE L2 % EST LA LISTE OBTENUE A PARTIR DE L1 % PAR AJOUT DE X EN QUEUE DE L1 % la liste [X] est la liste obtenue par ajout de X % en queue de la liste vide ajout_fin(X,[],[X]). % si l'ajout de X en queue de L1 donne la liste L3 % et si l'ajout en tete de Y a L3 donne L2 % alors L2 est la liste obtenue par ajout en queue de X % a la liste commencant par Y et de reste L1 ajout_fin(X,[Y|L1],L2):-ajout_tete(Y,L3,L2), ajout_fin(X,L1,L3). % la clause precedent aurait pu etre ecrite: % ajout_fin(X,[Y|L1],[Y|L2]):- ajout_fin(X,L1,L2). % ============================================================ % LE PREDICAT supprimer(X,L1,L2) % QUI EST VRAI LORSQUE L2 EST LA LISTE OBTENUE % PAR SUPPRESSION DE LA PREMIERE OCCURRENCE DE X % DANS L1 OU LORSQUE X NE FIGURE PAS DANS L1 ET QUE L2=L1 % la suppression de la premiere occurrence de X dans la liste vide % est la liste vide. supprimer(X,[],[]). % la suppression de la premiere occurrence de X % dans une liste commencant par X et de reste L1 % est L1 supprimer(X,[X|L1],L1). % si X est different de Y % et si L3 est la liste obtenue en supprimant la premiere occurrence de X dans L1 % et si L2 est la liste obtenue par ajout en tete de Y a L1 % alors L2 est la liste obtenue par suppression de la premiere occurrence de X % dans la liste commencant par Y et de reste L1 supprimer(X,[Y|L1],L2):-X\==Y , ajout_tete(Y,L3,L2), supprimer(X,L1,L3). % ============================================================ % LE PREDICAT supprimer_fin(X,L) % QUI EST VRAI LORSQUE L EST LA LISTE L PRIVE DE SON DERNIER ELEMENT SI L EST NON VIDE % OU LORSQUE L EST VIDE % la liste vide est la liste obtenue par suppression % du dernier element dans la liste vide supprimer_fin([],[]). % si L1 est la liste obtenue par ajout de Y en tete de L2 % et si L2 est la liste obtenue en supprimant le dernier element de L % alors L1 est la liste commencant par Y et de reste L % privee de son dernier element supprimer_fin([Y|L],L1):- supprimer_fin(L,L2),ajout_tete(Y,L2,L1). % ============================================================ % LE PREDICAT fusion(L1,L2,L3) % QUI EST VRAI LORSQUE L3 EST OBTENUE A PARTIR DE L1 ET L2 % EN PRENANT UN ELEMENT ALTERNATIVEMENT DANS L1 ET L2, % ET EN ADJOIGNANT EN QUEUE LES ELEMENTS NON UTILISES D'UNE DES DEUX LISTES, % S'IL EN RESTE (C.-A-D. LORSQUE LES DEUX LISTES NE SONT PAS DE MEME LONGUEUR) % lorsque la seconde liste est vide, % la liste fusion est la premiere liste. fusion(L1,[],L1). % lorsque la premiere liste est vide % la liste fusion est la seconde liste. fusion([],L2,L2). % si la fusion de L1 et L2 donne L5 % et si L4 est la liste de tete Y et de reste L5 % et si L3 est la liste de tete X et de reste L4 % alors L3 est la liste obtenue par fusion de L1 et L2 fusion([X|L1],[Y|L2],L3):-ajout_tete(X,L4,L3),ajout_tete(Y,L5,L4), fusion(L1,L2,L5). % ============================================================ % LE PREDICAT concatener(L1,L2,L3) % QUI EST VRAI LORSQUE L3 EST LA LISTE DONT LES ELEMENTS SONT D'ABORD % CEUX DE L1 PUIS CEUX DE L2 % la concatenation de la liste vide et de la liste L2 % est la liste L2 concatener([],L2,L2). % si L4 est la concatenation de l1 avec L2, % et si L3 est la liste de tete X et de reste L4 % alors L3 est la concatenation de la liste de tete X et de reste L1 avec L2 concatener([X|L1],L2,L3):-ajout_tete(X,L4,L3),concatener(L1,L2,L4). % on aurait pu ecire cette clause ainsi: % concatener([X|L1],L2,[X|L3]):- concatener(L1,L2,L3). % ============================================================ % LE PREDICAT inverser(L1,L2) % QUI EST VRAI LORSQUE L2 EST CONSTITUEE DES MEMES ELEMENTS % QUE L1 MAIS DANS L'ORDRE INVERSE. % la liste inverse de la liste vide est la liste vide. inverser([],[]). % si la liste inverse de la liste L1 est la liste L3 % et si L2 est la liste obtenue par ajout de X en queue de L3 % alors L2 est la liste inverse de la liste de tete X et de reste L1 inverser([X|L1],L2):-inverser(L1,L3),ajout_fin(X,L3,L2). % ============================================================ % LE PREDICAT reunion(L1,L2,L3) % QUI EST VRAI LORSQUE L1 ET L2 SONT SANS REPETITION % ET QUE L3 EST LA LISTE OBTENUE COMME SUIT: % L3 CONTIENT LES ELEMENTS QUI FIGURENT DANS L1 OU DANS L2 % DANS L'ORDRE DE LEUR DERNIERE APPARITION DANS (L1 SUIVIE DE L2) % --- UN ELEMENT COMMUN A L1 ET L2 NE FIGURE QU'UNE SEULE FOIS DANS L3 % Question: pourquoi l'ordre des elements dans L3 % est-il celui que je donne? % La reunion de la liste vide et de L2 est L2 % --- qu'on suppose sans repetition reunion([],L2,L2). % si X figure dans L2 % et si la reunion de L1 et L2 est L4 % alors L4 est la reunion de la liste de tete X et de reste L1 avec la liste L2 reunion([X|L1],L2,L4):-appartient(X,L2),reunion(L1,L2,L4). % si X ne figure pas dans L2 % et si la reunion de L1 avec L2 est L4 % et si L3 est obtenue par ajout de X en tete de L4 % alors la reunion de la liste de tete X et de reste L1 avec la liste L2 % est la liste L3 % --- par hypothese, qui est preservee au cours des appels successifs, % X ne figure pas dans L1: c'est pour cela qu'on obtient une liste sans repetition, % meme s'il y a des elements communs. reunion([X|L1],L2,L3):-non_appartient(X,L2), ajout_tete(X,L4,L3),reunion(L1,L2,L4). % on pourrait ajouter les clauses symetriques suivantes, % qui sont vraies, mais non necessaires: % avec les precedentes on finit toujours par arriver au cas reunion([],L2,L2). % Question: l'ajout de ces clauses conduit a plus de solutions, % comment expliquez-vous cela ? % reunion(L1,[],L1). % reunion(L1,[Y|L2],L4):-appartient(Y,L1),reunion(L1,L2,L4). % reunion(L1,[Y|L2],L3):-non_appartient(Y,L1) ajout_tete(Y,L4,L3),reunion(L1,L2,L4). % ============================================================ % LE PREDICAT commun(L1,L2,L3) % QUI EST VRAI LORQUE L3 EST UNE LISTE SANS REPETITION % DES ELEMENTS COMMUNS A L1 ET L2 % LORSQUE CELLES-CI SONT SANS REPETITION. % L'ORDRE DES ELEMENTS DANS L3 EST L'ORDRE DE LEUR PREMIERE APPARITION % DANS L1 SUIVIE DE L2. % si la premier liste est vide, % l'intersection est la liste vide. commun([],L2,[]). % si X appartient a L2 % et si l'intersection de L1 et L2 est L4 % et si L3 est la liste obtenue par ajout de X en tete de L4 % alors l'intersection de la liste de tete X et de reste L1 avec la liste L2 % est la liste L3 commun([X|L1],L2,L3):- appartient(X,L2),commun(L1,L2,L4),ajout_tete(X,L4,L3). % si X n'appartient a L2 % et si l'intersection de L1 et L2 est L3 % alors l'intersection de la liste de tete X et de reste L1 avec la liste L2 % est aussi la liste L3 commun([X|L1],L2,L3):- non_appartient(X,L2),commun(L1,L2,L3). % comme precedemment on pourrait rajouter les clauses symetriques % si X appartient a L2 % et si l'intersection de L1 et L2 est L4 % et si L3 est laiste obtenue par ajout de X en tete de L4 % alors l'intersection de la liste de tete X et de reste L1 avec la liste L2 % commun(L1,[],[]). % commun(L1,[Y|L2],L3):-appartient(Y,L1),commun(L1,L2,L4),ajout_tete(Y,L4,L3). % commun(L1,[Y|L2],L3):- non_appartient(Y,L1),commun(L1,L2,L3). % ============================================================ % LE PREDICAT ens(L1,L2) % QUI EST VRAI LORSQUE L2 % EST OBTENUE A PARTIR DE L1 % PAR SUPPRESSION DE TOUTES LES OCCURRENCES D'UN ELEMENT SAUF LA DERNIERE: % L2 EST TOUJOURS SANS REPETITION ET CONTIENT LES MEMES ELEMENTS % la liste vide est la reduite de la liste vide ens([],[]). % si X appartient a L1 % et que L2 est la reduite de L1 % alors L2 est la reduite de la liste de tete X et de reste L2 ens([X|L1],L2):-appartient(X,L1),ens(L1,L2). % si X n'appartient pas a L1 % et que L3 est la reduite de L1 % et que L2 est la liste de tete X et de reste L3 % alors L2 est la reduite de la liste de tete X et de reste L1 ens([X|L1],L2):-non_appartient(X,L1),ens(L1,L3),ajout_tete(X,L3,L2). % =========================================================================== % LE PREDICAT reunionbis(L1,L2,L3) % QUI EST VRAI LORSQUE L3 EST LA LISTE OBTENUE COMME SUIT: % L3 CONTIENT LES ELEMENTS QUI FIGURENT DANS L1 OU DANS L2 % DANS L'ORDRE DE LEUR DERNIERE APPARITION DANS (L1 SUIVIE DE L2) % --- UN ELEMENT COMMUN A L1 ET L2 NE FIGURE QU'UNE SEULE FOIS DANS L3 % CE PREDICAT NE RECQUIERT PAS QUE L1 ET L2 SOIENT SANS REPETITION % si L1ens est la liste reduite de L1, % et si L2ens est la liste reduite de L2 % et si L3 est la reunion de L1ens et de L2ens (qui sont sans repetition) % alors L3 est la reunion de L1 et L2 (qui peuvent comporter des repetition) % et L3 est sans repetition. reunionbis(L1,L2,L3):-ens(L1,L1ens), ens(L2,L2ens), reunion(L1ens,L2ens,L3). % on definit similairement un predicat communbis, % variante de commun % qui fonctionne pour des listes avec repetition % mais donne une liste sans repetition communbis(L1,L2,L3):-ens(L1,L1ens), ens(L2,L2ens), commun(L1ens,L2ens,L3).