Внедрение CRT в Haskell

Question

Я пытаюсь заставить работать алгоритм китайской теоремы остатка, поэтому я бродил по интернету в поисках помощи. Я пытаюсь просто скомпилировать этот пример CRT в haskell, но я получаю эти ошибки. Я реализовал свой собственный 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

Это не Питон. Списки и кортежи не одного типа. Ни близко.

Это то, что сообщение об ошибке говорит вам. (Integer, Integer, Integer) это не список Таким образом, вы не можете применить !! оператор к возвращению из extGCD,

base Пакет не включает в себя функции для работы с тройками, поэтому я, вероятно, изменил бы понимание списка на что-то вроде [ x' | x <- ms, let (_, x', _) = extGCD x (div p x) ],