CODEWITHSUNDEEP
haskellchinese-remainder-theorem
user3349534
user3349534

Reputation: 11

CRT implementation in Haskell

I'm trying to get the Chinese Remainder Theorem algorithm to work, so I've been trawling online looking for help. I'm trying to just get this example of the CRT in haskell to compile, but I'm getting these errors. I've implemented my own extGCD function.

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 ]

Here's the error:

 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.

Upvotes: 1

Views: 619

Answers (1)

Carl
Carl

Reputation: 27023

This isn't Python. Lists and tuples are not the same type. Nor even close.

That's what the error message is telling you. (Integer, Integer, Integer) isn't a list. So you can't apply the !! operator to the return from extGCD.

The base package doesn't include functions for working with triples, so I'd probably change the list comprehension to something like [ x' | x <- ms, let (_, x', _) = extGCD x (div p x) ].

Upvotes: 4

Related Questions