list - examples - ¿Más determinismo para `memberd/2`?

prolog examples

Question

Muchos sistemas proporcionan una implementación pura y eficiente de member/2 . En particular, no queda ningún punto de elección abierto para:

?- member(b,[a,b]).
true.

mientras que, una implementación ingenua de member/2 produce más bien:

?- member(b,[a,b]).
true ;
false.

Lo que ciertamente es correcto desde un punto de vista declarativo, pero menos eficiente.

Por otro lado, hay algunos problemas técnicos con el member/2 . Permite soluciones redundantes, como en:

?- member(a,[a,a]).
true ;
true.

memberd/2 resuelve este problema usando if_/3 y (=)/3 .

memberd(E, [X|Xs]) :-
   if_(E = X, true, memberd(E, Xs)).

?- memberd(a,[a,a]).
true.

Desafortunadamente, esta definición deja abiertos los puntos de elección - produciendo ; false ; false ("puntos de elección de sobra") en situaciones donde el miembro no:

?- memberd(X,[a,b]).
X = a ;
X = b ;
false.    % BAD - to be avoided!

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

Entonces, mi pregunta: ¿Existe una definición de memberd/2 que evite el punto de elección como este arriba?

Answer 1

En esta respuesta comparamos tres predicados de lista de miembros diferentes:

• member/2 , un predicado incorporado, como se implementó en SWI-Prolog.

• memberd/2 , como lo define el OP:

  memberd(E,[X|Xs]) :-
     if_(E=X, true, memberd(E,Xs)).

• memberd_new/2 , una alternativa propuesta que se define así:

  memberd_new(E,[X|Xs]) :-
     (  Xs /= [_|_]
     -> E=X
     ;  if_(E=X, true, memberd_new(E,Xs))
     ).

¡Vamonos!

Primero, algunas consultas de terreno:

?- member(b,[a,b]).
true.
?- memberd(b,[a,b]).
true.
?- memberd_new(b,[a,b]).
true.

?- member(a,[a,a]).
true ; true.                        % BAD
?- memberd(a,[a,a]).
true.
?- memberd_new(a,[a,a]).
true.

?- member(a,[a,b]).
true ; false.                       % BAD 
?- memberd(a,[a,b]).
true.
?- memberd_new(a,[a,b]).
true.

A continuación, algunas consultas que tienen múltiples soluciones distintas:

?- member(X,[a,b]).
X = a ; X = b.
?- memberd(X,[a,b]).
X = a ; X = b ; false.              % BAD
?- memberd_new(X,[a,b]).
X = a ; X = b.

A continuación, se sugiere un caso de prueba en un comentario a una respuesta anterior que rompió la versión de memberd_new/2 presentada anteriormente.

?- member(a,[a|nonlist]).
true.
?- memberd(a,[a|nonlist]).
true.
?- memberd_new(a,[a|nonlist]).
true.                               % IMPROVED

Una variación del caso de prueba anterior:

?- member(X,[a|nonlist]).
X = a.
?- memberd(X,[a|nonlist]).
X = a ; false.                      % BAD
?- memberd_new(X,[a|nonlist]).
X = a.                              % IMPROVED

Por último, algunas consultas no terminantes:

?- member(1,Xs).
  Xs =          [1|_A]
; Xs =       [_A,1|_B]
; Xs =    [_A,_B,1|_C]
; Xs = [_A,_B,_C,1|_D]
...

?- memberd(1,Xs).
  Xs =          [1|_A]
; Xs =       [_A,1|_B], dif(_A,1)
; Xs =    [_A,_B,1|_C], dif(_A,1), dif(_B,1)
; Xs = [_A,_B,_C,1|_D], dif(_A,1), dif(_B,1), dif(_C,1) 
...

?- memberd_new(1,Xs).
  Xs =          [1|_A]
; Xs =       [_A,1|_B], dif(_A,1)
; Xs =    [_A,_B,1|_C], dif(_A,1), dif(_B,1)
; Xs = [_A,_B,_C,1|_D], dif(_A,1), dif(_B,1), dif(_C,1)
...

Answer 2

Hay más ... Supongamos que implementamos memberD/2 basado en memberd_t/3 :

memberD(X,Xs) :- memberd_t(X,Xs,true).

¿Cómo se compara eso con memberd/2 , como lo define el OP en la pregunta?

Vamos a volver a ejecutar algunas consultas!

?- memberd(a,[a,a]), memberd(a,[a,b]), memberd(b,[a,b]), 
   memberD(a,[a,a]), memberD(a,[a,b]), memberD(b,[a,b]).
true.                             % all of these succeed deterministiaclly

?- memberd(X,[a,b]).
X = a ; X = b ; false.            % could be better
?- memberD(X,[a,b]).
X = a ; X = b ; false.            % could be better

?- memberd(a,[a|nonlist]), memberD(a,[a|nonlist]).
true.                             % both succeed deterministically

?- memberd(X,[a|nonlist]).
X = a ; false.                    % could be better
?- memberD(X,[a|nonlist]).
X = a ; false.                    % could be better

En las consultas anteriores, memberd/2 y memberD/2 dan las mismas respuestas y dejan atrás puntos de elección superfluos en los mismos casos.

Vamos a profundizar un poco más! Considere las siguientes consultas usando memberd_t/3 con casos de esquina:

?- memberd_t(a,[a|nonlist],T). T = true. % OK ?- memberd_t(b,[a|nonlist],T). false. % missing: `T = false` ?- memberd_t(X,[a|nonlist],T). T = true, X = a ; false. % missing: `T = false, dif(X,a)`

