Haskell-列表理解不能枚举N×N

Question

我必须写一个函数，它返回所有对(x,y)的列表，其中x，y∈N， 和:

• x是两个自然数(x = a•b，其中a, b∈N) 与
的乘积。
• x大于5但小于500，和
• y是平方数(y = c²其中c∈N)小于1000，和
• x是y的因数。

我尝试

:

listPairs :: [(Int, Int)] 
listPairs = [(a*b, y) | y <- [0..], a <- [0..], b <- [0..], 
                        (a*b) > 5, (a*b) < 500, (y*y) < 1001, 
                        mod y (a*b) == 0]

但是它不返回任何东西，而且计算机在它上面工作了很多。

然而，如果我为a, b和y选择一个较小的范围，例如[0..400]，它需要一分钟，但它返回正确的结果。

那么我如何解决性能问题呢?

Answer 1

因此，无限列表上嵌套的列表推导当然不会终止。

幸运的是，你的列表不是无限的。这是有限度的。如果是x = a*b < 500，那么我们知道它一定是a < 500和b < 500。同样，c = y*y < 1001就是y < 32。

listPairs :: [(Int, Int)] 
listPairs = 
    [(x, c*c) | c <- [1..31], a <- [1..499],    -- a*b < 500 ==> b<500/a ,
                b <- [a..min 499 (div 500 a)],  -- a*b==b*a  ==> b >= a
                let x = a*b, x > 5,  
                -- (a*b) < 500, (c*c) < 1001,   -- no need to test this
                rem (c*c) x == 0]    

mod 0 n == 0通常成立，所以我在这里从"自然数"中排除了0。

尽管我们在x=a*b中将b的值限制为b >= a，因为x可以有多种表示(例如1*6 == 2*3)，这里仍然会产生一些重复的值。

您可以使用Data.List.nub来删除它们