中国剩余定理的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

从表达这是哈斯克尔您的问题

除此之外，我在这里看到有关中国剩余定理公式本身这两个滑动的数学问题：

1. 你可能想minv big_m mi，不minv mi big_m。
2. 您无法总结术语列表。为此，您可以使用Haskell功能sum。

所以，你首先要拿到名单as和ms施加到每对元素的表达ai * big_m * (minv big_m mi)。

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

（注意我不把ai和mi在一个元组，我们将使用压缩功能：为清楚起见，将其定义为本身就是一个命名功能，我们称之为term它是有用的以后不会使用它们。）

但是，您已经定义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。你可以通过与map功能结合zip，像

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

注意lambda函数的语法，这@bheklilr指出，你有错的解决您的原始方法。尽管这里的元组混淆了一些问题，但一个普通的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