prolog - Recopile todas las soluciones "mínimas" de un predicado

backtracking aggregates

Question

Dados los siguientes hechos en una base de datos:

foo(a, 3).
foo(b, 2).
foo(c, 4).
foo(d, 3).
foo(e, 2).
foo(f, 6).
foo(g, 3).
foo(h, 2).

Quiero recopilar todos los primeros argumentos que tienen el segundo argumento más pequeño, más el valor del segundo argumento. Primer intento:

find_min_1(Min, As) :-
    setof(B-A, foo(A, B), [Min-_|_]),
    findall(A, foo(A, Min), As).

?- find_min_1(Min, As).
Min = 2,
As = [b, e, h].

En lugar de setof/3 , podría usar aggregate/3 :

find_min_2(Min, As) :-
    aggregate(min(B), A^foo(A, B), Min),
    findall(A, foo(A, Min), As).

?- find_min_2(Min, As).
Min = 2,
As = [b, e, h].

nótese bien

Esto solo da los mismos resultados si busco el mínimo de un número . Si una expresión aritmética está involucrada, los resultados pueden ser diferentes. Si se trata de un no número, el aggregate(min(...), ...) arrojará un error.

O, en cambio, puedo usar la lista completa ordenada por clave:

find_min_3(Min, As) :-
    setof(B-A, foo(A, B), [Min-First|Rest]),
    min_prefix([Min-First|Rest], Min, As).

min_prefix([Min-First|Rest], Min, [First|As]) :-
    !,
    min_prefix(Rest, Min, As).
min_prefix(_, _, []).

?- find_min_3(Min, As).
Min = 2,
As = [b, e, h].

Finalmente, a la (s) pregunta (s):

• ¿Puedo hacer esto directamente con la biblioteca (agregado)? Parece que debería ser posible ...

• ¿O hay un predicado como std::partition_point de la biblioteca estándar de C ++?

• ¿O hay alguna manera más fácil de hacer esto?

EDITAR:

Para ser más descriptivo. Digamos que hubo un predicado (biblioteca) partition_point/4 :

partition_point(Pred_1, List, Before, After) :-
    partition_point_1(List, Pred_1, Before, After).

partition_point_1([], _, [], []).
partition_point_1([H|T], Pred_1, Before, After) :-
    (   call(Pred_1, H)
    ->  Before = [H|B],
        partition_point_1(T, Pred_1, B, After)
    ;   Before = [],
        After = [H|T]
    ).

(No me gusta el nombre pero podemos vivir con él por ahora)

Entonces:

find_min_4(Min, As) :-
    setof(B-A, foo(A, B), [Min-X|Rest]),
    partition_point(is_min(Min), [Min-X|Rest], Min_pairs, _),
    pairs_values(Min_pairs, As).

is_min(Min, Min-_).

?- find_min_4(Min, As).
Min = 2,
As = [b, e, h].

Answer 1

¿Cuál es el enfoque idiomático para esta clase de problemas?

¿Hay alguna manera de simplificar el problema?

Muchas de las siguientes observaciones podrían agregarse a muchos programas aquí en SO.

Nombres imperativos

Cada vez que escribe un nombre imperativo para algo que es una relación, reducirá su comprensión de las relaciones. No mucho, solo un poquito. Muchos modismos comunes de Prolog como append/3 no dan un buen ejemplo. Piense en append(As,As,AsAs) . El primer argumento de find_min(Min, As) es el mínimo. Entonces minimum_with_nodes/2 podría ser un mejor nombre.

findall/3

No use findall/3 menos que los usos se verifiquen rigurosamente, esencialmente todo debe ser molido. En tu caso sucede que funciona. Pero una vez que generalices un poco foo/2 , perderás. Y eso es frecuentemente un problema: escribes un pequeño programa; Y parece funcionar. Una vez que te mueves a las más grandes, el mismo enfoque ya no funciona. findall/3 es (en comparación con setof/3 ) como un toro en una tienda de porcelana rompiendo el fino tejido de variables compartidas y cuantificación. Otro problema es que la falla accidental no conduce a la falla de findall/3 que a menudo lleva a casos extraños y difíciles de imaginar.

Programa inestable, demasiado específico

Otro problema también está relacionado con findall/3 . Su programa es tan específico que es bastante improbable que lo pruebe alguna vez. Y los cambios marginales invalidarán sus pruebas. Así que pronto te rendirás para realizar las pruebas. Veamos qué es específico: principalmente la relación foo/2 . Sí, solo un ejemplo. Piense en cómo configurar una configuración de prueba donde foo/2 puede cambiar. Después de cada cambio (escribir un nuevo archivo) deberá volver a cargar el programa. Esto es tan complejo, es probable que nunca lo hagas. Supongo que no tienes un arnés de prueba para eso. Plunit para uno, no cubre tales pruebas. Como regla general: si no puede probar un predicado en el nivel superior, nunca lo hará. Considere en su lugar

