这是在 Haskell 中查找毕达哥拉斯三元组的合适方法吗？

Question

我遇到这个问题，要求我找到自然数的所有毕达哥拉斯三元组，这样所有 3 个数字都是互质的，按 c 的升序排列。

我想出了这个解决方案，使用函数过滤掉倍数，然后使用列表理解。

sieve :: [Int] -> [Int]
sieve (x:xs) = filter (multiple x) xs
    where multiple a b = b `mod` a == 0


pythagoreanTriples :: [(Int, Int, Int)]
pythagoreanTriples = [(a,b,c) | c <- [1..], b <- sieve (c : [1..c]), a <- sieve (c:[1..c]), a*a + b*b == c*c]

模型答案中的答案要复杂得多，包括尝试用第一个数字找到所有 3 个数字的余数。这仍然会按预期工作吗？

Answer 1

代码永远不会返回解决方案，部分原因是

sieve

的实现方式错误。事实上，如果您希望两个项目互质，那么筛子应该保留除

1

之外不共享其他因子的所有项目。例如：

sieve :: Int -> [Int] -> [Int]
sieve x xs = filter (coprime x) xs
    where coprime x y = gcd x y == 1

然后我们可以使用：

pythagoreanTriples :: [(Int, Int, Int)]
pythagoreanTriples = [(a,b,c) | c <- [1..], let bs = sieve c [2 .. c], b <- bs, a <- sieve b bs, a*a + b*b == c*c]

但是这里的筛子可能只会增加工作量，为什么不直接使用：

pythagoreanTriples :: [(Int, Int, Int)]
pythagoreanTriples = [
  (a,b,c)
  | c <- [2..]
  , b <- [2..c-1]
  , gcd b c == 1
  , a <- [2..c-1]
  , gcd a b == 1
  , gcd a c == 1
  , a*a + b*b == c*c
  ]