listing - Eliminar los ceros a la izquierda en la lista en Prolog

prolog listing example

Question

Tengo una lista con un número desconocido de ceros al principio, por ejemplo [0, 0, 0, 1, 2, 0, 3]. Necesito que esta lista se elimine de ceros a la izquierda, para que se vea como [1, 2, 0, 3].

Esto es lo que tengo:

lead([Head | _], _) :- Head =/= 0.
lead([0 | Tail], _) :-
lead(Tail, Tail).

El resultado del cual es simplemente Verdadero. La lectura del seguimiento muestra que se está ejecutando hasta que tenga una lista sin ceros a la izquierda, pero luego la respuesta no se propaga hacia atrás en la pila. Soy bastante nuevo en Prolog, así que no puedo entender cómo hacerlo.

Answer 1

Aquí hay una solución que funciona en todas las direcciones:

lead([],[]).
lead([H|T],[H|T]) :-
dif(H,0).
lead([0|T],T2) :-
lead(T,T2).

Algunas consultas:

?- lead([0,0,0,1,2,0,3], L).
L = [1, 2, 0, 3] ;
false.
?- lead(L, []).
L = [] ;
L = [0] ;
L = [0, 0] ;
L = [0, 0, 0] ;
...
?- lead(L0, L).
L0 = L, L = [] ;
L0 = L, L = [_G489|_G490],
dif(_G489, 0) ;
L0 = [0],
L = [] ;
L0 = [0, _G495|_G496],
L = [_G495|_G496],
dif(_G495, 0) ;
L0 = [0, 0],
L = [] ;
L0 = [0, 0, _G501|_G502],
L = [_G501|_G502],
dif(_G501, 0) ;
L0 = [0, 0, 0],
L = [] ;
...

EDITAR Este predicado en realidad no funciona, por ejemplo, lead(L0, [0,1,2]) .

Answer 2

Aquí hay una solución que no genera ningún punto de elección. Está usando freeze / 2, de una manera que no es anticipada por dif / 2. Pero el uso de freeze / 2 aquí es bastante apropiado, ya que una regla general para freeze / 2 es la siguiente:

Regla de oro para freeze / 2: Use freeze / 2 donde el predicado generaría soluciones desinstaladas y muchos puntos de elección. La esperanza es que un objetivo posterior especifique más la solución, y el congelamiento / 2 se despierte. Desafortunadamente no funciona con CLP (FD) o dif / 2, ya que freeze / 2 no reacciona a los refinamientos implicados por CLP (FD) o dif / 2, solo la unificación lo despertará.

El código es así:

lead(X, Y) :- var(X), !, freeze(X, lead(X,Y)).
lead([X|Y], Z) :- var(X), !, freeze(X, lead([X|Y],Z)).
lead([0|X], Y) :- !, lead(X, Y).
lead(X, X).

Estas son algunas ejecuciones de muestra ( SWI-Prolog sin alguna importación, Jekejeke Prolog usa Minlog Extension y? - use_module (library (term / suspend))):

?- lead([0,0,0,1,2,3], X).
X = [1, 2, 3].
?- lead([0,0|X], Y).
freeze(X, lead(X, Y)).
?- lead([0,0|X], Y), X = [0,1,2,3].
X = [0, 1, 2, 3],
Y = [1, 2, 3].
?- lead([Z,0|X], Y), X = [0,1,2,3].
X = [0, 1, 2, 3],
freeze(Z, lead([Z, 0, 0, 1, 2, 3], Y)).
?- lead([Z,0|X], Y), X = [0,1,2,3], Z = 0.
Z = 0,
X = [0, 1, 2, 3],
Y = [1, 2, 3].

En la implementación de lead / 2 anterior solo se maneja el primer argumento. Manejar múltiples argumentos simultáneamente el predicado cuando / 2 puede ser usado. Pero por simplicidad, esto no se muestra aquí.

Además, cuando se usan objetivos suspendidos, uno puede necesitar un etiquetado como predicado al final, ya que los objetivos suspendidos no pueden detectar inconsistencias entre ellos.

Answer 3

Aquí hay una solución que realmente funciona para todas las entradas posibles y no deja puntos de elección innecesarios:

lead(L0, L) :-
( nonvar(L),
L = [H|_] ->
dif(H,0)
;
true
),
lead_(L0, L).
lead_([], []).
lead_([H|T], L) :-
if_(H /= 0,
L = [H|T],
lead_(T,L)).

La verificación inicial para nonvar(L) es la única solución que he podido encontrar que evitaría problemas con, por ejemplo, lead(L0, [0,1,2,3]) , mientras se conserva el comportamiento del predicado en todos otras situaciones

Esto usa if_/3 , parte de la library(reif)

