una tuplas misma llenar listas lista elementos comparar cambiar agregar list prolog

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



listas en prolog (8)

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

Ejemplo:

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

No se como hacer esto. ¡Gracias por tu ayuda! Loïc.

Está claro que el reemplazo usando la recursión de @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, haces una matriz en blanco de tamaño Idx y la 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 se puede simplificar 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).

La respuesta de Fortran está bien, pero en SWI-Prolog las estructuras tienen arity 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! Por lo tanto, para mi disgusto, al intentar obtener algún rendimiento, termino llenando un informe de error a la lista de correo de SWI-Prolog ...

EDITAR : Después de la publicación en la lista de correo de SWI-Prolog y la corrección (¡rápida!), 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 valores grandes inusuales, se necesita una instrucción de crecimiento de pila antes de:

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

Aquí está el procedimiento actualizado:

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. Por cierto, creo que esta es una manera bastante horrible de hacer el trabajo. Incluso si quieres hacerlo de esta manera, simplemente usa setarg / 3 en lugar de nb_setarg / 3. Este último debería ser realmente un último recurso. Este método usa más memoria porque necesita tanto el gran término como la lista. Finalmente, los funtores (pares de nombre / aridad) no se recuperan en la actualidad, por lo que se crea un objeto para cada reemplazo de una lista con una longitud en la que nunca se utilizó.

Realmente, nadie debería hacer esto con listas simples de cualquier IMO de longitud considerable, ya que cada actualización ocupará O(n) espacio nuevo. Direct set_once / update a través de setarg/nb_setarg ocupará 0 espacios nuevos, y con la representación en árbol binario de listas, O(log(n)) espacio nuevo. 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 aquí ) 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, el solo acceso a listas simples es irremediablemente lento, O(n) tiempo, convirtiendo cualquier algoritmo cuadrático en un santiamén. Las listas solo son realmente cortas, o como un ejercicio de tarea.

Te daré el caso base, creo que deberías poder hacer el caso recursivo con facilidad:

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

editar:

Ahora que la operación lo ha resuelto, agregaré 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 fuera de límites como pregunta @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).

Básicamente se está aprovechando el operador de corte para no llegar a la tercera cláusula de retroceso si hay un buen reemplazo dentro de los límites.

¿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 que el OP especificó:

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

El código anterior es puro, por lo que podemos hacer consultas más generales y esperar respuestas lógicamente válidas:

?- 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.

Si usamos same_length/2 , append/3 y length/2 , no necesitamos escribir 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).

Consulta de muestra dada por el OP:

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

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

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

Mejor aún, ni siquiera necesitamos especificar el índice 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.

El código presentado en esta respuesta anterior es bastante versátil, gracias a clpfd .

¿Hay algún inconveniente? Sí, hay un inconveniente: ¡ineficiencia!

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

:- use_module(library(clpfd)).

Procedemos como lo hizo esta respuesta previa cuando definió 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).

Entonces ... ¿se ha vuelto 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.

OK, 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!

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].