haskell - Haskell 演算子の可換プロパティ?

Question

両方向に同一の定義を与える必要がないように、演算子が交換可能であることを述べる方法はありますか? 例えば：

data Nat = Zero | Succ Nat

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

ここで、これらの定義の両方を与える必要がなく、一方が他方から暗示されるような方法はありますか? それを述べる方法はありfn = flip fnますか？

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

ここでは、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

go Reverseこれで、通勤したにもかかわらず一致するものがない場合を処理する方程式を追加しないと、GHC は文句を言うようになりました。

しかし、これは多数のケースを持つ関数にのみ適していると思います。それ以外の場合は、単純にすべてを列挙する方がはるかに明確です。

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

これを修正する簡単な方法は、可換性を明示的に定義して、あなたが行った方法で加算を定義することです。