Prólogo: reemplazar un elemento en una lista en un índice especificado

Question

Me gustaría tener un predicado Prolog que pueda reemplazar un elemento en una lista en un índice especificado.

Ejemplo:

% replace(+List,+Index,+Value,-NewList). 
?- L=[a,b,c,d], replace(L,1,z,L2). 
L2 = [a,z,c,d] 

No sé cómo hacer esto. ¡Gracias por tu ayuda! Loïc.

Answer 1

te voy a dar el caso base, creo que debe ser capaz de hacer el caso recursivo con facilidad:

replace([_|T], 0, X, [X|T]). 

edición:

Ahora que el op ha resuelto, voy a añadir el caso recursivo:

replace([H|T], I, X, [H|R]):- I > 0, I1 is I-1, replace(T, I1, X, R). 

Edit2:

Esto debería devolver la lista original en una situación de fuera de límites mientras que pide @GeorgeConstanza en los comentarios:

replace([_|T], 0, X, [X|T]). 
replace([H|T], I, X, [H|R]):- I > -1, NI is I-1, replace(T, NI, X, R), !. 
replace(L, _, _, L). 

Se trata básicamente aprovechando el operador de corte para no llegar a la cláusula tercera alternativa en caso de que hay una buena reemplazo dentro de límites

Answer 2

bien, claramente, el reemplazo mediante recursion por @fortran es el camino a seguir. pero, ¿es esto demasiado loco/lento para usar realmente?

replace(List, Idx, With, ListOut) :- 
    length(Idx, Before), 
    append(Before, After, List), 
    ( After=[_Discard|Rest] 
    -> true 
    ; Rest=[] 
    ), 
    append(Before, [With|Rest], ListOut). 

Básicamente se hace una matriz en blanco de tamaño Idx y se lo vincula a la lista de entrada. luego deseche el artículo después de eso y una las dos listas junto con el elemento de reemplazo intercalado.

esto puede simplificarse aún más si está bien si falla si intenta establecer idx N (indización desde 0) de una lista de elementos N .

replace(List, Idx, With, ListOut) :- 
    length(Idx, Before), 
    append(Before, [_Discard|Rest], List), 
    append(Before, [With|Rest], ListOut). 

Answer 3

La respuesta de FORTRAN que está bien, pero en estructuras SWI-Prolog tienen aridad ilimitado, así que esto debería funcionar:

replace([_|T], 0, X, [X|T]). 
replace([H|T], I, X, [H|R]) :- 
    I > 0, 
    I1 is I - 1, 
    replace(T, I1, X, R). 

replace1(L, I, X, R) :- 
    Dummy =.. [dummy|L], 
    J is I + 1, 
    nb_setarg(J, Dummy, X), 
    Dummy =.. [dummy|R]. 

tr(Method, K) :- 
    length(L, K), 
    K1 is K - 1, 
    time(call(Method, L, K1, test, R)), 
    assertion(nth1(K, R, test)). 

pero, para mi sorpresa:

?- % /home/carlo/prolog/replace.pl compiled 0,00 sec, 2,280 bytes 
?- tr(replace,2000000). 
% 3,999,999 inferences, 2,123 CPU in 2,128 seconds (100% CPU, 1884446 Lips) 
true . 

?- tr(replace1,2000000). 
% 5 inferences, 1,410 CPU in 1,414 seconds (100% CPU, 4 Lips) 
true. 

?- tr(replace,4000000). 
% 7,999,999 inferences, 3,510 CPU in 3,520 seconds (100% CPU, 2279267 Lips) 
true . 

?- tr(replace1,4000000). 
% 5 inferences, 2,825 CPU in 2,833 seconds (100% CPU, 2 Lips) 
true. 

?- tr(replace,5000000). 
% 9,999,999 inferences, 3,144 CPU in 3,153 seconds (100% CPU, 3180971 Lips) 
true . 

?- tr(replace1,5000000). 
% 5 inferences, 4,476 CPU in 4,486 seconds (100% CPU, 1 Lips) 
ERROR: =../2: Arguments are not sufficiently instantiated 
^ Exception: (9) setup_call_catcher_cleanup(system:true, prolog_statistics:catch(user:call(replace1, [_G1, _G4, _G7, _G10|...], 4999999, test, _G15000005), _G15000021, (report(t(1324124267.2924964, 18.892632697, 28490132), 10), throw(_G15000021))), _G15000145, prolog_statistics: (_G15000032=true)) ? abort 
% Execution Aborted 

