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 .