如何自动将 Data.Bits 添加到 Data.Modular？

Question

我需要 xor 几个 mod 号码（来自 Data.Modular）....

let x = 4 :: Integer `Mod` 10
    y = 6 :: Integer `Mod` 10

print $ x `xor` y

..但是，这不起作用，因为 Mod x y 不是 Data.Bits.

的实例

我可以，或者当然，将这些值转换为整数，对其进行异或，然后再转换回来。或者，我什至可以通过编写所有 class 函数来手动使 Mod x y 成为 Bits 的一个实例，但这都是丑陋的样板代码，应该是自动化的。 StandaloneDeriving 扩展将是实现此目的的方法，但它似乎不起作用....

{-# LANGUAGE DataKinds, TypeOperators, TypeSysonymInstances, FlexibleInstances, StandaloneDeriving #-}

import Data.Bits
import Data.Modular
import GHC.TypeLits

deriving instance Bits (Int `Mod` 10)

产量

"Can't make a derived instance of 'Bits (Mod Int 10)': The data constructors of 'Mod' are not all in scope so you cannot derive an instance for it"

我没有与 StandaloneDeriving 结婚，我只是想要任何能给我的可异或 mod 元数（减去一堆样板）的解决方案....

Answer 1

您不能仅通过异或基础位来为 mod 元数实现 xor；你会得到超出范围的数字。例如：

ghci> 9 `xor` 4 :: Integer
13

这是派生实例会做的事情，这意味着它无论如何都不会工作。这种事情就是隐藏 Mod 的构造函数的原因：以便可以通过智能构造函数维护 "is less than n" 不变量。

但这里的情况更糟：mod整数确实不是Bits的合理实例！ 通常，在这种情况下，您编写的代码而不是自动类型 class 实例化只是使用了一堆提升函数，例如

mapMod :: (KnownNat n, Integral j) => (i -> j) -> i `Mod` n -> j `Mod` n
mapMod f = toMod . f . unMod

liftMod2 :: (KnownNat n, Integral k)
         => (i -> j -> k) -> i `Mod` n -> j `Mod` n -> k `Mod` n
liftMod2 f x y = toMod $ f (unMod x) (unMod y)

然后实现一大堆方法如(.&.) = liftMod2 (.&.)等等（包括xor = liftMod2 xor）。

不幸的是，这会产生一大堆问题。这是一个不一定详尽无遗的清单。给定一个实例 Bits (i `Mod` n):

bitSizeMaybe 并没有很好的定义。它可能应该是表示 n-1 所需的位数，但请考虑 n = 10：然后我们将声称有一个 4 位数字，但这似乎声称有 16 个可能的数字mod10个！或许我们应该声称自己是一个 log2 10 = 3.32…-位数？（缺少整数位大小可以说是问题的根源。）
bit 需要 modulus-aware，所以它不能被解除：再次考虑 n = 10，其中 bit 3 == 8 但 bit 4 == 0。这样没问题，但是……
setBit 变得很奇怪。再次考虑 n = 10 和 3 = 0b0011。那么 setBit 3 3 不能只计算 0b1011 = 11；相反，它必须计算出 0b0001 = 1，它甚至设置了 更少的 位。最后一点不完整！
complement 同样不稳定：在四位中，我们有 complement 3 = complement 0b0011 = 0b1100 = 12。那么当工作mod10时，应该complement 3 = 2，以便complement 0b0011 = 0b0010？呃
，结果 xor 操作不是关联的。给定 xorM = liftMod2 xor，我们有
```
ghci> (9 `xorM` 4) `xorM` 3 :: Integer `Mod` 10
0
ghci> 9 `xorM` (4 `xorM` 3) :: Integer `Mod` 10
4
```
按位或类似的中断（尽管按位和很好，我相信）。这是因为按位 (x)or 可以产生更大的数字，然后取余数，并且这种取余与按位运算没有关联。

此实例确实有意义的唯一情况，如（再次），是当 n 是 2 的幂时。然后您基本上会有一个基于 mod 的计算机式二进制数编码，只是大小可能不同（128 位？256 位？1024 位？），简单的提升就可以正常工作，并且奇怪的行为会消失，因为你的类型真的有整数位。

如何自动将 Data.Bits 添加到 Data.Modular？

How do I add Data.Bits to Data.Modular, automatically?

polymorphism

haskell

ghc