描述关于关系排序的整数序列的最一般的高阶约束 [英] Most general higher-order constraint describing a sequence of integers ordered with respect to a relation

问题描述

在 CLP(FD) 中，我们经常需要声明:这是按(有时:严格)升序/降序排列的整数和有限域变量的列表."

In CLP(FD), we frequently need to state: "This is a list of integers and finite domain variables in (sometimes: strictly) ascending/descending order."

是否有任何 CLP(FD) 系统为此任务提供通用(可参数化)内置约束?

Is there any CLP(FD) system that provides a general (parametrisable) built-in constraint for this task?

SWI-Prolog 提供了一个名为 chain/2 的约束，这与我正在寻找的类似.但是，名称有点过于具体，无法包含约束可以描述的所有关系(例如:#< 不是偏序，但在 chain/2 中是可接受的，前导到序列—被视为一组整数—不再算作数学顺序理论中定义的链).因此，名称并不能完全描述约束实际实现的内容.

SWI-Prolog provides a constraint called chain/2, which is similar to what I am looking for. However, the name is slightly too specific to encompass all relations that the constraint can describe (example: #< is not a partial order but admissible in chain/2, leading to the sequence — taken as a set of integers — no longer counting as a chain as defined in mathematical order-theory). Hence, the name does not fully describe what the constraint actually implements.

请给出关于通常二进制 CLP(FD) 约束的最一般定义 —或至少包含 #<、#>、#=< 和 #>= —包括根据约束定义的代数结构的专有名称.施加的条件是该约束描述了一个在文献中具有专有名称的实际数学结构.

Please give the most general definition with respect to the usual binary CLP(FD) constraints — or a suitable subset that contains at least #<, #>, #=< and #>= — including the proper name according to the algebraic structure the constraint defines. The condition imposed is that the constraint describe an actual mathematical structure that has a proper name in the literature.

首先，考虑使用 SICStus Prolog 或 SWI:

As a start, consider with SICStus Prolog or 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).

示例案例:

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

请注意，允许 #= 甚至是可以接受的，因为这种关系仍然描述了数学顺序理论中已知的连接.因此，就通常的二进制 CLP(FD) 约束而言，上述代码并不是最通用的.

Notice that it would even be admissible to allow #=, because the relation would still describe a connex as known in mathematical order-theory. Hence, the code above is not most general with respect to the usual binary CLP(FD) constraints.

推荐答案

Hoogle 不是很有用，但是 喂！

Hoogle was not very useful, but Hayoo is!

所以这是列表的一种特殊折叠形式，但它不会应用 length list 次，而是应用少一次.

so this is a special form of fold for a list, but it does not apply length list times but one time less.

在它的名字上并不完全通用，但在它的签名上.也许坚持使用最通用的名称并没有太大帮助.否则我们只是到处都是实体?

is not entirely general in its name, but in its signature. Maybe insisting on the most general name is not that helpful. Otherwise we just have entities all over?

定义如下:

如果谓词对列表中的所有相邻元素对返回 true，则 isSortedBy 函数返回 True.

The isSortedBy function returns True iff the predicate returns true for all adjacent pairs of elements in the list.

也许:all_adjacent_pairs(R_2, Xs).在有一个以 adjacent_pair 作为修饰符的循环构造之后，这听起来有点.

Maybe: all_adjacent_pairs(R_2, Xs). which sounds a bit after having a looping construct that has adjacent_pair as some modifier.

这篇关于描述关于关系排序的整数序列的最一般的高阶约束的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！