Permutations d'une liste en Prolog

Le problème exposé dans ce sujet a été résolu.

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.

+0 -0

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.
+1 -0

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 :)

+0 -0

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).

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

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