Discussion :

[JB122]

Bonjour, je débute en prolog et je galère à comprendre le déroulement de fonctions récursive sur les listes. Le problème c'est que j'ai lu de nombreux cours sur le net mais que je n'en trouve aucun qui explique en détail comment cela marche.

Voici le code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
appartient(X,Liste) : X appartient à Liste
appartient(X,[X|_N]).  //ligne 1
appartient(X,[_Z|N]):- appartient(X,N).  //ligne 2

Quelqu'un pourrait m'expliquer en détail ce qu'il se passe dans ce programme et comment fonctionne ces deux lignes. Voici ce que je pnse avoir compris.

La ligne 1 est la condition d'arret. Lorsque X est le premier élément de la liste, on considère qu'il appartient à la liste ça va retourner true , si cela n'arrive jamais ça va retourner false. J'ai bon ? (Question 1)

Si je pose la question appartient (c,[a,b,c,d]).
Le programme va chercher
* Ligne 1 Appartient (c, [c|a, b, c, d] ). C n'est pas le premier élément de la liste donc il va passer à la ligne 2. J'ai bien compris ? (Question 2)

Ensuite on arrive à ligne 2, je suis perdu, je prends la queue de la regle et fais appartient (X, N). à quoi correspond N (Question 3) N= a, b, c, d ?
et dans ce cas que veut dire appartient(X,[_Z|N]): (Question 4).

Est ce que je pose les questions dans le bon ordre? Merci pour vos réponses.

[Trap D]

Attention, en Prolog il n'y a pas de fonction, mais des prédicats qui réussissent ("retour" true) ou échouent ("retour" false).

Pour comprendre le code, il faut se rappeller que [a,b,c,d] est équivalanet à [a|[b,c,d]], si tu as fait du Lisp c'est l'équivalent du car et cdr d'une liste
En Prolog on a
Liste --> []
Liste --> [a | Liste]

Donc [a] = [a|[]].

Pour le déroulement de appartient(c, [a,b,c,d]) :

appartient(c, [a,b,c,d])
La règle 1 échoue car c n'est pas égal à a

On applique donc la règle 2
appartient(c, [a|[b,c,d]]) :- appartient(c, [b,c,d]).

Maintenant
appartient(c, [b,c,d]).
La règle 1 échoue car c n'est pas égal à b

On applique donc la règle 2
appartient(c, [b|[c,d]]) :- appartient(c, [c,d]).

Nouvel essai
appartient(c, [c,d]).
La règle 1 réussit, donc en remontant, les règle 2 réussissent.

[JB122]

Désolé pour la réponse tardive, mais un grand merci.
Je crois que je commence à comprendre.