Prolog - predicado miembro one-liner

Question

Pregunta de entrevista!

Ésta es la forma en que normalmente define la relación 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. 

definirla usando sólo una regla.

Answer 1

1. Solución:

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

2. Demostración:

   ?- 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. Cómo funciona:

   • Buscamos una ocurrencia del primer argumento, X, en el el segundo argumento, [Y|T].
   • Se supone que el segundo argumento es una lista. Y coincide con su cabeza, T coincide con la cola.
   • Como resultado, el predicado falla para la lista vacía (como debería).
   • Si X = Y (es decir, X se puede unificar con Y), entonces encontramos X en la lista. De lo contrario (;) probamos si X está en la cola.

4. Observaciones:

   • , gracias a humble coffee para señalar que el uso de = (unificación) produce código más flexible que el uso de == (prueba para la igualdad).

   • Este código también se puede utilizar para enumerar los elementos de una lista dada:

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

   • Y puede ser utilizado para "enumerar" todas las listas que contienen un elemento dado:

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

   • Reemplazando = por == en el código anterior lo hace mucho menos flexible: fallaría inmediatamente en member(X, [a]) y causaría un desbordamiento de pila en member(a, X) (probado con SWI-Prolog versión 5.6.57) .

Answer 2

Dado que no especificó qué otros predicados se nos permite utilizar, voy a tratar de engañar un poco.:P

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

Answer 3

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

Con

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

En realidad, la siguiente definición también asegura que Xs es una lista:

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