Il più generale vincolo di ordine superiore che descrive una sequenza di numeri interi ordinati rispetto a una relazione

In CLP (FD), abbiamo spesso bisogno di dichiarare: “Questa è una lista di interi e variabili di dominio finite in ordine (talvolta: strettamente ) ascendente / discendente”.

Esiste un sistema CLP (FD) che fornisce un vincolo incorporato generale (parametrizzabile) per questa attività?

SWI-Prolog fornisce un vincolo chiamato chain/2 , che è simile a quello che sto cercando. Tuttavia, il nome è leggermente troppo specifico per comprendere tutte le relazioni che il vincolo può descrivere (esempio: #< non è un ordine parziale ma ammissibile in chain/2 , che porta alla sequenza – preso come un insieme di numeri interi – che non conta più come una catena come definita nella teoria dell’ordine matematico). Quindi, il nome non descrive completamente ciò che il vincolo effettivamente implementa.

Si prega di fornire la definizione più generale rispetto ai consueti vincoli CLP (FD) binari – o un sottoinsieme adatto che contenga almeno #< , #> , #=< e #>=incluso il nome proprio in base alla struttura algebrica il il vincolo definisce. La condizione imposta è che il vincolo descriva una struttura matematica reale che ha un nome proprio nella letteratura.

Per prima cosa, considera 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_([], _). connex_([L|Ls], Relation_2) :- foldl(adjacent(Relation_2), Ls, L, _). adjacent(Relation_2, X, Prev, X) :- call(Relation_2, Prev, X). 

Casi di esempio:

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

Si noti che sarebbe anche ammissibile consentire #\= , perché la relazione descriverebbe ancora un collegamento come noto nella teoria dell’ordine matematico. Quindi, il codice sopra non è il più generale rispetto ai soliti vincoli CLP (FD) binari.

Hoogle non è stato molto utile, ma Hayoo lo è!

foldcmpl

quindi questa è una forma speciale di piega per una lista, ma non applica i tempi di length list ma una volta di meno.

isSortedBy

non è del tutto generale nel suo nome, ma nella sua firma. Forse insistere sul nome più generico non è così utile. Altrimenti abbiamo solo quadro dappertutto?

La definizione dice:

La funzione isSortedBy restituisce True se il predicato restituisce true per tutte le coppie adiacenti di elementi nell’elenco.

Forse: all_adjacent_pairs(R_2, Xs) . che suona un po ‘dopo avere un costrutto ciclico che ha adjacent_pair come un qualche modificatore.

Questo è ispirato da una serie di idiomi funzionali di ordine superiore che ho implementato una volta. Allora ho trovato i casi angosciosi agonizzante, lo faccio ancora oggi 🙂 Inoltre, trovare buoni nomi è sempre un problema …

Considera meta-predicato 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). 

Usi del campione:

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

Sono a conoscenza della spaccatura nei casi d’angolo As = [] e As = [_] , tuttavia sento che questo è il più vicino a “per tutti gli elementi della lista adiacente”.

Inoltre, tutto ciò può essere facilmente esteso:

  • giù per mapadj/2 (simile a chain/2 , ad eccezione del type-check con liste singleton)
  • lateralmente, con un ulteriore argomento di stato, a foldadjl/n , scanadjl/n

Per quanto riguarda i nomi: IMO il suffisso l / r è richiesto con fold / scan , ma non con la map .


Modifica 2015-04-26

Ecco che arriva il già citato 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). 

Modifica 2015-04-27

Ecco il meta-predicato splitlistIfAdj/3 , basato su if_/3 che è stato proposto in una precedente risposta sulla reificazione.

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

Per mostrarlo in uso definiamo dif/3 esattamente allo stesso modo di (=)/3 ma con valore di verità capovolto:

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

Ora li usiamo in tandem:

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

Cosa succede se generalizziamo alcuni elementi della lista? Riceviamo più risposte con i giusti obiettivi in ​​attesa?

Innanzitutto, un piccolo esempio:

 ?- 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 esempio un po ‘più grande che riguarda le due variabili 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]]. 

Modifica 2015-05-05

Ecco 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 del campione:

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

Modifica 2015-05-15

splitlistIf/3 e avanti, … ecco 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))). 

Usiamolo:

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

Abbastanza nello stesso modo di mapadj/4 presentato in una risposta precedente … forse il nome è migliore.

 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 del campione:

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

Dove potrebbe portarci?

  • forallAdj => existAdj
  • forse varianti con index ( forallAdjI , existAdjI ) come in Collections.List Module (F #)
  • findfirstAdj / pickfirstAdj piace anche F # find / pick