Haskell中的CRT實現

Question

我試圖讓中國剩餘定理算法運行起來，所以我一直在網上尋找幫助。我試圖在haskell中得到這個CRT的例子來編譯，但是我收到了這些錯誤。我已經實現了我自己的extGCD函數。

extGCD :: Integer -> Integer -> (Integer, Integer, Integer) 
extGCD a 0 = (a, 1, 0) 
extGCD a b = let (q, r) = divMod a b 
      (d, m, n) = extGCD b r 
     in (d, n, m - n*q) 

crt :: [Integer] -> [Integer] -> Integer 
crt as ms = let {p = product ms 
      ;ls = [extGCD x (div p x) !! 1 |x<- ms] 
     }in sum [ div (x*y*p) z | (x,y,z)<- zip3 as ls ms ] 

這裏的錯誤：

Couldn't match expected type `[t0]' 
      with actual type `(Integer, Integer, Integer)' 
    In the return type of a call of `extGCD' 
    In the first argument of `(!!)', namely `extGCD x (div p x)' 
    In the expression: extGCD x (div p x) !! 1 
Failed, modules loaded: none. 

Answer 1

這不是Python的。列表和元組不是相同的類型。也不甚密切。

這就是錯誤信息告訴你的。 (Integer, Integer, Integer)不是一個清單。因此，您不能將!!運營商應用於extGCD的回報。

base軟件包不包含使用三元組的函數，所以我可能會將列表理解改爲[ x' | x <- ms, let (_, x', _) = extGCD x (div p x) ]之類的東西。