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

Question

我需要异或几个mod数字(来自Data.Modular)....

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

print $ x `xor` y

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

我当然可以将这些值转换为整数，对其进行异或，然后再转换回来。或者，我什至可以通过编写所有类函数来手动使 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)

产量

“无法创建“Bits (Mod Int 10)”的派生实例:“Mod”的数据构造函数并不全部在范围内，因此您无法为其派生实例”

我并没有与 StandaloneDeriving 结婚，我只是想要任何能够提供我的可异或模块化数字(减去一堆样板文件)的解决方案....

Answer 1

您不能仅通过对底层位进行异或来实现模数的xor；你会得到超出范围的数字。例如:

ghci> 9 `xor` 4 :: Integer
13

这就是派生实例将要做的事情，这意味着它无论如何都不会工作。这类事情就是隐藏 Mod 构造函数的原因:以便可以通过智能构造函数维护“小于 n”不变量。

但是这里的情况更糟糕:模数确实不是位的合理实例!一般来说，在类似的情况下这样，您编写的代码而不是自动类型类实例化只是使用了一堆提升函数，例如

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

1. bitSizeMaybe 并没有一个很好的定义。它可能应该是表示 n-1 所需的位数，但考虑 n = 10:那么我们会声称有一个 4 位数字，但是这似乎是在声称有 16 个可能的数字 mod 10!也许我们应该声称是一个 log2 10 = 3.32…位数字？ (缺乏整数位大小可以说是问题的根源。)

2. bit 需要具有模数感知功能，因此不能简单地提升它:再次考虑 n = 10，其中 bit 3 == 8 但位 4 == 0。这没问题，但是……

3. setBit 变得很奇怪。再次考虑 n = 10 和 3 = 0b0011。那么 setBit 3 3 不能只计算 0b1011 = 11；相反，它必须计算出0b0001 = 1，其中设置的位甚至更少。最后一点还没有完全实现!

4. 补码同样很奇怪:在四位中，我们有补码3 =补码0b0011 = 0b1100 = 12。那么，当使用 mod 10 时，是否应该对 3 = 2 进行补码，以便对 0b0011 = 0b0010 进行补码？呃。

5. As Reid Barton said in a comment ，生成的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 可以产生更大的数字，然后对其取余，而这种取余与按位运算不具有关联性。

此实例确实有意义的唯一情况，如(再次)mentioned by Reid Barton in a comment ，是当 n 是 2 的幂时。那么您本质上就会对计算机样式的二进制数进行基于 mod 的编码，只是大小可能不同(128 位？256 位？ 1024 位？)，简单的提升就可以正常工作，奇怪的行为就会消失，因为您的类型实际上具有整数位。