Haskell实现互质勾股三元组的方案是否可行？

核心结论 #

你的代码完全无法生成符合要求的三元组，且即使修正筛选逻辑，也无法正确过滤出三个数互质的勾股三元组，下面具体分析问题：

问题1：sieve函数逻辑错误 #

当前sieve函数的定义是：

sieve (x:xs) = filter (multiple x) xs
    where multiple a b = b `mod` a == 0

它的作用是保留xs中能被x整除的元素。当你在列表推导式中传入c : [1..c]时，x是c，xs是[1..c]，因此filter后只会得到[c]（只有c能被自身整除）。这意味着b和a只能取到c，此时a² + b² = 2c²，不可能等于c²（自然数c≥1），所以你的代码不会生成任何结果。

问题2：即使修正sieve，筛选逻辑仍不符合要求 #

假设你把sieve的条件改成过滤掉能被x整除的元素（将==改为/=），此时b和a会取[1..c-1]中不被c整除的数，但这和“三个数均互质”的要求毫无关系：

• 非本原三元组（如(6,8,10)，gcd(6,8,10)=2≠1）会被错误纳入：6和8都不是10的倍数，满足你的筛选条件，但不符合互质要求。
• 你的筛选条件只排除了a或b是c倍数的情况，但三个数互质的核心是三者的最大公约数为1，而非两两不整除。

正确的实现思路 #

要生成所有三个数互质的本原勾股三元组，最可靠的方法是使用欧几里得公式：
对于正整数m > n > 0，满足：

1. gcd(m, n) = 1（m和n互质）
2. m和n一奇一偶（保证生成的三元组是本原的）
   则：
   a = m² - n²，b = 2mn，c = m² + n²
   所有本原勾股三元组都可以通过该公式生成（包括调整a和b的顺序）。

修正后的Haskell代码示例 #

import Data.List (sort)

-- 生成本原勾股三元组
primitivePythagoreanTriples :: [(Int, Int, Int)]
primitivePythagoreanTriples = 
  [(a, b, c) | m <- [2..], n <- [1..m-1], 
               gcd m n == 1, 
               odd (m + n), -- 确保m和n一奇一偶
               let a = m*m - n*n,
               let b = 2*m*n,
               let c = m*m + n*n]

-- 按c的升序排列
sortedPrimitiveTriples :: [(Int, Int, Int)]
sortedPrimitiveTriples = sort primitivePythagoreanTriples

内容的提问来源于stack exchange，提问作者internationalmysteryman