中國剩餘定理的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