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

Question

我需要xor几个国防部号码(从Data.Modular).

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

print $ x `xor` y

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

我可以，或者当然，将值转换为整数，xor，然后再转换回来。或者，我甚至可以通过编写所有的类函数使Mod x y成为一个位实例，但是这都是丑陋的样板代码，应该是自动化的。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结婚，我只是想要任何给出我的xor‘可模数(减去一串样板)的解决方案.

Answer 1

您不能仅仅通过对底层位进行xorring来实现模块数字的xor；您将得到超出范围的数字。例如：

ghci> 9 `xor` 4 :: Integer
13

这就是派生实例所要做的，这意味着它无论如何都不能工作。这就是为什么Mod的构造函数是隐藏的:这样就可以通过智能构造函数来维护“小于n”的不变量。

但是这里的情况更糟:模数实际上不是，这是Bits__的一个明智的例子！通常，在这种情况下，您编写的代码而不是自动类型类实例化只使用一些提升函数，如

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！也许我们应该声明为日志₂10 = 3.32…-bit号码？(缺少一个完整的位大小可以说是问题的根源。)
2. bit需要具有模数感知能力，所以它不能仅仅被提升:再一次考虑n = 10，其中bit 3 == 8但是bit 4 == 0。这是可以的，但是…
3. setBit变得很奇怪。再一次，考虑一下n = 10和3 = 0b0011。然后，setBit 3 3不能只计算0b1011 = 11；相反，它必须计算到设置了更少位的0b0001 = 1。最后一点还没有完全到位！
4. complement也同样不稳定:在四位中，我们有complement 3 = complement 0b0011 = 0b1100 = 12。那么当工作模式10，应该complement 3 = 2，所以complement 0b0011 = 0b0010？呃。
5. As Reid Barton said in a comment，生成的xor操作不是关联的。考虑到xorM = liftMod2 xor，我们 ghci> (9 xorM 4) xorM 3 :：整数Mod 10 0 ghci> 9 xorM (4 xorM 3) :：整数Mod 10 4 按位或类似的断路(虽然按位排列，但我相信是好的)。这是因为按位(X)或可以产生更大的数字，其馀数随后被取走，而这种余数取则不是位运算的联合运算。

这个实例确实有意义的唯一例子，就像(再次) mentioned by Reid Barton in a comment一样，是当n是2的幂的时候，那么你基本上就会有一个基于模式的计算机式二进制数字的编码，只是一个可能不同的大小(128位?256位?1024位？)，简单的提升会很好，而奇怪的行为也会消失，因为你的类型真的会有一个完整的位数。