prolog clpfd topology meta-predicate

prolog - La restricción más general de orden superior que describe una secuencia de enteros ordenados con respecto a una relación



clpfd topology (3)

En CLP (FD), con frecuencia necesitamos indicar: "Esta es una lista de enteros y variables de dominio finito en (a veces: estrictamente ) orden ascendente / descendente".

¿Hay algún sistema CLP (FD) que proporcione una restricción incorporada general (parametrizable) para esta tarea?

SWI-Prolog proporciona una restricción llamada chain/2 , que es similar a lo que estoy buscando. Sin embargo, el nombre es ligeramente demasiado específico para abarcar todas las relaciones que la restricción puede describir (ejemplo: #< no es un orden parcial pero admisible en chain/2 , lo que lleva a la secuencia - tomada como un conjunto de enteros - ya no cuenta como una cadena como se define en la teoría de orden matemática). Por lo tanto, el nombre no describe completamente lo que la restricción realmente implementa.

Proporcione la definición más general con respecto a las restricciones binarias CLP (FD) habituales, o un subconjunto adecuado que contenga al menos #< , #> , #=< y #>= - incluido el nombre propio según la estructura algebraica restricción define. La condición impuesta es que la restricción describa una estructura matemática real que tiene un nombre propio en la literatura.

Para empezar, considere con SICStus Prolog o SWI:

:- use_module(library(clpfd)). connex(Relation_2, List) :- connex_relation(Relation_2), connex_(List, Relation_2). connex_relation(#=). connex_relation(#<). connex_relation(#=<). connex_relation(#>). connex_relation(#>=). connex_([], _). connex_([L|Ls], Relation_2) :- foldl(adjacent(Relation_2), Ls, L, _). adjacent(Relation_2, X, Prev, X) :- call(Relation_2, Prev, X).

Ejemplos de casos:

?- connex(#<, [A,B,C]). A#=<B+-1, B#=<C+-1. ?- connex(#=, [A,B,C]). A = B, B = C, C in inf..sup. ?- maplist(connex(#<), [[A,B],[C,D]]). A#=<B+-1, C#=<D+-1.

Nótese que incluso sería admisible permitir #/= , porque la relación aún describiría una conexión como se conoce en la teoría de orden matemática. Por lo tanto, el código anterior no es el más general con respecto a las restricciones binarias CLP (FD) habituales.

Esto está inspirado en una caja de herramientas de modismos funcionales de orden superior que una vez implementé. En aquel entonces, encontré los casos de las esquinas agonizantes, todavía lo hago hoy :) Además, encontrar buenos nombres siempre es un problema ...

Considere el meta-predicado mapadj/4 :

mapadj(Relation_4,As,Bs,Cs) :- list_list_list_mapadj(As,Bs,Cs,Relation_4). list_list_list_mapadj([],[],[],_). list_list_list_mapadj([A|As],Bs,Cs,Relation_4) :- list_prev_list_list_mapadj(As,A,Bs,Cs,Relation_4). list_prev_list_list_mapadj([],_,[],[],_). list_prev_list_list_mapadj([A1|As],A0,[B|Bs],[C|Cs],Relation_4) :- call(Relation_4,A0,A1,B,C), list_prev_list_list_mapadj(As,A1,Bs,Cs,Relation_4).

Usos de muestra:

z_z_sum_product(X,Y,Sum,Product) :- Sum #= X + Y, Product #= X * Y. :- mapadj(z_z_sum_product,[], [], []). :- mapadj(z_z_sum_product,[1], [], []). :- mapadj(z_z_sum_product,[1,2], [3], [2]). :- mapadj(z_z_sum_product,[1,2,3], [3,5], [2,6]). :- mapadj(z_z_sum_product,[1,2,3,4],[3,5,7],[2,6,12]).

Soy consciente de la grieta en los casos de esquina As = [] y As = [_] , aún siento que esto es lo más cercano a "para todos los ítems de la lista adyacente".

Además, todo esto puede extenderse fácilmente:

  • hasta mapadj/2 (similar a chain/2 , a excepción de la verificación de tipo con listas de singleton)
  • de lado, con un argumento de estado adicional, para foldadjl/n , scanadjl/n

En cuanto a los nombres: IMO, el sufijo l / r es obligatorio con fold / scan , pero no con map .

Editar 2015-04-26

Aquí viene el antes mencionado foldadjl/4 :

foldadjl(Relation_4,Xs) --> list_foldadjl(Xs,Relation_4). list_foldadjl([],_) --> []. list_foldadjl([X|Xs],Relation_4) --> list_prev_foldadjl(Xs,X,Relation_4). list_prev_foldadjl([],_,_) --> []. list_prev_foldadjl([X1|Xs],X0,Relation_4) --> call(Relation_4,X0,X1), list_prev_foldadjl(Xs,X1,Relation_4).

Editar 2015-04-27

Aquí viene meta-predicate splitlistIfAdj/3 , basado en if_/3 que fue propuesto en una respuesta previa sobre reificación.

split_if_adj(P_3,As,Bss) :- splitlistIfAdj(P_3,As,Bss). splitlistIfAdj(P_3,As,Bss) :- list_split_(As,Bss,P_3). list_split_([],[],_). list_split_([X0|Xs], [Cs|Bss],P_3) :- list_prev_split_(Xs,X0,Cs,Bss, P_3). list_prev_split_([], X, [X],[],_). list_prev_split_([X1|Xs],X0,[X0|Cs],Bss,P_3) :- if_(call(P_3,X0,X1), (Cs = [], Bss = [Cs0|Bss0]), (Cs = Cs0, Bss = Bss0)), list_prev_split_(Xs,X1,Cs0,Bss0,P_3).

Para mostrarlo en uso, definamos dif/3 exactamente de la misma manera que (=)/3 pero con el valor de verdad invertido:

dif(X, Y, R) :- X == Y, !, R = false. dif(X, Y, R) :- ?=(X, Y), !, R = true. % syntactically different dif(X, Y, R) :- X /= Y, !, R = true. % semantically different dif(X, Y, R) :- R == false, !, X = Y. dif(X, X, false). dif(X, Y, true) :- dif(X, Y).

Ahora los usamos en tándem:

?- splitlistIfAdj(dif,[1,2,2,3,3,3,4,4,4,4],Pss). Pss = [[1],[2,2],[3,3,3],[4,4,4,4]]. % succeeds deterministically

¿Qué pasa si generalizamos algunos elementos de la lista? ¿Recibimos respuestas múltiples con los objetivos pendientes correctos?

Primero, un pequeño ejemplo:

?- splitlistIfAdj(dif,[1,X,2],Pss). X = 1, Pss = [[1,1],[2]] ; X = 2, Pss = [[1],[2,2]] ; dif(X,1),dif(X,2), Pss = [[1],[X],[2]].

Un ejemplo algo más grande que involucra las dos variables X e Y

?- splitlistIfAdj(dif,[1,2,2,X,3,3,Y,4,4,4],Pss). X = 2, Y = 3, Pss = [[1],[2,2,2],[3,3,3],[4,4,4]] ; X = 2, Y = 4, Pss = [[1],[2,2,2],[3,3],[4,4,4,4]] ; X = 2, dif(Y,3),dif(Y,4), Pss = [[1],[2,2,2],[3,3],[Y],[4,4,4]] ; X = Y, Y = 3, Pss = [[1],[2,2],[3,3,3,3],[4,4,4]] ; X = 3, Y = 4, Pss = [[1],[2,2],[3,3,3],[4,4,4,4]] ; X = 3, dif(Y,3),dif(Y,4), Pss = [[1],[2,2],[3,3,3],[Y],[4,4,4]] ; dif(X,2),dif(X,3), Y = 3, Pss = [[1],[2,2],[X],[3,3,3],[4,4,4]] ; dif(X,2),dif(X,3), Y = 4, Pss = [[1],[2,2],[X],[3,3],[4,4,4,4]] ; dif(X,2),dif(X,3), dif(Y,3),dif(Y,4), Pss = [[1],[2,2],[X],[3,3],[Y],[4,4,4]].

Editar 2015-05-05

Aquí está la tpartition/4 :

tpartition(P_2,List,Ts,Fs) :- tpartition_ts_fs_(List,Ts,Fs,P_2). tpartition_ts_fs_([],[],[],_). tpartition_ts_fs_([X|Xs0],Ts,Fs,P_2) :- if_(call(P_2,X), (Ts = [X|Ts0], Fs = Fs0), (Ts = Ts0, Fs = [X|Fs0])), tpartition_ts_fs_(Xs0,Ts0,Fs0,P_2).

Uso de muestra:

?- tpartition(=(0), [1,2,3,4,0,1,2,3,0,0,1], Ts, Fs). Ts = [0, 0, 0], Fs = [1, 2, 3, 4, 1, 2, 3, 1].

Editar 2015-05-15

Una y otra vez, ... aquí está la lista splitlistIf/3 :

split_if(P_2,As,Bss) :- splitlistIf(P_2,As,Bss). splitlistIf(P_2,As,Bss) :- list_pred_split(As,P_2,Bss). list_pred_split([],_,[]). list_pred_split([X|Xs],P_2,Bss) :- if_(call(P_2,X), list_pred_split(Xs,P_2,Bss), (Bss = [[X|Ys]|Bss0], list_pred_open_split(Xs,P_2,Ys,Bss0))). list_pred_open_split([],_,[],[]). list_pred_open_split([X|Xs],P_2,Ys,Bss) :- if_(call(P_2,X), (Ys = [], list_pred_split(Xs,P_2,Bss)), (Ys = [X|Ys0], list_pred_open_split(Xs,P_2,Ys0,Bss))).

Vamos a usarlo:

?- splitlistIf(=(x),[x,1,2,x,1,2,3,x,1,4,x,x,x,x,1,x,2,x,x,1],Xs). Xs = [[1, 2], [1, 2, 3], [1, 4], [1], [2], [1]].

Hoogle no fue muy útil, ¡pero Hayoo sí!

foldcmpl

así que esta es una forma especial de fold para una lista, pero no aplica los tiempos de length list , pero una vez menos.

isSortedBy

no es completamente general en su nombre, sino en su firma. Tal vez insistir en el nombre más general no es tan útil. De lo contrario, solo tenemos entidades en todas partes?

La definición dice:

La función isSortedBy devuelve True iff el predicado devuelve verdadero para todos los pares adyacentes de elementos en la lista.

Quizás: all_adjacent_pairs(R_2, Xs) . que suena un poco después de tener una construcción de bucle que tiene adjacent_pair como un modificador.

Muy similar al mapadj/4 presentado en una respuesta anterior ... tal vez el nombre sea mejor.

forallAdj(P_2,Xs) :- list_forallAdj(Xs,P_2). list_forallAdj([],_). list_forallAdj([X|Xs],P_2) :- list_forallAdj_prev(Xs,P_2,X). list_forallAdj_prev([],_,_). list_forallAdj_prev([X1|Xs],P_2,X0) :- call(P_2,X0,X1), list_forallAdj_prev(Xs,P_2,X1).

Uso de muestra:

:- use_module(library(clpfd)). :- use_module(library(lambda)). ?- Ls = [0,_,_,_,_,_], forallAdj(/X0^X1^(X0 + 1 #= X1), Ls). Ls = [0, 1, 2, 3, 4, 5].

¿A dónde nos puede llevar eso?

  • forallAdj => existAdj
  • tal vez variantes con index ( forallAdjI , existAdjI ) como en Collections.List Module (F #)
  • findfirstAdj / pickfirstAdj también me gusta F # find / pick