中国余数定理的Haskell实现问题

Question

所以我在试图将中国余数定理实现到Haskell中时遇到了问题。到目前为止，我有这个：

minv :: Integer -> Integer -> Integer
minv a m = let (1, x, _) = extGCD a m
           in x `mod` m

crt :: [Integer] -> [Integer] -> Integer
crt as ms = let
                    prod = product ms
                    big_m = [div prod i| i <- ms]
            in (zip as ms ((ai,mi)) ((ai * big_m * (minv mi big_m)) `mod` prod))

好吧，我知道minv函数可以工作（我已经测试过多次），但我无法让crt函数工作。所以我想做的是：

我需要将as和ms压缩列表在一起，然后将每个二进制应用于实际找到中国余数定理的方程。但我需要首先处理二进制文件，然后将`mod` prod应用于我从处理所有二进制文件中得到的整个数字。

希望这在某种程度上有意义。

提前谢谢。

Answer 1

除了用Haskell表示这一点的问题外，我在这里看到了两个与中国余数定理公式本身有关的简单数学问题：

1. 您可能想要minv big_m mi，而不是minv mi big_m
2. 你没有汇总术语表的功能。为此，您可以使用Haskell函数sum

因此，首先需要将表达式ai * big_m * (minv big_m mi)应用于列表as和ms中的每一对元素。为了清晰起见，将其单独定义为命名函数是有用的，我们称之为term:

    term ai mi = ai * big_m * (minv big_m mi)

（请注意，我不是将ai和mi放在元组中，因为我们稍后用于压缩的函数不使用它们。）

然而，您定义big_m的方式不是数字，而是列表

    big_m = [div prod i| i <- ms]

您实际需要的big_m是该列表中与ai和mi匹配的特定元素，它等于div prod mi。由于这是mi的函数，因此在term:的定义中定义它是最简单的

    term ai mi = let big_m = div prod mi
                 in ai * big_m * (minv big_m mi)

（事实上，我自己更喜欢where而不是let，但我决定使用let，因为你在问题中这样做了。）

现在您需要将函数term应用于as和ms中的所有相应元素。您可以通过将zip与map函数（类似）相结合来修复原始方法

map ((ai,mi) -> term ai mi) (zip as ms)

请注意lambda函数语法，@bhekliler指出您有错误。尽管元组在这里混淆了问题，但普通的lambda函数内部不需要括号，并且必须同时具有和->。

然而，Haskell有一个方便的函数zipWith，它可以一次性完成这两项工作（并且不需要该函数来获取元组）：

zipWith term as ms

然后，您需要使用sum来对由此构建的列表中的项求和。

sum (zipWith term as ms)

最后，您现在可以将最终的`mod` prod应用于以下内容：

sum (zipWith term as ms) `mod` prod

综合所有这些，最终的crt函数可以成为

crt :: [Integer] -> [Integer] -> Integer
crt as ms = let
                prod = product ms
                term ai mi = let big_m = div prod mi
                             in ai * big_m * (minv big_m mi)
            in sum (zipWith term as ms) `mod` prod