sorting - inglés - gramatica del ingles paso a paso pdf

Prolog-¿Cómo consigo que la cola no sea nula?

Question

Tengo el siguiente problema:

Defina un predicado sorted(LL) , que se cumple cuando la lista LL contiene otras listas que están ordenadas en orden de aumentar la longitud. Por ejemplo:

?- sorted([[],[1],[1,1],[1,1,1]]) -> yes.
?- sorted([[],[1],[1,1]]) -> yes.
?- sorted([[1],[],[1,1],[1,1,1]]) -> no.

Y tengo este código hasta ahora:

% shorter/2

shorter([],_).
shorter([_|T1], [_|T2]) :- shorter(T1,T2).

% sorted/1

sorted([]).
sorted([_]).
sorted([L1,L2 | T]) :- shorter2(L1, L2), sorted([L2,T]).

El problema está contenido en la línea anterior: sorted([L2,T]) . Cuando solo queda un elemento en la lista de listas, esa llamada agregará una lista vacía [] debido a que fallará la versión más corta / 2. Se representa en la siguiente traza SWIPL.

[trace]  ?- sorted([[1],[2,3]]).
   Call: (6) sorted([[1], [2, 3]]) ? creep
   Call: (7) shorter2([1], [2, 3]) ? creep
   Call: (8) shorter2([], [3]) ? creep
   Exit: (8) shorter2([], [3]) ? creep
   Exit: (7) shorter2([1], [2, 3]) ? creep
   Call: (7) sorted([[2, 3], []]) ? creep <-- empty list appended
   Call: (8) shorter2([2, 3], []) ? creep
   Fail: (8) shorter2([2, 3], []) ? creep
   Fail: (7) sorted([[2, 3], []]) ? creep
   Fail: (6) sorted([[1], [2, 3]]) ? creep

Answer 1

@PauloMoura ya te dio la respuesta correcta. ¿Hay algo que aprender sobre esto? ¿Cómo encontraste ese problema? ¿Y cómo puedes localizar tales problemas sistemáticamente? Supongo que no saltaste al depurador para ver todos esos rastros por pura curiosidad y un bajo suministro de gifs animados.

Usted más bien encontró un problema . Es decir, tenía el objetivo sorted([[1],[2,3]]). que esperabas tener éxito, pero no fue así. Entonces tuviste aquí un fracaso inesperado . Algunas veces también se llama insuficiencia o incompletitud . Esto significa que la definición de sorted/1 es demasiado especializada, describe un conjunto de soluciones que es demasiado pequeño, al menos se omite sorted([[1],[2,3]]) .

A menudo, ayuda a minimizar el problema, primero. También sorted([[],[3]]) falla, aunque esperamos que tenga éxito. Y sorted([[],[]]) incluso bucles.

Comprender la no terminación

Loops? Eso a menudo es aún más fácil de localizar en un programa Prolog puro. Agregaré objetivos false y metas como T = [] en el programa. El fragmento de programa resultante (llamado segmento de falla ) ciertamente se volverá completamente disfuncional. Pero conservará una propiedad muy agradable. Para: si este nuevo fragmento se repite, entonces también se reproducirá el programa original. Aquí está ese programa que aún sigue:

?- sorted([[],[]]), false. sorted([]) :- false. sorted([_]) :- false. sorted([L1,L2 | T]) :- T = [], L1 = [], L2 = [], shorter(L1, L2), sorted([L2,T]). shorter([],_). shorter([_|T1], [_|T2]) :- false, shorter(T1,T2).

en otras palabras:

sorted([[],[]]) :-
   shorter([],[]),
   sorted([[],[]]).

Entonces, procesalmente hablando, esa regla no (siempre) reduce la longitud de la lista.

Lectura final

Otra forma de entender el problema es leer la regla recursiva de derecha a izquierda en la dirección en que apunta la flecha . En realidad ,: :- pretende simbolizar ←, bueno, el estilo de los años 70 (escucha este verano de 1972 en francés hasta que entiendas). Así que probemos esto. Lo leeré:

sorted([L1,L2 | T]) :- shorter2(L1, L2), sorted([L2,T]).
                                         ^^^^^^^^^^^^^^ starting here

Comienzo en el lado derecho e interpreto esto como:

Siempre, sorted([L2,T]) es verdadero.

Tal vez algún comentario adicional: ahora, puede sentirse bastante incómodo. Usted podría decir: ¿Quién sabe esto? Tal vez eso no es cierto en absoluto! Pero el punto es que es solo condicional. ¿OKAY?

y siempre que sea shorter(L1, L2) es verdadero

entonces, podemos concluir que sorted([L1, L2|T]) es verdadero.

Entonces tomamos una lista de longitud 2 como otorgada y concluimos que una lista de longitud 2 o más también es válida.

Pero, ¿dónde realmente declaramos que una lista de longitud 2 se mantiene? No hay otro lugar que esta regla. Por lo tanto: en ninguna parte se declara esto. Y por lo tanto, las listas de longitud 2 o más nunca se ordenarán.

Answer 2

Tiene dos errores tipográficos en la última cláusula del predicado sorted/1 , que debería ser:

sorted([L1,L2| T]) :- shorter(L1, L2), sorted([L2| T]).