list - proyectos - Agregue dos más ocurrencias usando prolog

prolog pdf

Question

Tengo una lista [a, b, a, a, a, c, c] y necesito agregar dos más ocurrencias de cada elemento.

El resultado final debería verse así:

[a, a, a, b, b, b, a, a, a, a, a, c, c, c, c]

Si tengo un elemento en la lista que es igual al siguiente, entonces continúa hasta que haya un nuevo elemento, cuando encuentra el nuevo, agrega dos ocurrencias del elemento anterior y luego se mueve.

Este es mi código hasta ahora, pero no puedo entender cómo agregar dos ...

dbl([], []).
dbl([X], [X,X]).
dbl([H|T], [H,H|T], [H,H|R]) :- dbl(T, R).

Answer 1

Estaba a punto de lanzar esta versión con if_ / 3 y (=) / 3 en el sombrero cuando vi que @repeat ya lo había sugerido. Así que esta es esencialmente la versión más compacta tal como se resume en @repeat:

list_dbl([],[]).
list_dbl([X],[X,X,X]).
list_dbl([A,B|Xs],DBL) :-
   if_(A=B,DBL=[A,B|Ys],DBL=[A,A,A,B|Ys]),
   list_dbl([B|Xs],[B|Ys]).

Produce los mismos resultados que dbl2 / 2 por @repeat:

   ?- list_dbl([a],DBL).
DBL = [a,a,a]
   ?- list_dbl([a,b,b],DBL).
DBL = [a,a,a,b,b,b,b]

La consulta de ejemplo del OP funciona como se espera:

   ?- list_dbl([a,b,a,a,a,c,c],DBL).
DBL = [a,a,a,b,b,b,a,a,a,a,a,c,c,c,c]

Además aquí están algunas de las consultas de ejemplo proporcionadas por @ lambda.xy.x. Producen los mismos resultados que @ repeat''s dbl / 2 y @ lambda.xy.x''s dbl / 2:

   ?- dif(Xs,[a,a,a,b,b,b,a,a,a,a,a,c,c,c,c]), list_dbl([a,b,a,a,a,c,c],Xs).
no

   ?- list_dbl(X,[a,a,a,b,b]).
no

   ?- list_dbl(L,[a,a,a,b,b,b]).
L = [a,b] ? ;
no

   ?- list_dbl(L,DBL).
DBL = L = [] ? ;
DBL = [_A,_A,_A],
L = [_A] ? ;
DBL = [_A,_A,_A,_A],
L = [_A,_A] ? ;
DBL = [_A,_A,_A,_A,_A],
L = [_A,_A,_A] ? ;
...

   ?- list_dbl([a,X,a],DBL).
DBL = [a,a,a,a,a],
X = a ? ;
DBL = [a,a,a,X,X,X,a,a,a],
dif(X,a),
dif(a,X)

   ?- length(L,_), list_dbl(L,DBL).
DBL = L = [] ? ;
DBL = [_A,_A,_A],
L = [_A] ? ;
DBL = [_A,_A,_A,_A],
L = [_A,_A] ? ;
DBL = [_A,_A,_A,_B,_B,_B],
L = [_A,_B],
dif(_A,_B) ? ;
DBL = [_A,_A,_A,_A,_A],
L = [_A,_A,_A] ? 

Answer 2

Su código parece un poco extraño porque la última regla toma tres parámetros. Solo llama a la versión binaria, por lo que ninguna recursividad intentará derivarla.

Ya has tenido una buena idea para mirar las partes de la lista, donde los elementos cambian. Entonces hay 4 casos:

1) Tu lista está vacía. 2) Tienes exactamente un elemento. 3) Tu lista comienza con dos elementos iguales. 4) Tu lista comienza con dos elementos diferentes.

El caso 1 no está especificado, por lo que es posible que necesite encontrar una opción sensata para eso. El caso 2 es de alguna manera similar al caso 4, ya que el final de la lista se puede ver como un cambio en los elementos, donde debe agregar dos copias, pero luego ha terminado. El Caso 3 es bastante simple, podemos simplemente mantener el elemento y recurse en el resto. El caso 4 es donde debe insertar las dos copias nuevamente.

Esto significa que su código se verá más o menos así:

% Case 1
dbl([],[]).
% Case 2
dbl([X],[X,X,X]).
% Case 3
dbl([X,X|Xs], [X|Ys]) :-
   % [...] recursion skipping the leading X
% Case 4
dbl([X,Y|Xs], [X,X,X|Ys]) :-
   dif(X,Y),
   % [...] we inserted the copies, so recursion on [Y|Xs] and Ys

El caso 3 debe ser fácil de terminar, simplemente soltamos la primera X de ambas listas y recursemos en dbl ([X | Xs], Ys). Tenga en cuenta que implícitamente hicimos que los dos primeros elementos fueran iguales (es decir, los unificamos) escribiendo la misma variable dos veces.