Mi primer intento (con K = 10000000) mató el proceso! lo tanto, para mi disgusto, tratando de ganar algo de rendimiento, me acaban de llenar un informe de error a la lista de correo SWI-Prolog ...

EDITAR: Después de que el mensaje de correo a la lista de SWI-Prolog, y el (rápido!) corrección, he reconstruido, y aquí está la versión que da una pista sobre el uso de la memoria (¡ahora es todo el código estándar ISO!).Debido a los grandes valores inusuales, se necesita una pila crecer de instrucciones antes:

?- prolog_stack_property(global,limit(L)), N is L*2, set_prolog_stack(global,limit(N)). 
N = 536870912. 

Aquí es el procedimiento actualización:

replace2(L, I, X, R) :- 
    Dummy =.. [dummy|L], 
    J is I + 1, 
    setarg(J, Dummy, X), 
    Dummy =.. [dummy|R]. 

y la prueba:

?- tr(replace,10000000). 
% 19,999,999 inferences, 5.695 CPU in 5.719 seconds (100% CPU, 3511942 Lips) 
true . 

?- tr(replace2,10000000). 
% 5 inferences, 2.564 CPU in 2.571 seconds (100% CPU, 2 Lips) 
true. 

El código es más rápido , pero tenga en cuenta el comentario de Jan a mi correo:

Se reduce a un mal manejo de errores en = .. (+, -). Fijo. B.t.w. I creo que esta es una manera bastante horrible de hacer el trabajo. Incluso si quiere hacerlo de esta manera, simplemente use setarg/3 en lugar de nb_setarg/3. El último debería ser realmente un último recurso. Este método usa más memoria porque necesita el término enorme y la lista. Finalmente, los funtores (pares de nombre/aridad) no se recuperan actualmente, por lo que crea un objeto para cada reemplazo de una lista con una longitud en la que este nunca se usó.

Answer 4

Realmente, nadie debe jamás hacer esto con listas simples de un largo espacio de la OMI, ya que cada actualización durará unos O(n) nuevo espacio. Direct set_once/update a través de setarg/nb_setarg ocupará 0 nuevo espacio, y con representación en árbol binario de listas, O(log(n)) nuevo espacio. Los reemplazos también podrían mantenerse en un diccionario separado, que se mantendrá como un árbol (ya que necesita crecer). Una lista fragmentada (como in here) podría contener grandes fragmentos en un árbol, cada uno un término compuesto de tamaño fijo directamente configurable/actualizable a través de setarg/nb_setarg, y agregar nuevos fragmentos en el árbol según sea necesario.

Incluso sin la actualización, simplemente acceder a las listas de fricción es desesperadamente lento, O(n) tiempo, convirtiendo cualquier algoritmo cuadrática en un santiamén. Las listas solo son realmente cortas, o como un ejercicio de tarea.

Answer 5

¿Qué hay de hacerlo de una manera directa como esta?

 
:- use_module(library(clpfd)). 

list_nth0_item_replaced([_|Xs], 0, E, [E|Xs]). 
list_nth0_item_replaced([X|Xs], N, E, [X|Ys]) :- 
    N #> 0, 
    N #= N0+1, 
    list_nth0_item_replaced(Xs, N0, E, Ys). 

Aquí está el caso de uso de la OP especifica:

?- list_nth0_item_replaced([a,b,c,d],1,z,Ls). 
    Ls = [a,z,c,d] 
; false. 

Por encima de código es puro, por lo que se puede pedir consultas más generales — y esperar respuestas lógicamente sonido:

?- list_nth0_item_replaced([a,b,c,d], N, X, Ls). 
    N = 0, Ls = [X,b,c,d] 
; N = 1, Ls = [a,X,c,d] 
; N = 2, Ls = [a,b,X,d] 
; N = 3, Ls = [a,b,c,X] 
; false. 

Answer 6

Si utilizamos same_length/2, append/3 y length/2, no es necesario que escribamos el código recursivo:

 
list_nth0_item_replaced(Es, N, X, Xs) :- 
    same_length (Es, Xs), 
    append (Prefix, [_|Suffix], Es), 
    length (Prefix, N), 
    append(Prefix, [X|Suffix], Xs). 

