生成所有可能的互质的排序列表

我需要生成所有互质的无限排序列表。 每对中的第一个元素必须小于第二个元素。 排序必须按升序进行——按对元素的总和；如果两个总和相等，则除以该对的第一个元素。

因此，结果列表必须是

[(2,3),(2,5),(3,4),(3,5),(2,7),(4,5),(3,7),(2,9),(3,8),(4,7)...`

这是我的解决方案。

coprimes :: [(Int, Int)]
coprimes = sortBy (\t1 t2 -> if uncurry (+) t1 <= uncurry (+) t2 then LT else GT) $ helper [2..]
    where helper xs = [(x,y) | x <- xs, y <- xs, x < y, gcd x y == 1]

问题是我不能接受n第一对。我意识到排序不能在无限列表上完成。

但是我怎样才能以惰性的方式生成相同的序列呢？

虽然可能不是最好的方法，但如果您首先生成所有可能的对然后过滤它们，它应该会起作用。

所以使用你的标准：

pairs :: [(Integer,Integer)]
pairs = [ (i,l-i) | l <- [1..], i <- [1..l-1] ]

coprimes :: [(Integer,Integer)]
coprimes = [ (i,j) | (i,j) <- pairs, 1 < i, i < j,gcd i j == 1]

产生

λ> take 10 coprimes
[(2,3),(2,5),(3,4),(3,5),(2,7),(4,5),(3,7),(2,9),(3,8),(4,7)]

现在当然你可以放一些东西1 < i and i < j浮现在脑海中pairs定义甚至加入他们，但我认为这里发生的事情更明显