使用 KnownNat 算法让 GHC 接受类型签名

Question

我一直在尝试实现 Chinese Remainder Theorem, for the specific case of just two equations, using the Data.Modular 包。这个想法是我可以指定每个方程只有一个模数（x = a (mod m) 使用数字 a (mod m)）。这是我的实现。

{-# 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)

我收到以下错误：Could not deduce (KnownNat (k1 * k2)) arising from a use of ‘toMod’。但是，GHC 不应该能够计算 KnownNat (k1 * k2) 吗？此外，由于某些奇怪的原因，看起来如果我有一个 Mod 类型的构造函数而不是 toMod 函数，一切都会起作用。我也看不出这会有什么不同...

我正在寻找有助于此编译的任何修复程序，包括任何扩展。但是，如果可能的话，我希望不必制作自己的 Data.Modular 版本。（我想我可以通过直接使用 Mod 构造函数来使这项工作变得不优雅和笨拙）。

Answer 1

进行此编译的廉价、俗气的方法是添加 FlexibleContexts，然后将 KnownNat (k1 * k2) 添加到 crt 的上下文中。一旦我这样做了，我就可以在 ghci 中成功调用它：

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

享受如何将 Coprime k1 k2 表达为约束的乐趣... ;-)

使用 KnownNat 算法让 GHC 接受类型签名

Getting the GHC to accept type signature with KnownNat arithmetic

haskell

math

ghc

number-theory