Prólogo: primer valor duplicado

Question

Necesito encontrar el primer valor duplicado en una lista.

prep(3,[1,3,5,3,5]). Debe ser verdad.

prep(5,[1,3,5,3,5]). Debe ser falso.

Pensé en verificar la igualdad con el valor actual y los miembros de la lista anterior hasta que encuentre un duplicado; si encuentra uno, probará la igualdad con X pero no tengo idea de cómo hacerlo en Prolog.

¡Agradezco cualquier ayuda! Gracias

Answer 1

No estoy seguro si esto es tarea/hay restricciones sobre qué predicados se le permite usar, pero esto obtiene prolog para hacer la recursión para usted.

Dice ... encontrar todos los duplicados, es decir. donde hay un elemento con el índice de lista I1 y otro con I2, de modo que ambos tienen el mismo valor N, y los índices no son los mismos, es decir, no consideran el mismo elemento de lista como un duplicado.

Estos duplicados se ponen (en el orden en que se encuentran, desde el principio crucialmente) en la lista AllDups, y el predicado es verdadero si el primer duplicado encontrado se unifica con M, el valor que está comprobando.

primer intento: Esto funciona, pero es muy ineficiente, la construcción de una lista de todos los duplicados

prep(M, List) :- 
    findall(N, 
     (nth0(I1, List, N), 
     nth0(I2, List, N), 
     not(I1 =:= I2)), 
     AllDups), 
    nth1(1, AllDups, M). 


?- prep(3,[1,3,5,3,5]). 
true. 

?- prep(5,[1,3,5,3,5]). 
false. 

Incluso si usted no está autorizado a utilizar findall, podría ayudarle a resolver cómo hacerlo ' a mano'.

segundo intento: Esto no funciona/retrocede demasiado produciendo un falso positivo

Incluso puede hacerlo sin la findall - nth0 utilizar para encontrar el primer elemento duplicado, a continuación, si es que se unifica con el valor que está comprobando, devuelve verdadero, de lo contrario es falso.

prep(N, List) :- 
     nth0(I1, List, N), 
     nth0(I2, List, N), 
     not(I1 =:= I2). 

tercer intento: Esto funciona, y devuelve tan pronto como el primer duplicado se ha encontrado

prep(M, List) :- 
     nth0(I1, List, N), 
     nth0(I2, List, N), 
     not(I1 =:= I2), !, 
     M == N. 

Answer 2

representante (N, Lista): - append (L1, [N | _] , Lista), anexar (_, [N | _], L1), \ + (rep (_, L1)).

Answer 3

Aquí hay una versión pura que usa dif/2 que implementa la desigualdad del sonido. dif/2 es ofrecido por B-Prolog, YAP-Prolog, SICStus-Prolog y SWI-Prolog.

 
firstdup(E, [E|L]) :- 
    member(E, L). 
firstdup(E, [N|L]) :- 
    non_member(N, L), 
    firstdup(E, L). 

member(E, [E|_L]). 
member(E, [_X|L]) :- 
    member(E, L). 

non_member(_E, []). 
non_member(E, [F|Fs]) :- 
    dif(E, F), 
    non_member(E, Fs). 

Las ventajas son que puede también ser utilizado con más consultas generales:

 
?- firstdup(E, [A,B,C]). 
E = A, A = B ; 
E = A, A = C ; 
E = C, 
B = C, 
dif(A, C) ; 
false. 

Aquí, obtenemos tres respuestas: A es el duplicado en las dos primeras respuestas, pero por dos motivos diferentes : A puede ser igual a B o C. En la tercera respuesta, B es el duplicado, pero solo será un duplicado si C es diferente a A.

Para entender la definición, lea :- como una flecha ← Entonces, lo que está en el lado derecho es lo que usted sabe ya la izquierda es lo que concluye. A menudo es un poco irritante leer predicados en esa dirección, después de todo, es posible que sienta la tentación de seguir "el hilo de la ejecución". Pero a menudo este hilo lleva a ninguna parte – se vuelve demasiado complejo de entender.

