Prolog - membre prédicatif one-liner

Question

Question d'interview!

Voici comment vous définissez normalement la relation member en Prolog:

member(X, [X|_]).  % member(X, [Head|Tail]) is true if X = Head 
         % that is, if X is the head of the list 
member(X, [_|Tail]) :- % or if X is a member of Tail, 
    member(X, Tail).  % ie. if member(X, Tail) is true. 

définir en utilisant une seule règle.

Answer 1

1. Solution:

   member(X, [Y|T]) :- X = Y; member(X, T). 
   

2. Démonstration:

   ?- member(a, []). 
   fail. 
   ?- member(a, [a]). 
   true ; 
   fail. 
   ?- member(a, [b]). 
   fail. 
   ?- member(a, [1, 2, 3, a, 5, 6, a]). 
   true ; 
   true ; 
   fail. 
   

3. Comment ça marche:

   • Nous sommes à la recherche d'une occurrence du premier argument, X, dans le s argument econd, [Y|T].
   • Le second argument est supposé être une liste. Y correspond à sa tête, T correspond à la queue.
   • Par conséquent, le prédicat échoue pour la liste vide (comme il se doit).
   • Si X = Y (c'est-à-dire X peut être unifié avec Y) alors nous avons trouvé X dans la liste. Sinon (;) nous testons si X est dans la queue.

4. Remarques:

   • Grâce à humble coffee de remarquer que l'utilisation = (unification) donne un code plus souple que l'utilisation == (test pour l'égalité).

   • Ce code peut également être utilisé pour énumérer les éléments d'une liste donnée:

     ?- member(X, [a, b]). 
     X = a ; 
     X = b ; 
     fail. 
     

   • Et il peut être utilisé pour « énumérer » toutes les listes qui contiennent un élément donné:

     ?- member(a, X). 
     X = [a|_G246] ; 
     X = [_G245, a|_G249] ; 
     X = [_G245, _G248, a|_G252] ; 
     ... 
     

   • Remplacer = par == dans le code ci-dessus le rend beaucoup moins flexible: il échouerait immédiatement sur member(X, [a]) et provoquerait un débordement de pile sur member(a, X) (testé avec SWI-Prolog version 5.6.57) .

Answer 2

Puisque vous ne spécifiez pas ce que d'autres prédicats nous sommes autorisés à utiliser, je vais essayer de tricher un peu.:P

member(X, L) :- append(_, [X|_], L). 

Answer 3

newmember(X, Xs) :- 
    phrase((..., [X]),Xs, _). 

Avec

... --> [] | [_], ... . 

En fait, la définition suivante assure également que Xs une liste:

member_oflist(X, Xs) :- 
    phrase((..., [X], ...), Xs).