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


i need xor couple of mod numbers (from data.modular)....

let x = 4 :: integer `mod` 10     y = 6 :: integer `mod` 10  print $ x `xor` y

....but, doesn't work, because mod x y not instance of data.bits.

i can, or course, convert values integers, xor it, , convert back. or, make mod x y instance of bits hand writing class functions, ugly boilerplate code, should automated. standalonederiving extension way achieve this, doesn't seem work....

{-# language datakinds, typeoperators, typesysonyminstances, flexibleinstances, standalonederiving #-}  import data.bits import data.modular import ghc.typelits  deriving instance bits (int `mod` 10)

yields

"can't make derived instance of 'bits (mod int 10)': data constructors of 'mod' not in scope cannot derive instance it"

i not married standalonederiving, solution gives xor'able modular numbers (minus bunch of boilerplate)....

you can't implement xor modular numbers xorring underlying bits; you'll out-of-range numbers. example:

ghci> 9 `xor` 4 :: integer 13

this derived instance do, means wouldn't work anyway. sort of thing why constructor mod hidden: "is less n" invariant can maintained via smart constructors.

but situation here worse: modular numbers aren't sensible instance of bits! in general, in case this, code write instead of automatic type class instantiations uses bunch of lifting functions such as

mapmod :: (knownnat n, integral j) => (i -> j) -> `mod` n -> j `mod` n mapmod f = tomod . f . unmod  liftmod2 :: (knownnat n, integral k)          => (i -> j -> k) -> `mod` n -> j `mod` n -> k `mod` n liftmod2 f x y = tomod $ f (unmod x) (unmod y)

and implementing whole bunch of methods (.&.) = liftmod2 (.&.) , on (including xor = liftmod2 xor).

unfortunately, produces whole bunch of issues. here's not-necessarily exhaustive list. given instance bits (i `mod` n):

  1. bitsizemaybe doesn't have great definition. should number of bits takes represent n-1, consider n = 10: we'll claim have 4-bit number, seems claim there 16 possible numbers mod 10! perhaps should claim log₂ 10 = 3.32…-bit number? (this lack of integral bit size arguably root of problem.)

  2. bit needs modulus-aware, can't lifted: consider n = 10, again, bit 3 == 8 bit 4 == 0. ok, but…

  3. setbit gets weird. again, consider n = 10, , 3 = 0b0011. setbit 3 3 can't compute 0b1011 = 11; instead has work out 0b0001 = 1, has fewer bits set. last bit isn't there!

  4. complement wonky: in 4 bits, have complement 3 = complement 0b0011 = 0b1100 = 12. when working mod 10, should complement 3 = 2, complement 0b0011 = 0b0010? ugh.

  5. as reid barton said in comment, resulting xor operation isn't associative. given xorm = liftmod2 xor, have

    ghci> (9 `xorm` 4) `xorm` 3 :: integer `mod` 10 0 ghci> 9 `xorm` (4 `xorm` 3) :: integer `mod` 10 4

    bitwise or breaks (although bitwise , fine, believe). because bitwise (x)or can produce larger numbers, remainders taken, , remainder-taking not associative on bitwise operations.

the case instance does make sense, (once again) mentioned reid barton in comment, when n power of 2. have mod-based encoding of computer-style binary number, of potentially different size (128-bit? 256-bit? 1024-bit?), simple liftings work fine, , weird behavior go away, because type have whole number of bits.


-