if_(If_1, Then_0, Else_0) :-
call(If_1, T),
( T == true -> Then_0
; T == false -> Else_0
; nonvar(T) -> throw(error(type_error(boolean,T),
type_error(call(If_1,T),2,boolean,T)))
; throw(error(instantiation_error,instantiation_error(call(If_1,T),2)))
).

Esto también usa (/=)/3 , que se me ocurrió con una simple modificación de (=)/3 en la library(reif) .

/=(X, Y, T) :-
( X /= Y -> T = true
; X == Y -> T = false
; T = true, dif(X, Y)
; T = false,
X = Y
).

Algunas consultas

?- lead([0,0,0,1,2,0,3],L). % No choice point
L = [1, 2, 0, 3].
?- lead([1,2,0,3],L).
L = [1, 2, 0, 3].
?- lead([0,0,0,0],L).
L = [].
?- lead([],L).
L = [].
?- lead(L0,[0,1,2,0,3]). % Correctly fails
false.
?- lead(L0,[1,2,0,3]).
L0 = [1, 2, 0, 3] ;
L0 = [0, 1, 2, 0, 3] ;
L0 = [0, 0, 1, 2, 0, 3] ;
…
?- lead(L0,L). % Exhaustively enumerates all cases:
L0 = L, L = [] ; % - LO empty
L0 = L, L = [_G2611|_G2612], % - L0 contains no leading 0
dif(_G2611, 0) ;
L0 = [0], % - L0 = [0]
L = [] ;
L0 = [0, _G2629|_G2630], % - L0 contains one leading 0
L = [_G2629|_G2630],
dif(_G2629, 0) ;
L0 = [0, 0], % - L0 = [0, 0]
L = [] ;
L0 = [0, 0, _G2647|_G2648], % - L0 contains two leading 0s
L = [_G2647|_G2648],
dif(_G2647, 0) ;
… % etc.

Answer 4

Así es como lo expresaría. Primero, establezca restricciones: X o Y deben estar vinculados a una lista. Cualquier otra cosa falla

• Si X está vinculado, no nos importa Y: se puede unir o no. Simplemente eliminamos los ceros a la izquierda de X y unificamos los resultados con Y. Esta ruta tiene una única solución posible.

• Si X está desatado e Y está vinculado, cambiamos al modo generativo. Esta ruta tiene infinitas soluciones posibles.

El código:

strip_leading_zeros(X,Y) :- listish(X), !, rmv0( X , Y ) .
strip_leading_zeros(X,Y) :- listish(Y), !, add0( Y , X ) .
rmv0( [] , [] ) .
rmv0( [D|Ds] , R ) :- D /= 0 -> R = [D|Ds] ; rmv0(Ds,R) .
add0( X , X ) .
add0( X , Y ) :- add0([0|X],Y ) .

listish/1 es una simple prueba superficial para listish-ness. Usa is_list/1 si quieres ser pedante sobre las cosas.

listish( L ) :- var(L), !, fail.
listish( [] ) .
listish( [_|_] ) .

Editado para que note: is_list/1 recorre toda la lista para asegurarse de que está probando es una lista correctamente construida, es decir, un término ./2 , cuyo hijo derecho es en sí mismo otro término ./2 o el átomo [] (que denota la lista vacía). Si la lista es larga, esta puede ser una operación costosa.

Entonces, algo como [a,b,c] es una lista adecuada y en realidad es este término:. .(a,.(b,.(c,[]))) . Algo como [a,b|32] no es una lista adecuada: es el término .(a,.(b,32)) .

Answer 5

Con la biblioteca (reif) :

:- use_module(reif).
remove_leading_zeros([], []).
remove_leading_zeros([H|T], Rest) :-
if_( H = 0,
remove_leading_zeros(T, Rest),
Rest = [H|T]).

Entonces:

?- remove_leading_zeros([0,0,0,1,2,0,3], R).
R = [1, 2, 0, 3].
?- remove_leading_zeros([2,0,3], R).
R = [2, 0, 3].
?- remove_leading_zeros(L, R).
L = R, R = [] ;
L = [0],
R = [] ;
L = [0, 0],
R = [] ;
L = [0, 0, 0],
R = [] . % and so on

Answer 6

El problema en su código es que el segundo parámetro, su salida, se especifica como _ , por lo que su predicado es verdadero para cualquier salida. Lo que quiere es un predicado que sea verdadero si y solo si es la entrada menos los ceros a la izquierda.

lead([], []).
lead([0 | Tail], Tail2) :- !, lead(Tail, Tail2).
lead([Head | Tail], [Head | Tail]) :- Head =/= 0.

El ! en la primera línea es opcional. Se poda el árbol de búsqueda para que Prolog no tenga en cuenta la segunda línea (que fallaría) si la primera línea coincide.