Esto no es exactamente lo que esperaba / quería obtener. ¿Qué podemos hacer? Básicamente, veo dos opciones:

1. Acepte esta discrepancia y proclame: "Estas consultas son casos de esquina sin importancia".

2. Cree una implementación de memberd_t/3 que pueda manejar estos casos.

Ambas opciones tienen fortalezas y debilidades. A continuación, implementamos memberd_new_t/3 que maneja los casos de esquina y reduce la creación de puntos de elección superfluos.

Advertencia: ¡código feo por delante!

memberd_new_t(E,Xs0,Truth) :-
   (  Xs0 /= [_|_]
   -> Truth = false
   ;  Truth = false,
      freeze(Xs0, Xs0/=[_|_])
   ;  Xs0 = [X|Xs],
      (  Xs /= [_|_]
      -> =(E,X,Truth)
      ;  if_(E=X,Truth=true,memberd_new_t(E,Xs,Truth))
      )
   ).

¡Verifiquemos si producimos menos puntos de elección inútiles con memberd_new_t/3 !

?- memberd_t(X,[a,b],true). X = a ; X = b ; false. % suboptimal ?- memberd_new_t(X,[a,b],true). X = a ; X = b. % BETTER ?- memberd_t(X,[a|nonlist],true). X = a ; false. % suboptimal ?- memberd_new_t(X,[a|nonlist],true). X = a. % BETTER

¡Bien! Entonces, ¿qué pasa con los casos de esquina arriba?

?- memberd_t(a,[a|nonlist],T).
T = true.                           % OK
?- memberd_new_t(a,[a|nonlist],T).
T = true.                           % OK

?- memberd_t(b,[a|nonlist],T).
false.                              % BAD
?- memberd_new_t(b,[a|nonlist],T).
T = false.                          % OK

?- memberd_t(X,[a|nonlist],T).
  T = true, X = a 
; false.                            % BAD
?- memberd_new_t(X,[a|nonlist],T).
  T =  true,     X=a
; T = false, dif(X,a).              % OK

¡Funciona! Por fin, considere las consultas más generales:

?- memberd_t(X,Xs,T).          
  T=false, Xs = []            
; T=true , Xs = [X       |_A]        
; T=false, Xs = [_A         ], dif(X,_A)
; T=true , Xs = [_A, X   |_B], dif(X,_A)
; T=false, Xs = [_A,_B      ], dif(X,_A), dif(X,_B)
; T=true , Xs = [_A,_B, X|_C], dif(X,_A), dif(X,_B)
; T=false, Xs = [_A,_B,_C   ], dif(X,_A), dif(X,_B), dif(X,_C)
...

?- memberd_new_t(X,Xs,T).
  T=false, freeze(Xs,Xs/=[_|_])
; T=true ,                       Xs = [ X      |_A]
; T=false, freeze(_B,_B/=[_|_]), Xs = [_A      |_B], dif(X,_A)
; T=true ,                       Xs = [_A, X   |_B], dif(X,_A)
; T=false, freeze(_C,_C/=[_|_]), Xs = [_A,_B   |_C], dif(X,_A), dif(X,_B)
; T=true ,                       Xs = [_A,_B, X|_C], dif(X,_A), dif(X,_B)
; T=false, freeze(_D,_D/=[_|_]), Xs = [_A,_B,_C|_D], dif(X,_A), dif(X,_B), dif(X,_C)
...       

Para estos casos de esquina, memberd_new_t/3 es más como memberd/3 que memberd_t/3 :

?- memberd(X,Xs).
  Xs = [ X            |_A]
; Xs = [_A, X         |_B], dif(X,_A)
; Xs = [_A,_B, X      |_C], dif(X,_A), dif(X,_B)
; Xs = [_A,_B,_C, X   |_D], dif(X,_A), dif(X,_B), dif(X,_C)
; Xs = [_A,_B,_C,_D, X|_E], dif(X,_A), dif(X,_B), dif(X,_C), dif(X,_D)
...

Answer 3

Primero, cambiamos el nombre de memberd a memberd_old por claridad.

Luego, implementamos memberd_new/2 , que utiliza el rezago y la indexación del primer argumento para evitar la creación del punto de elección inútil al final de la lista.

memberd_new(E,[X|Xs]) :-
   memberd_new_aux(Xs,X,E).

% auxiliary predicate to enable first argument indexing
memberd_new_aux([],E,E).
memberd_new_aux([X1|Xs],X0,E) :-
   if_(E=X0, true, memberd_new_aux(Xs,X1,E)).

Comparemos member/2 (SWI-Prolog builtin predicate), memberd_old/2 y memberd_new/2 !

Primero, una consulta de terreno:

?- member(a,[a,a]).
true ;
true.                       % BAD!

?- memberd_old(a,[a,a]).
true.

?- memberd_new(a,[a,a]).
true.

A continuación, otra consulta de terreno:

?- member(a,[a,b]).
true ;                      % BAD!
false.

?- memberd_old(a,[a,b]).
true.

?- memberd_new(a,[a,b]).
true.

Ahora, una consulta que tiene múltiples soluciones distintas:

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

?- memberd_old(X,[a,b]).
X = a ;
X = b ;                     % BAD!
false.

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

Editar

La implementación de memberd_new/2 presentada aquí está en desuso.

Recomiendo usar la implementación más nueva que se muestra en esta respuesta .