list - Implementar el predicado de miembro como una sola línea

prolog dcg

Question

Pregunta de la entrevista!

Así es como normalmente se define la relación de 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.

Defínelo usando una sola 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:

   • Estamos buscando una aparición del primer argumento, X , en 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 ( ; ) comprobamos si X está en la cola.

4. Observaciones:

   • Gracias al humilde café por señalar que el uso de = (unificación) produce un código más flexible que el uso de == (pruebas de igualdad).

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

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

   • Y se puede usar 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] ;
     ...

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

Answer 2

Ya que no especificaste qué otros predicados podemos usar, voy a intentar hacer un poco de trampa. :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).