是否可以根据要比较的数据生成相等函数?

Is it possible to generate an equality function based on the data to be compared?

提问人:X10D 提问时间:5/4/2020 最后编辑:X10D 更新时间:12/10/2021 访问量:238

问:

如果两个布尔值相同,则两个布尔值相等,两个数字相似。如果两个集合具有相同的元素,则它们相等。在检查两组是否相等的情况下,我们可以使用以下方案/球拍函数:

(define (same-set? l1 l2)
  (and (subset? l1 l2) (subset? l2 l1)))

如何自动生成这样的函数?可以为任意数据类型生成吗?

等价关系的基本性质是:

替换性质:对于任何量 a 和 b 以及任何表达式 F(x),如果 a = b,则 F(a) = F(b)(如果两边都有意义,即格式良好)。 一些具体的例子是:

对于任何实数 a、b 和 c,如果 a = b,则 a + c = b + c(这里 F(x) 是 x + c);

对于任何实数 a、b 和 c,如果 a = b,则 a − c = b − c(这里 F(x) 是 x − c);

对于任何实数 a、b 和 c,如果 a = b,则 ac = bc(这里 F(x) 是 xc);

对于任何实数 a、b 和 c,如果 a = b 和 c 不为零,则 a/c = b/c(这里 F(x) 是 x/c)。

反身性质:对于任何量 a,a = a。 对称性质:对于任何量 a 和 b,如果 a = b,则 b = a。 传递性:对于任何量 a、b 和 c,如果 a = b 且 b = c,则 a = c。

是否可以生成遵循上述属性的函数?这够了吗?了解数据类型会有所帮助吗?

如果您对如何改进此问题或标记它有任何想法,请发表评论。

方案 球拍 代码生成 等于 平等

评论

0赞 Raymond Chen 5/4/2020
请使用编程语言进行标记。这是计划吗?口齿伶俐?

答:

-1赞 Richard Topchii 5/4/2020 #1

是的,这绝对是可能的。一些编程语言允许自动相等函数综合。斯威夫特就是这样一个例子。

如果没有自动合成,开发人员必须编写代码来实现相等性,例如,考虑一个结构:

struct Country: Equatable {
  let name: String
  let capital: String
  var visited: Bool

  static func == (lhs: Country, rhs: Country) -> Bool {
    return lhs.name == rhs.name &&
    lhs.capital == rhs.capital &&
    lhs.visited == rhs.visited
  }
}

在 Swift 4.1 及更高版本中,不再需要这样做。编译器会为您生成相等函数:

struct Country: Equatable { // It's enough to just declare that the type is `Equatable` and the compiler do the rest
  let name: String
  let capital: String
  var visited: Bool
}

让我们来测试一下:

let france = Country(name: "France", capital: "Paris", visited: true)
let spain = Country(name: "Spain", capital: "Madrid", visited: true)
if france == spain { ... } // false

更新:

即使在 Swift 4.1 之后,也可以使用自己的自定义逻辑覆盖默认实现。例如:

struct Country: Equatable {
  let name: String
  let countryCode: String
  let capital: String
  var visited: Bool

  static func == (lhs: Country, rhs: Country) -> Bool {
    return lhs.countryCode == rhs.countryCode
  }
}

因此,开发人员始终处于控制之中。相等不会自动合成,开发人员必须添加到结构声明中。如果在此之后他们对默认实现不满意,或者无法推断,则始终可以选择覆盖编译器的意图并提供自定义变体。Equatable

评论

0赞 Richard Topchii 5/4/2020
@tfb由于该语言“无法为您有效地执行此操作”,因此由开发人员使用自动生成 .如果必须基于其他属性进行比较,例如,开发人员有完全的权力在他们自己的实现中仅通过该属性进行比较。编译器在简单的情况下会有所帮助,因此开发人员不必在 80% 的情况下编写代码。这已经是一个了不起的成就了。由于编译器无法推断出这样的复杂逻辑,因此开发人员必须提供此信息。EquatablecountryCodeEquatable
0赞 Richard Topchii 5/4/2020
当然,对于其中的每一个,都可以创建一个方法。或者,定义的自定义运算符。例如 或任何其他任务所需的内容。||=
0赞 Richard Topchii 5/4/2020
为什么会犯错?在 Swift 中,它是一种定义的行为,编译器的行为方式只有一种方式。如果默认实现不合适,开发人员始终可以选择实现自定义实现。因此,大多数时候,语言绝对可以为你做“完全平等的事情”。当他们不能时,可以选择帮助他们。
3赞 Sorawee Porncharoenwase 5/4/2020 #2

如果两个布尔值相同,则两个布尔值相等,两个数字相似。如果两个集合具有相同的元素,则它们相等。

这些是有用的等式,但它们并不是您可以创建的唯一等式。例如,当两个数字的奇偶校验(奇数/偶数)相同时,您可以将它们视为相等。或者,您可以将每个数字都视为彼此相等。

如何自动生成这样的函数?

一般来说,这是不可能的,因为这取决于你的意图。没有人能读懂你的心思。

是否可以生成遵循上述属性的函数?

答案是肯定的。至少,你有 ,它表示每个对象都等于其他每个对象。它满足等价关系属性,尽管它完全没用。(lambda (x y) #t)

对于适用于各种值的非平凡相等,您具有服从等价关系属性的引用相等(如果您使用不安全的 API IIUC,它可能会给您一个奇怪的结果,但这是题外话)。eq?

equal?可用于多个值(如列表和默认透明结构的实例)的结构相等性,并且它还与用户提供的自定义相等性配合使用。这通常是您想要在 Racket 中使用的内容。

评论

0赞 X10D 5/4/2020
可以用哪些表达方式来表达意图?能否生成树的相等函数?还可以为哪些其他数据类型生成它?
5赞 Alex Knauth 5/4/2020 #3

我只想稍微扩展一下 @Sorawee Porncharoenwase 的答案。他们提到了两种相等,即与 的参照相等和结构相等。eq?equal?

这些不同的平等概念都应该遵循反身性、对称性和传递性的基本要求。但是,将它们彼此区分开来的是它们在返回真假时给出的保证。

要记住的一些有用的相等类是引用相等、所有时间的结构相等、当前时间的结构相等和特定领域的等价。

引用相等

eq? 函数实现了引用相等性,当它返回 true 时,它有最强的保证,但当它返回 false 时,你并没有学到太多东西。

(eq? x y)意味着 和 实际上是同一个对象,并且任何对 上的操作都可以用相同的 on 替换,包括突变。有一件事有助于向我解释这一点,那就是在《球拍的境界》一书中,他说如果你剃须,那么也会被剃光,因为它是同一个物体。xyxyxy

但是,当返回 false 时,这是非常弱的酱汁。在涉及分配内存的许多数据结构上,可以仅仅因为指针不同而返回 false,即使它们是不可变的并且其他一切都相同。(eq? x y)eq?

这可以由编程语言自动提供,因为它实际上只不过是指针相等,并且不必为新数据结构生成任何新行为。

有史以来的结构平等

这种平等的概念目前并没有得到基础 Racket 或标准 Scheme 的良好支持,尽管像 Rackjure 这样的库可以提供有限的版本,比如 egal?。它在可变数据结构上实现引用相等,但在不可变数据结构上实现结构相等。

这是为了保证,如果现在返回 true,那么它在过去一直为 true,并且只要两者都存在,将来就会继续为 true。(egal? x y)xy

这可以由编程语言自动提供,只要该语言允许您指定哪些数据结构是不可变的,哪些是可变的,并强制执行不可变性。

我不确定,但 chaperone-of? 也可能是遵循“所有时间的结构平等”思想的一个例子,除了 chaperone-of? 不是对称的(幼稚的对称闭包会失去传递性)。

如果您想了解更多信息,请参阅 Pyret 中的平等类型功能对象的平等权利

当前时间的结构平等

equal? 函数实现当前时间的结构相等。这意味着,如果两个可变数据结构当前具有所有相等的组件,那么它们现在可以相等,即使它们过去不相等或将来由于突变而不相等。

这可以由编程语言自动提供,只要它始终知道数据结构中包含的所有子部分。

特定领域的等价物

例如,对于数字和数学域,您可能希望不精确的数字等同于精确整数。对于字符串搜索域,您可能希望字符串和字符不区分大小写的等效性,以便 和 等效。对于集合域,您可能希望顺序不相关,以便 和 是等价的。2.02Aa(a b)(b a)

每个域都是不同的,因此这需要在每个域上付出更多的努力。编程语言无法读懂你的心思。

评论

2赞 5/4/2020
你的最后两段是对问题的精彩总结!