Implementar el predicado miembro como un solo trazador

Question

Implementar el predicado miembro como un solo trazador

Pregunta de entrevista!

Así es como normalmente se 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.

Defínelo usando solo una regla.

27

list prolog dcg

Author: Mateusz Piotrowski, 2009-11-16

Source

3 answers

Dado que no especificaste qué otros predicados se nos permite usar, voy a intentar hacer trampa un poco. :P

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

20

Author: bcat,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2009-11-17 00:11:51

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

5

Author: false,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-07-31 12:17:09

score 36 · Accepted Answer

Solución:

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

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.

Cómo funciona:
- que Estamos buscando una ocurrencia del primer argumento, X, en el segundo argumento, [Y|T].
- Se asume 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 encontrado X en la lista. De lo contrario (;) probamos si X está en la cola.
Observaciones:
- Gracias a humble coffee por señalar que usar = (unificación) produce un código más flexible que usar == (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 utilizar para "enumerar" todas las listas que contienen una elemento:
```
?- 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 member(X, [a]) y causaría un desbordamiento de pila en member(a, X) (probado con SWI-Prolog versión 5.6.57).