Muestra consulta propuesta por el OP:

?- list_nth0_item_replaced([a,b,c,d], 1, z, Xs). 
    Xs = [a,z,c,d] 
; false. 

Esto funciona "en la otra dirección", también!

?- list_nth0_item_replaced(Xs, 1, z, [a,z,c,d]). 
    Xs = [a,_A,c,d] 
; false. 

Mejor aún, ni siquiera es necesario especificar el índice de concreto:

?- list_nth0_item_replaced(Es, N, X, [a,z,c,d]). 
    N = 0, X = a, Es = [_A, z, c, d] 
; N = 1, X = z, Es = [ a,_A, c, d] 
; N = 2, X = c, Es = [ a, z,_A, d] 
; N = 3, X = d, Es = [ a, z, c,_A] 
; false. 

?- list_nth0_item_replaced([a,b,c,d], N, X, Xs). 
    N = 0, Xs = [X,b,c,d] 
; N = 1, Xs = [a,X,c,d] 
; N = 2, Xs = [a,b,X,d] 
; N = 3, Xs = [a,b,c,X] 
; false. 

Answer 7

el código presentado in this previous answer es muy versátil gracias a — clpfd.

¿Hay algún inconveniente? Sí, hay una desventaja: ¡Ineficiencia!

En esta respuesta, mejoramos el rendimiento y preservamos la versatilidad.

 
:- use_module(library(clpfd)). 

Exactamente igual que lo hicieron this previous answer cuando se define el predicado fd_length/2:

list_nth0_item_replaced__NEW(Es, N, X, Xs) :- 
    list_index0_index_item_replaced(Es, 0,N, X, Xs). 

list_index0_index_item_replaced([_|Es], I ,I, X, [X|Es]). 
list_index0_index_item_replaced([E|Es], I0,I, X, [E|Xs]) :- 
    I0 #< I, 
    I1 #= I0+1, 
    list_index0_index_item_replaced(Es, I1,I, X, Xs). 

Así que ... ha conseguido que más rápido?

 
?- numlist(1,100000,Zs), time(list_nth0_item_replaced(Zs,99999,x,Xs)). 
% 14,499,855 inferences, 0.893 CPU in 0.893 seconds (100% CPU, 16237725 Lips) 
Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...], 
Xs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ; 
% 7 inferences, 0.000 CPU in 0.000 seconds (99% CPU, 18377 Lips) 
false. 

?- numlist(1,100000,Zs), time(list_nth0_item_replaced__NEW(Zs,99999,x,Xs)). 
% 499,996 inferences, 0.049 CPU in 0.049 seconds (100% CPU, 10158710 Lips) 
Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...], 
Xs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ; 
% 6 inferences, 0.000 CPU in 0.000 seconds (93% CPU, 213988 Lips) 
false. 

bien, es más rápido. Pero, ¿sigue siendo versátil?

 
?- list_nth0_item_replaced__NEW([a,b,c,d], 1, z, Xs). 
    Xs = [a,z,c,d] 
; false. 

?- list_nth0_item_replaced__NEW(Xs, 1, z, [a,z,c,d]). 
    Xs = [a,_A,c,d] 
; false. 

?- list_nth0_item_replaced__NEW(Es, N, X, [a,z,c,d]). 
    N = 0, X = a, Es = [_A, z, c, d], 
; N = 1, X = z, Es = [ a,_A, c, d] 
; N = 2, X = c, Es = [ a, z,_A, d], 
; N = 3, X = d, Es = [ a, z, c,_A] 
; false. 

?- list_nth0_item_replaced__NEW([a,b,c,d], N, X, Xs). 
    N = 0, Xs = [X,b,c,d] 
; N = 1, Xs = [a,X,c,d] 
; N = 2, Xs = [a,b,X,d] 
; N = 3, Xs = [a,b,c,X] 
; false. 

¡Me parece bien!

Answer 8

Otra forma en que se me ocurrió, que creo que es correcta (?). No sé sobre la complejidad del tiempo de ejecución.

replace(I, L, E, K) :- 
    nth0(I, L, _, R), 
    nth0(I, K, E, R). 

Uso:

?- replace(2, [1, 2, 3, 4, 5], 10, X). 
X = [1, 2, 10, 4, 5].