问题 Haskell运算符的交换属性？

有没有办法说明运算符是可交换的，所以我不必为两个方向给出相同的定义？例如：

data Nat = Zero | Succ Nat

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

在这里，有没有一种方法可以让我不必同时给出这两种定义，其中一种定义会被另一种定义？有没有办法说明这一点 fn = flip fn？

12030

2018-05-19 18:58

起源

您可以正常定义加法，并且可以免费获得（慢）交换。 - ThreeFx

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

如果你考虑到懒惰，几乎没有任何操作是完全可交换的，因为通常 f undefined x 可以不同于 f x undefined 由于模式匹配基本上是顺序的。这就是为什么很难在函数式语言的操作和指称语义之间获得完全抽象的原因：在指称语义中，你包含了函数，如parallel和etc，它们实际上不能在语言中定义。 - Bakuriu

答案:

这个加法运算符不是必需的，但通常你可以通过添加翻转参数的最终方程式来实现一个可交换的函数而不实现所有翻转的情况：

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

这里， adjacent A C 会打电话 adjacent C A，这会打电话 adjacent 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

如果你不添加，GHC会抱怨 go Reverse 方程式来处理你减刑的情况，但仍然没有匹配。

但我认为这只适用于具有大量案例的函数 - 否则，简单地枚举它们就更清楚了。

2018-05-19 22:13

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

此外，GHC非常谨慎地内联递归函数（因为它可能永远不会停止！）因此使用此技术可能会干扰编译器优化。虽然GHC当然也有可能弄清楚它是真的不递归，并最终内联，但我不确定它是如此聪明。 - dfeuer

把它作为答案：是的，如果你实施定期添加，你自动最终会进行交换操作：

(+) :: 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

解决这个问题的一个简单方法是定义添加方式，明确定义交换性。

2018-05-19 20:22

问题 Haskell运算符的交换属性？

答案:

热门问题