minimum_with(Rel_2, Min, Els)

Con tal relación, ahora puede tener un xfoo/3 generalizado con un parámetro adicional, por ejemplo:

xfoo(o, A,B) :-
   foo(A,B).
xfoo(n, A,B) :-
   newfoo(A,B).

y, naturalmente, obtienes dos respuestas para minimum_with(xfoo(X), Min, Els) . Si hubiera utilizado findall/3 lugar de setof/3 , ya tendría problemas serios. O simplemente en general: minmum_with(/A^B^member(AB, [x-10,y-20]), Min, Els) . Para que pueda jugar en el nivel superior y producir muchos casos de prueba interesantes.

Casos fronterizos no verificados

Su versión 3 es claramente mi enfoque preferido, sin embargo, todavía hay algunas partes que pueden mejorarse. En particular, si hay respuestas que contienen variables como mínimo. Estos deben ser revisados.

Y ciertamente, también setof/3 tiene sus límites. E idealmente los probarías. Las respuestas no deben contener restricciones, en particular no en las variables relevantes. Esto muestra cómo setof/3 tiene ciertos límites. Después de la fase pionera, SICStus produjo muchos errores para las restricciones en tales casos (mediados de la década de 1990), que luego cambió para ignorar las restricciones en los elementos integrados que no pueden manejarlos. SWI, por otro lado, hace cosas completamente indefinidas aquí. A veces las cosas se copian, a veces no. Como ejemplo, tome: setof(A, ( A in 1..3 ; A in 3..5 ), _) y setof(t, ( A in 1..3 ; A in 3.. 5 ), _) .

Al envolver el objetivo, esto se puede evitar.

call_unconstrained(Goal_0) :-
   call_residue_vars(Goal_0, Vs),
   ( Vs = [] -> true ; throw(error(representation_error(constraint),_)) ).

Sin embargo, tenga en cuenta que SWI tiene restricciones espurias:

?- call_residue_vars(all_different([]), Xs).
Xs = [_G1130].

No está claro si esta es una característica mientras tanto. Ha estado allí desde la introducción de call_residue_vars/2 aproximadamente 5 años.

Answer 2

No creo que la biblioteca (agregado) cubra su caso de uso. agregado (min) permite un testigo:

min (Expr, Witness) Un término min (Min, Witness), donde Min es la versión mínima de Expr sobre todas las soluciones, y Witness es cualquier otra plantilla aplicada a las soluciones que produjeron Min. Si varias soluciones proporcionan el mismo mínimo, Witness corresponde a la primera solución.

Hace algún tiempo, escribí una pequeña ''biblioteca'', lag.pl , con predicados para agregar con poca sobrecarga, de ahí el nombre (LAG = Agregado lineal). He agregado un fragmento, que maneja su caso de uso:

integrate(min_list_associated, Goal, Min-Ws) :-
    State = term(_, [], _),
    forall(call(Goal, V, W),    % W stands for witness
        (    arg(1, State, C),  % C is current min
             arg(2, State, CW), % CW are current min witnesses
             (   ( var(C) ; V @< C )
             ->  U = V, Ws = [W]
             ;   U = C,
                 (   C == V
                 ->  Ws = [W|CW]
                 ;   Ws = CW
                 )
             ),
             nb_setarg(1, State, U),
             nb_setarg(2, State, Ws)
        )),
    arg(1, State, Min), arg(2, State, Ws).

Es una extensión simple de integración (min) ... El método de comparación es seguramente cuestionable (utiliza un operador menos general para la igualdad), podría valer la pena adoptar una llamada convencional como la adoptada para predsort / 3. En cuanto a la eficiencia, aún mejor sería codificar el método de comparación como una opción en el ''selector de funciones'' (min_list_associated en este caso)

edite gracias @false y @Boris por corregir el error relativo a la representación del estado. Llamar a nb_setarg(2, State, Ws) realidad cambia el término ''forma, cuando se usó State = (_,[],_) . Actualizará el repositorio de github en consecuencia ...

Answer 3

Usando la library(pairs) y [ sort/4 ], esto se puede escribir simplemente como:

?- bagof(B-A, foo(A, B), Ps),
   sort(1, @=<, Ps, Ss), % or keysort(Ps, Ss)
   group_pairs_by_key(Ss, [Min-As|_]).
Min = 2,
As = [b, e, h].

Esta llamada a sort/4 se puede reemplazar con keysort/2 , pero con sort/4 también se pueden encontrar, por ejemplo, los primeros argumentos asociados con el segundo argumento más grande: simplemente use @>= como segundo argumento.

Esta solución probablemente no sea tan eficiente en tiempo y espacio como las otras, pero puede ser más fácil de asimilar.

Pero hay otra forma de hacerlo por completo:

?- bagof(A, ( foo(A, Min), /+ ( foo(_, Y), Y @< Min ) ), As).
Min = 2,
As = [b, e, h].