Si observa el encabezado del caso 4, puede imitar directamente el patrón que describió: se supone que la lista comienza con X, luego Y y son diferentes (dif (X, Y)), la X se repite 3 veces en lugar de solo copiado y luego continuamos con la recursión en el resto comenzando con Y: dbl ([Y | Xs], Ys).

Entonces probemos el predicado:

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

Nuestro caso de prueba es aceptado (verdadero) y no encontramos más de una solución (falso). Veamos si encontramos una solución incorrecta:

?- dif(Xs,[a,a,a,b,b,b,a,a,a,a,a,c,c,c,c]), dbl([a,b,a,a,a,c,c],Xs).
false.

No, eso también es bueno. ¿Qué sucede si tenemos variables en nuestra lista?

?- dbl([a,X,a],Ys).
X = a,
Ys = [a, a, a, a, a] ;
Ys = [a, a, a, X, X, X, a, a, a],
dif(X, a),
dif(X, a) ;
false.

O bien X = a, entonces Ys es una sola carrera de 5 como; o X no es igual a a, entonces necesitamos anexar las copias en las tres ejecuciones. También parece bien. (*)

Ahora veamos, ¿qué pasa si solo especificamos la solución?

?- dbl(X,[a,a,a,b,b]).
false.

Correcto, una lista con una racha de solo dos bs no puede ser el resultado de nuestra especificación. Intentemos agregar uno:

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

¡Hurra, funcionó! Entonces, como última prueba, veamos qué sucede si llamamos a nuestro predicado con dos variables:

?- dbl(Xs,Ys).
Xs = Ys, Ys = [] ;
Xs = [_G15],
Ys = [_G15, _G15, _G15] ;
Xs = [_G15, _G15],
Ys = [_G15, _G15, _G15, _G15] ;
Xs = [_G15, _G15, _G15],
Ys = [_G15, _G15, _G15, _G15, _G15] ;
Xs = [_G15, _G15, _G15, _G15],
Ys = [_G15, _G15, _G15, _G15, _G15, _G15] ;
[...]

Parece que obtenemos las respuestas correctas, pero solo vemos casos para una sola carrera. Este es el resultado de la estrategia de búsqueda de prolog (que no explicaré aquí). Pero si miramos listas más cortas antes de generar las más largas, podemos ver todas las soluciones:

 ?- length(Xs,_), dbl(Xs,Ys).
Xs = Ys, Ys = [] ;
Xs = [_G16],
Ys = [_G16, _G16, _G16] ;
Xs = [_G16, _G16],
Ys = [_G16, _G16, _G16, _G16] ;
Xs = [_G86, _G89],
Ys = [_G86, _G86, _G86, _G89, _G89, _G89],
dif(_G86, _G89) ;
Xs = [_G16, _G16, _G16],
Ys = [_G16, _G16, _G16, _G16, _G16] ;
Xs = [_G188, _G188, _G194],
Ys = [_G188, _G188, _G188, _G188, _G194, _G194, _G194],
dif(_G188, _G194) ;
[...]

Entonces parece que tenemos un predicado que funciona (**), supuestamente completaste los objetivos que faltaban en el texto :)

(*) Una observación aquí: este caso solo funciona porque estamos usando dif. Los primeros predicados con igualdad, uno generalmente se encuentra son =, == y sus respectivas negaciones / = y / ==. The = significa unifyability (sustituyendo variables en los argumentos st se vuelven iguales) y = = significa igualdad sintáctica (los términos son exactamente iguales). P.ej:

?- f(X) = f(a).
X = a.

?- f(X) /= f(a).
false.

?- f(X) == f(a).
false.

?- f(X) /== f(a).
true.

Esto significa que podemos hacer que f (X) sea igual a f (a), si sustituimos X por a. Esto significa que si preguntamos si no se pueden hacer iguales (/ =), obtenemos la respuesta falsa. Por otro lado, los dos términos no son iguales, entonces == devuelve falso, y su negación / == responde verdadera.

Lo que esto también significa es que X / == Y siempre es verdadero, por lo que no podemos usar / == en nuestro código. En contraste con eso, dif espera hasta que pueda decidir si sus argumentos son iguales o no. Si aún no se ha decidido después de encontrar una respuesta, se imprimen las instrucciones "dif (X, a)".