La primera regla dice lo siguiente:

Siempre E es un elemento de la lista L llegamos a la conclusión de que tiene [E|L] E como primer duplicado.

La segunda regla dice lo siguiente:

disponibles E es el primer duplicado de L (no se asuste aquí y decimos que no sabemos que ...) y siempre que N no es un elemento de L llegamos a la conclusión de que [N|L] tiene E como primer duplicado.

El predicado member/2 se proporciona en muchos sistemas Prolog y nonmember(X,L) se puede definir como maplist(dif(X),L). De este modo se podría definir firstdup/2 más bien como:

 
firstdup(E, [E|L]) :- 
    member(E, L). 
firstdup(E, [N|L]) :- 
    maplist(dif(N), L), 
    firstdup(E, L). 

Answer 4

En esta respuesta mejoramos el código de lógica pura presentado en this earlier answer. Paso a paso:

1. Combinamos dos predicados memberd/2 y non_member/2 a uno, memberd_t/3, que utiliza un argumento adicional para cosificar pertenencia de la lista en un valor de verdad (o truefalse).

   memberd_t/3 es equivalente a memberd/2 + non_member/2, por lo que podría definirlo así:

    
   memberd_t(X,Xs,true) :- 
       memberd(X,Xs). 
   memberd_t(X,Xs,false) :- 
       non_member(X,Xs). 
   

   O, a la inversa, que podría definir memberd/2 y non_member/2 así:

    
   memberd(X,Xs) :- 
       memberd_t(X,Xs,true). 
   
   non_member(X,Xs) :- 
       memberd_t(X,Xs,false). 
   

   En la práctica, utilizamos una implementación ajustada de memberd_t/3 -one w con un mejor determinismo

   Veamos que memberd_t/3, de hecho, abarca tanto memberd/2 y non_member/2!

    
   ?- memberd_t(X,[1,2,3],T). 
       T = true ,  X=1 
   ; T = true ,    X=2 
   ; T = true ,       X=3 
   ; T = false, dif(X,1), dif(X,2), dif(X,3). 
   

2. Tome la siguiente variante del predicado firstdup/2 (defined earlier) como punto de partida:

    
   firstdup(E,[X|Xs]) :- 
       ( memberd(X,Xs), 
        E=X  
       ; non_member(X,Xs), 
        firstdup(E,Xs) 
       ). 
   

3. Vamos a sustituir el uso de memberd/2 y non_member/2 con memberd_t/3!alzamiento

    
   firstdup(E,[X|Xs]) :- 
       ( memberd_t(X,Xs,true), 
        E=X 
       ; memberd_t(X,Xs,false), 
        firstdup(E,Xs) 
       ). 
   

4. Vamos memberd_t/3!

    
   firstdup(E,[X|Xs]) :- 
       memberd_t(X,Xs,T), 
       ( T=true 
       -> E=X  
       ; T=false, 
        firstdup(E,Xs) 
       ). 
   

5. Por encima de patrón pred_t(OtherArgs,T), (T = true -> Then ; T = false, Else) se puede expresar de manera más concisa utilizando if_/3, escribiendo if_(pred_t(OtherArgs),Then,Else).

    
   firstdup(E,[X|Xs]) :- 
       if_(memberd_t(X,Xs), 
        E=X, 
        firstdup(E,Xs)). 
   

---

Vamos a ejecutar algunas consultas!

 
?- firstdup(1,[1,2,3,1]). 
true.        % succeeds deterministically 

?- firstdup(X,[1,2,3,1]). 
X = 1.        % succeeds deterministically 

?- firstdup(X,[A,B,C]).    % succeeds, leaving behind a choicepoint 
     A=X ,  B=X     % ... to preserve the full solution set. 
;  A=X , dif(B,X), C=X 
; dif(A,X),  B=X , C=X 
; false.