intervals-general Crate RFC

• 开始日期 2018 年 10 月 13 日
• 最后编辑 2019 年 3 月 24 日
• 工作正在进行中
• Scott Moeller

摘要

添加一个名为 intervals-general 的新 Crate，它支持严格的区间定义（例如，类型强制表示所有实数区间类型），区间集合和常见的区间操作，同时操作泛型边界数据类型，只要满足所需的特征（例如，可以使用 units of measure 作为边界）。

许可

根据以下任一许可授权

• Apache 许可证第 2 版，(LICENSE-APACHE 或 http://apache.ac.cn/licenses/LICENSE-2.0)
• MIT 许可证 (LICENSE-MIT 或 http://opensource.org/licenses/MIT)

由您选择。

贡献

除非您明确声明，否则根据 Apache-2.0 许可证定义的，您有意提交的任何贡献，都应按上述方式双重许可，不附加任何其他条款或条件。

动机

在编写一个支持例如步进函数表示（强制使用度量单位）的模拟工具时，我发现自己在寻找可以接受 uom 类型并且能够充分表达以便在常见区间操作（如并集、交集、补集）下闭合的区间表示。没有找到满足这些标准的 crate，我研究了其他语言实现，并开始编写 intervals-general 的提案。

需求

该库的需求如下

1. 通过泛型提供对具有边界数据类型的区间支持
2. 支持开、闭和半开区间的支持
3. 支持类型强制的空区间的表示
4. 支持类型强制的无界区间的表示

其他需求

1. 支持no_std
2. 不使用panic，assert
3. 通过设计最小化错误处理
4. 使库难以错误使用

需求推理

作为一个激励案例，考虑使用这个区间库来构建用于物理模拟的阶梯函数库。现在我们暂时不考虑使用区间表示来支持阶梯函数库的设计决策（例如，与“变化点”注释相比）。在这种环境下，你可能想要

• 表示一个信号，其定义域覆盖了某个单位中的(-inf, to +inf)
• 构成域的阶梯函数区间集合是连续的

在这个空间中，仅使用闭区间是不切实际的（你也不能包括无界区间，也不能定义一个集合，其定义域是连续的，例如在实数中，但其区间不重叠）。仅使用开集也存在问题（不能定义一个集合，其定义域是连续的，例如在实数中，但每个区间都是开的）。如果你坚持仅使用左半开或右半开区间，你可以定义不重叠且连续的区间集合 - 但你现在无法清楚地表示两种风味（例如，仅左半开区间阻止你使用+inf边界，迫使作者选择一个“足够大的”偏移量作为右侧闭界，以便在他们的用例中近似+inf）。最后，请注意，如果支持左半开和右半开边界类型的混合，那么在交集下，必须支持的区间类型闭合集变为{开，闭，左半开，右半开，左半开无界，右半开无界，单点，空集}。省略任何这些风味都需要引入错误处理或异常 - 我强烈希望避免这种情况。因此，希望支持完整的区间类型集（参见proofwiki:Real Interval Types）。

详细设计

术语选择

• 建议使用区间而不是范围
  • 使数学构造的意图更清晰
  • 避免与编程语言中出现的许多范围概念混淆
• 建议使用边界而不是端点或极限
  • 尽管我现在看不到任何优势
• 建议使用左边界和右边界
  • 这比例如min，max等更符合区间中心思想

支持的区间操作

1. 并集
2. 交集
3. 补集
4. 左部分比较
5. 右部分比较

基于这些，可以派生出许多有用的实用工具。以下是一些示例

1. 元素包含：[1, 1]是否包含在[-1, 5]中？ -> 集合的并集等于[1, 1]？ -> true
2. 区间包含：是否(1, 2]包含在[-1, 5]中？ -> 集合的并集等于(1,2]? -> true
3. 按（左|右）边界对区间进行排序

区间边界类型表示

区间通过枚举表示，代表所有开区间、闭区间和半开区间的组合及其射线变体（一个边界在正负无穷）。有关包含左边界和右边界枚举的表示方式的评估，请参见下面的替代讨论（以下内容）。

对于包含有界左和右端点的区间，处理边界参数的设计挑战随之而来 - 尤其是左右边界值的交互，这些值的顺序取决于区间类型。为了通过简单的枚举实现区间表示和构建，带有左右边界值的区间将首先构建一个BoundPair结构体（通过BoundPair::new() - 返回一个可以进行错误检查的结果）。因此，不能构建无效的区间枚举。

#[derive(Debug, Copy, Clone, PartialEq)]
pub struct BoundPair<T> {
    left: T,
    right: T,
}

区间枚举变体分类法来自proofwiki:实数区间类型

#[derive(Debug, Copy, Clone, PartialEq)]
pub enum Interval<T> {
    Closed { bound_pair: BoundPair<T> },        // [a, b]
    Open { bound_pair: BoundPair<T> },          // (a, b)
    LeftHalfOpen { bound_pair: BoundPair<T> },  // (a, b]
    RightHalfOpen { bound_pair: BoundPair<T> }, // [a, b)
    UnboundedClosedRight { right: T },          // (-inf, a]
    UnboundedOpenRight { right: T },            // (-inf, a)
    UnboundedClosedLeft { left: T },            // [a, inf)
    UnboundedOpenLeft { left: T },              // (a, inf)
    Singleton { at: T },                        // [a]
    Unbounded,                                  // (-inf, inf)
    Empty,                                      // Empty Interval
}

边界数据类型所需的特性

• T: std::cmp::PartialOrd

这是为了支持区间边界的比较，这是许多区间操作所必需的。

缺点

计算复杂性

由于动态运行时表示和支持跨区间类型操作（例如，包括对类型强制的开区间、闭区间和半开区间的支持，以及对类型强制的开无限边界的表示），区间操作的计算复杂度增加。一个C++库提供了运行时动态或静态区间支持（见Boost区间容器库（以下内容）。原型化区间操作以比较与简单的区间表示的性能可能是有教育意义的，例如，对于所有区间都是左半开，并且不支持通用区间。

替代方案

现有的Crates

这个领域存在现有的Crates，如果为现有生态系统做出贡献是合理的路径，那么创建一个新的crate是不合适的。因此，我将列举我找到的crate - 以及为什么我认为它们与动机中列出的目标不一致。我还会指出这些crate提供的可能对通用区间有吸引力的功能。在继续进行通用区间之前，我会联系这些crate的所有者并收集他们的反馈。

区间算术库 - 支持仅限闭区间边界，单例和空（通过IsSingleton，IsEmpty）。仅支持原始类型的边界（没有uom支持）。使用从原始边界极值抽取的哨兵值（例如，i8的-128 -> [inf）来近似无界区间。

Interval - 在0.0.1版时被放弃

其他语言的现有库

Haskell区间包 - 仅支持开区间和无界区间。包含有关区间操作的良好集合，包括（成员，下确界，上确界，宽度，分割，交集，包络，距离，膨胀，收缩，缩放，比较以及各种实用区间构造函数）。

Haskell IntervalMap包 - 集合和映射实现，支持区间作为键，并提供了高效获取包含一个点的所有区间子集、交集一个区间等功能。

Boost区间容器库 - ICL - 支持静态编译时类型right_open_interval、left_open_interval、closed_interval、open_interval（全部有界）。还支持动态运行时的discrete_interval和continuous_interval，可以使用左开或右开规范构建。静态编译时变体的提供很有趣，因为它在消费者坚持使用单个区间类型的情况下可以减少计算负担，并可以确保在只想使用例如左开区间的应用程序中使用一致的区间类型。连续区间支持字符串和日期，这是一个有趣的概念。还实现了区间集和区间映射。

区间边界类型的替代表示

我探索了多个用于库中所需的类型强制表示的选项，包括

1. 一个不带左右绑定的枚举边界，能够表示开无限边界（例如，Closed<数据类型>、OpenFinite<数据类型>、OpenInfinite）
2. 一个不带左右绑定的枚举边界，无法表示开无限边界（例如，Closed<数据类型>、Open<数据类型>），其中<数据类型>支持类型强制无限表示
3. 一个带有左右绑定的枚举边界（例如，LeftOpenFinite<数据类型>、LeftOpenInfinite、LeftClosed、RightOpenFinite、RightOpenInfinite、RightClosed）

enum LeftBound<T> {
    Unbounded,
    OpenBounded(T),
    ClosedBounded(T),
}

enum RightBound<T> {
    Unbounded,
    OpenBounded(T),
    ClosedBounded(T),
}

在区间创建时对边界的替代处理

对于具有左右边界的区间，用户可能会提供无效的值。例如，左边界大于右边界，或者边界相等（在这种情况下，这应该是一个单点区间）。在这个库中的目标是捕捉这样的错误，同时让库用户知道，同时最大限度地减少这种错误的机会——并且不抛出异常。上述设计建议创建一个单独的结构（BoundaryPair）进行错误检查，然后将其传递给需要两个边界值的区间枚举构造函数。

除了上述应用的方法之外，还有关于边界无效或不适用于区间变体时详细行为的问题。考虑的替代方案包括

1. 接收左(l)和右(r)边界
   • 如果 !(l < r) 返回错误
   • 否则返回 Left(l), Right(r)
2. 接收 a 和 b 边界
   • 如果 a == b 返回 Singleton(a)
   • 如果 a < b 返回 Left(a), Right(b)
   • 如果 a > b 返回 Left(b), Right(a)
3. 接收左(l)边界和宽度(w)
   • 如果 w < 0 返回错误
   • 如果 w == 0 返回 Singleton(l)
   • 否则返回 Left(l), Right(l + w)
4. 接收边界 a 和宽度(w)
   • 如果 w == 0 返回 Singleton(a)
   • 如果 w > 0 返回 Left(a), Right(a+w)
   • 如果 w < 0 返回 Left(a - w), Right(a)
5. 对无效区间枚举变体的支持

问题在于是否提供一个库来避免错误，只要可以构建有效的区间即可，或者是否应该为程序员的边界未按要求排序提供防御。审查野外的其他区间库，一些根本不提供任何验证（例如，Haskell IntervalMap包，Boost Interval Container Library - ICL）。一些在边界顺序错误时应用边界反转（例如，Haskell intervals包）。一些在边界顺序不正确时断言（例如，Rust Honest Intervals）。

未解决的问题

未解决的舍入模式问题

根据应用于区间的算术运算，舍入误差可能导致一组区间超出预期地突变。我已确信，舍入问题并不比您从一般的浮点使用表示（即，似乎没有出现与区间特定的刺痛）更严重 - 特别是即使在缩放（例如 *2.5 [1, 2) = [2.5, 5.0)）的情况下，在缩放之前在实域中连续的区间集合在缩放之后仍然在实域中保持连续。因此，舍入误差不会导致连续区间的集合在某些域（同样适用于对区间的偏移修改，例如 +2.5 [1, 2) = [3.5, 4.5)）变得不连续。然而，如果区间的宽度是一个希望依赖的属性（例如 区间算术） - 那么舍入模式是一个重要的考虑因素，因为它可能会破坏区间在突变下的预期属性。按照目前的定义，这个区间库可能不支持区间算术的使用。

未解决的静态区间类型支持

在上述Boost区间容器库中，提供了两种区间变体（静态编译时强制单一类型，或动态运行时类型支持混合区间类型）。静态编译时单一类型的缺点是某些操作不受支持（例如，补码） - 并且许多实际的区间表示需要混合区间类型（例如，表示步函数域的从 -inf 到 +inf 的区间集合）。

未解决的溢出行为

没有尝试检测溢出或下溢 - 这可以完成吗（将溢出/下溢转换为无界区间？）

资源

• 浮点区间算术运算
• 区间算术：从原理到实现
• 区间的并集、交集和补集
• 区间 @ Wolfram