(**) Una última observación aquí: también hay una solución con el constructo if-then-else (test -> goals_if_true; goals_if_false, que combina los casos 3 y 4. Dado que prefiero esta solución, es posible que deba examinar el otra versión usted mismo.

Answer 3

TL; DR : desde un punto de vista declarativo, el código esbozado por @ lambda.xy.x es perfecto. Su determinación puede mejorarse sin sacrificar la pureza lógica .

Variante de código # 0: código de @ lambda.xy.x

Aquí está el código que queremos mejorar:

dbl0([], []). dbl0([X], [X,X,X]). dbl0([X,X|Xs], [X|Ys]) :- dbl0([X|Xs], Ys). dbl0([X,Y|Xs], [X,X,X|Ys]) :- dif(X, Y), dbl0([Y|Xs], Ys).

Considere la siguiente consulta y la respuesta que SWI-Prolog nos brinda:

?- dbl0([a],Xs). Xs = [a,a,a] ; false.

Con ; false ; false el prólogo-nivel de SWI indica que se dejó un punto de elección cuando se demostró el objetivo.

• Para la primera respuesta, Prolog no buscó en todo el árbol de pruebas.
• En cambio, respondió "aquí hay una respuesta, puede haber más".
• Luego, cuando se le preguntó por más soluciones, Prolog atravesó las ramas restantes del árbol de pruebas pero no encontró más respuestas.

En otras palabras: Prolog necesita pensarlo dos veces para demostrar algo que sabíamos desde el principio.

Entonces, ¿cómo podemos dar pistas de determinación a Prolog? Utilizando:

1. construcciones de control !/0 y / o (->)/2 (potencialmente impuras)

2. primer argumento indexado en el functor principal ( nunca impuro)

El código presentado en la respuesta anterior por @CapelliC, que se basa en !/0 , (->)/2 y el predicado meta-lógico (/=)/2 funciona bien si todos los argumentos están suficientemente instanciados . De lo contrario, pueden surgir respuestas erráticas, como muestra el comentario de @ lambda.xy.x.

Variante de código n. ° 1: indización

La indexación puede mejorar la determinación sin hacer que el código sea monótono. Si bien los diferentes procesadores Prolog tienen distintas capacidades de indexación avanzada, la variante de indexación "first-argument principal-functor" está ampliamente disponible.

¿Director de escuela? Es por esto que ejecutar el objetivo dbl0([a],Xs) deja atrás un punto de elección: Sí, el objetivo solo coincide con una cláusula- dbl0([X],[X,X,X]). -pero no busca más profundo que el functor principal Prolog asume que cualquiera de las últimas tres cláusulas podría eventualmente utilizarse. Por supuesto, sabemos mejor ...

Para decirle a Prolog que utilizamos indexación principal-funtor de primer argumento:

dbl1([], []). dbl1([E|Es], Xs) :- dbl1_(Es, Xs, E). dbl1_([], [E,E,E], E). dbl1_([E|Es], [E|Xs], E) :- dbl1_(Es, Xs, E). dbl1_([E|Es], [E0,E0,E0|Xs], E0) :- dif(E0, E), dbl1_(Es, Xs, E).

¿Mejor? Un poco, pero la determinación podría ser aún mejor ...

Variante de código n. ° 2: indización en igualdad de términos reificados

Para hacer que Prolog vea que las dos cláusulas recursivas de dbl1_/3 son mutuamente excluyentes (en ciertos casos), reificamos el valor de verdad de la igualdad de término y luego indexamos ese valor :

Aquí es donde entra en juego el término de igualdad reificada (=)/3 :

dbl2([], []). dbl2([E|Es], Xs) :- dbl2_(Es, Xs, E). dbl2_([], [E,E,E], E). dbl2_([E|Es], Xs, E0) :- =(E0, E, T), t_dbl2_(T, Xs, E0, E, Es). t_dbl2_(true, [E|Xs], _, E, Es) :- dbl2_(Es, Xs, E). t_dbl2_(false, [E0,E0,E0|Xs], E0, E, Es) :- dbl2_(Es, Xs, E).

Consultas de muestra con SWI-Prolog:

?- dbl0([a],Xs). Xs = [a, a, a] ; false. ?- dbl1([a],Xs). Xs = [a, a, a]. ?- dbl2([a],Xs). Xs = [a, a, a]. ?- dbl0([a,b,b],Xs). Xs = [a, a, a, b, b, b, b] ; false. ?- dbl1([a,b,b],Xs). Xs = [a, a, a, b, b, b, b] ; false. ?- dbl2([a,b,b],Xs). Xs = [a, a, a, b, b, b, b].

Para hacer que el código anterior sea más compacto, use la construcción de control if_/3 .

Answer 4

dbl([X,Y|T], [X,X,X|R]) :- X /= Y, !, dbl([Y|T], R).
dbl([H|T], R) :-
        T = []
    ->  R = [H,H,H]
    ;   R = [H|Q], dbl(T, Q).

La primera cláusula maneja el requisito básico, agregando dos elementos en el cambio de secuencia. El segundo maneja la terminación de la lista como un cambio de secuencia, de lo contrario, hace una copia simple.