CODEWITHSUNDEEP
haskellmathghcnumber-theory
Alec
Alec

Reputation: 32309

Getting the GHC to accept type signature with KnownNat arithmetic

I have been trying to implement the Chinese Remainder Theorem, for the specific case of just two equations, using the Data.Modular package. The idea is that I can specify each equation with only one modular number (x = a (mod m) using the number a (mod m)). Here is my implementation.

{-# LANGUAGE DataKinds, ScopedTypeVariables, TypeOperators #-}

import GHC.TypeLits
import Data.Proxy (Proxy (..))
import Data.Modular

crt :: forall k1 k2 i. (KnownNat k1, KnownNat k2, Integral i) => i `Mod` k1 -> i `Mod` k2 -> i `Mod` (k1 * k2)
crt a1 a2 = toMod $ (unMod a1)*n2*(unMod n2') + (unMod a2)*n1*(unMod n1')
  where n1 = getModulus a1 :: i
        n2 = getModulus a2 :: i
        n2' = inv $ (toMod n2 :: i `Mod` k1)
        n1' = inv $ (toMod n1 :: i `Mod` k2)

        getModulus :: forall n i j. (Integral i, Integral j, KnownNat n) => i `Mod` n -> j
        getModulus x = fromInteger $ natVal (Proxy :: Proxy n)

I get the following error: Could not deduce (KnownNat (k1 * k2)) arising from a use of ‘toMod’. However, shouldn't GHC be able to do the arithmetic for KnownNat (k1 * k2)? Also, for some weird reason, it looks like if I had a constructor for the Mod type instead of the toMod function, everything would work. I fail to see how that should make a difference either...

I am looking for any fix to help this compile, including whatever extensions. I would, however, like to not have to make my own version of Data.Modular if possible. (I think I could make this work inelegantly and clumsily by using the Mod constructor directly).

Upvotes: 3

Views: 269

Answers (1)

Daniel Wagner
Daniel Wagner

Reputation: 152707

The cheap, cheesy way to make this compile is to add FlexibleContexts, then add KnownNat (k1 * k2) to the context of crt. Once I did this, I could successfully call it in ghci:

> crt (3 :: Mod Integer 5) (5 :: Mod Integer 7)
33

Have fun working out how to express Coprime k1 k2 as a constraint... ;-)

Upvotes: 2

Related Questions