Permutations d'une liste en Prolog

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Salut,

Je suis en train de jeter un coup d’œil aux langages de programmation logique. J'ai découvert le langage Curry, qui est en (très) gros une version logique de Haskell. Sur les exemples de la page Wikipedia de Curry, celui ci a attiré mon attention:

1
2
3
4
5
insert x ys     = x : ys
insert x (y:ys) = y : insert x ys

perms [] = []
perms (x:xs) = insert x (perms xs)

Il calcule toutes les permutations d'une liste donnée, mais pour définir cette fonction j'ai besoin de la fonction insert. La fonction insert permet d'insérer un élément à toutes les positions de la liste à la fois. En voyant le manque de documentation et de communauté Curry, j'ai décidé d'apprendre Prolog à la place. Du coup j'ai essayé d'implementer la même fonction insert en Prolog. Voici ce que j'ai essayé:

1
2
3
4
insert(X, YS, ZS) :- ZS = [ X | YS ].
insert(X, [Y | YS], ZS) :-
    insert(X, YS, ZS),
    [Y | ZS].

Cependant lorsque j'exécute, avec SWI-Prolog, j'obtiens une erreur (en plus d'obtenir un mauvais résultat):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
?- insert(0, [1,2,3], XS).
XS = [0, 1, 2, 3] ;
ERROR: is_absolute_file_name/1: Type error: `text' expected, found `1'
ERROR: is_absolute_file_name/1: Type error: `text' expected, found `0'
ERROR: is_absolute_file_name/1: Type error: `text' expected, found `2'
ERROR: is_absolute_file_name/1: Type error: `text' expected, found `3'
XS = [0, 2, 3] ;
ERROR: is_absolute_file_name/1: Type error: `text' expected, found `2'
ERROR: is_absolute_file_name/1: Type error: `text' expected, found `0'
ERROR: is_absolute_file_name/1: Type error: `text' expected, found `3'
ERROR: is_absolute_file_name/1: Type error: `text' expected, found `1'
ERROR: is_absolute_file_name/1: Type error: `text' expected, found `0'
ERROR: is_absolute_file_name/1: Type error: `text' expected, found `3'
XS = [0, 3] ;
ERROR: is_absolute_file_name/1: Type error: `text' expected, found `3'
ERROR: is_absolute_file_name/1: Type error: `text' expected, found `0'
ERROR: is_absolute_file_name/1: Type error: `text' expected, found `2'
ERROR: is_absolute_file_name/1: Type error: `text' expected, found `0'
ERROR: is_absolute_file_name/1: Type error: `text' expected, found `1'
ERROR: is_absolute_file_name/1: Type error: `text' expected, found `0'
XS = [0] ;
false.

Je sais pas trop ce qu'essaye de me dire l'interpréteur, apparemment j'ai une erreur de types parce que je fournis un nombre au lieu d'un text.

Si quelqu'un pourrait m'éclairer ça serait sympa,

AZ.

Édité par felko

Anciennement AlphaZeta

+0 -0

Cette réponse a aidé l'auteur du sujet

En ce qui concerne le code quelques remarques :

  • Dans ta deuxième règle, la dernière clause [Y | ZS] ne veut rien dire (je suspecte que prolog le prend pour un consult et que c'est ce qui provoque ton erreur) ; je préfère te laisser chercher comment faire correctement ce que tu veux.
  • Ta première clause peut être réécrite comme suit : insert(X, YS, [X | YS])., c'est plus idiomatique.

Édité par yoch

+1 -0
Auteur du sujet

Ah oui merci, j'ai encore un peu de mal x)

Voici le code du coup (fonctionnel):

1
2
3
4
insert(Element, List, [Element | List]).
insert(Element, [First | Rest], Result) :-
    insert(Element, Rest, Inserted),
    Result = [First | Inserted].

Du coup voici mon code pour les permutations:

1
2
3
4
perms([], []).
perms([First | Rest], Result) :-
    perms(Rest, Perms),
    insert(First, Perms, Result).

Ça marche, merci beaucoup.

Je passe en résolu :)

Anciennement AlphaZeta

+0 -0

Cette réponse a aidé l'auteur du sujet

C'est parfait !

Encore une fois, ton code pourrait être réécrit de façon plus idiomatique :

1
2
3
insert(Element, List, [Element | List]).
insert(Element, [First | Rest], [First | Inserted]) :-
    insert(Element, Rest, Inserted).

Et juste pour info, tes deux prédicats existent déjà en standard, il s'agit de select/3 et permutation/2 (tu peux consulter les sources dans les liens).

Édité par yoch

+0 -0

Cette réponse a aidé l'auteur du sujet

Il y a bien sur des cas ou c'est utile, par exemple pour tester si deux variables unifient, ou dans le cadre d'expressions plus complexes, ou autre. Mais en tout cas, on peut bien souvent s'en passer.

+1 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte