Haskell 运算符的交换律？

Question

有没有一种方法可以说明一个运算符是可交换的，这样我就不必为两个方向都给出相同的定义了吗？例如：

data Nat = Zero | Succ Nat

(+) :: Nat -> Nat -> Nat
Zero + x = x
x + Zero = x
...

这里，是否有一种方法可以不必给出这两个定义中的一个，而另一个可以从中暗示出来？是否有某种方式可以说明 fn = flip fn？

- Mark Anastos

---

你可以正常定义加法，这样就会自动获得（慢速）交换性。 - ThreeFx

此外，这个问题已经有答案了这里。（它比你的用例更通用，所以你可能需要做一些研究如何使用建议的包） - ThreeFx

如果考虑到惰性计算，几乎没有任何操作是完全可交换的，因为通常 f undefined x 可能与 f x undefined 不同，这是由于模式匹配本质上是顺序执行的原因。这就是为什么在函数式语言的操作语义和指称语义之间很难获得完全抽象的原因：在指称语义中，您包括诸如并行等实际上无法在语言中定义的函数。 - Bakuriu

Answer 1

对于这个加法运算符而言并不是必需的，但是一般情况下你可以通过添加一个最终方程来翻转参数，从而使函数具有可交换性，而无需实现所有翻转的情况：

data X = A | B | C

adjacent A B = True
adjacent B C = True
adjacent A C = False
adjacent x y = adjacent y x  -- covers B A, C B, and C A

然而，缺点是如果您忘记处理一个情况，这很容易导致无限循环：

adjacent A B = True
adjacent B C = True
adjacent x y = adjacent y x

在这里，“相邻的 A C” 会调用“相邻的 C A”，然后再调用“相邻的 A C”，依此类推。 GHC 的模式匹配完整性检查（-fwarn-incomplete-patterns 或 -Wall）在这里无法帮助您。

我想您可以添加一个附加参数来防止循环：

data Commute = Forward | Reverse

adjacent = go Forward
  where
    go _ A B = True
    go _ B C = True
    go Forward x y = go Reverse y x  -- try to commute
    go Reverse _ _ = False           -- commuting failed

现在，如果您没有添加go Reverse方程来处理您已经交换但仍然没有匹配的情况，GHC将会抱怨。

但我认为这只适用于具有大量情况的函数 - 否则，直接列举所有情况会更清晰明了。

- Jon Purdy

---

完美而简单，谢谢！不知道为什么我自己没想到这个。 - Mark Anastos

此外，GHC 非常谨慎地内联递归函数（因为它可能永远不会停止！），所以使用这种技术可能会干扰编译器优化。当然，GHC 也有可能会发现它并不是真正的递归，最终会内联展开，但我不确定它是否那么聪明。 - dfeuer

Answer 2

回答是：如果您实现常规加法，那么您自动获得一个可交换的操作：

(+) :: UInt -> UInt -> UInt
Zero + x = x
(Succ s) + x = s + (Succ x)

这个操作是可交换的，虽然不是双向高效的，也就是说 "big number as UInt" + Zero 比 Zero + "big number as UInt" 花费更多时间，这是因为加法运算符是按照这种方式定义的。

ghci> :set +s
ghci> bignum + Zero
number as uint
(0.01 secs, 4,729,664 bytes) -- inefficient O(n) operation
ghci> Zero + bignum
number as uint
(0.00 secs, 0 bytes) -- instant constant operation

一个简单的解决方法是按照你所做的那样定义加法，明确地定义交换律。

- ThreeFx

---

当一个参数在某个点上是底部时，大于比较会发生什么。例如，3 >=（Succ（Succ（undefined））+ Succ Zero）。如果它是可交换的，则两种方式都应该得到未定义或真。 - codeshot

一般来说，你是正确的，但在某些（初学者或非常理论的）观点中，我们有时会忽略 undefined。在理论视角中，undefined 带来了很多复杂性，有时在一个理想化的模型中工作更容易。 - ThreeFx

为什么不做到正确而不是理想化呢？让Succ在其参数中严格一些，这样你就可以两种方式都未定义，并且它既是可交换的又是理想化的，而不是当要求是可交换的时只有理想化但不可交换。 - codeshot

通常情况下，您不希望对每个函数都强制执行严格性，因为这样会错过编译器可能能够执行的一些不错的优化（短路融合是其中一个例子，其中惰性对编译器有很大帮助）。当然，在这个玩具示例中，您也可以使其严格 - 这并不重要。 - ThreeFx

好主意，那我们把加法函数在两个参数上都设为严格模式怎么样？ - codeshot