1

我试图让中国剩余定理算法工作，所以我一直在网上寻找帮助。我试图在 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.
4

1 回答 1

4

这不是 Python。列表和元组不是同一类型。也没有关闭。

这就是错误消息告诉您的内容。 (Integer, Integer, Integer)不是列表。因此，您不能将!!运算符应用于从extGCD.

该base包不包含用于处理三元组的函数，因此我可能会将列表理解更改为[ x' | x <- ms, let (_, x', _) = extGCD x (div p x) ].

于 2014-02-25T05:00:06.173 回答