function - 在 Haskell 中为给定的 `x^k*y^l` 和 `k` 生成所有可能数字 `l` 的流

Question

Generate the function generateExponents k l, which for given k and l generates a stream of all unique possible numbers x^k*y^l in increasing order. For example generateExponents 2 3 = [1,4,8,9,16,25,27...]

出于明显的原因，这不起作用:

generateExponents k l = sort [x^k*y^l | x <- [1..], y <- [1..]]

然后我尝试了这个，但也不起作用:

generateExponents k l = [n | n <- [1 ..], n `elem` products n]
  where
    xs n = takeWhile (\x -> x ^ k <= n) [1 ..]
    ys n = takeWhile (\y -> y ^ l <= n) [1 ..]
    products n = liftA2 (*) (xs n) (ys n)

我做错了什么？

Answer 1

你的算法非常慢——它检查每个数字，并为每个数字搜索适当的因式分解!您可以通过生成无限的答案表，然后适当折叠该表来做得更好。例如，对于 x^2*y^3，表格如下所示:

 x  1    2    3    4    5
y
1   1    4    9   16   25
2   8   32   72  128  200
3  27  108  243  432  675
4  64  256  576 1024 1600
5 125  500 1125 2000 3125

请注意此表的两个很好的功能:每行都已排序，并且行本身也已排序。这意味着我们可以通过简单地获取左上角的值，然后将第一行的尾部重新插入到新的排序位置来有效地合并它们。例如，上表在发出 1 后将如下所示:

  4    9   16   25   36
  8   32   72  128  200
 27  108  243  432  675
 64  256  576 1024 1600
125  500 1125 2000 3125

然后，在发出左上角值 4 后:

  8   32   72  128  200
  9   16   25   36   49
 27  108  243  432  675
 64  256  576 1024 1600
125  500 1125 2000 3125

请注意顶行现在如何成为第二行以保留双重排序属性。

这是按正确顺序构造所有正确数字的有效方法。然后，剩下的唯一需要的技巧是重复数据删除，为此您可以部署标准技巧 map head 。 group，因为重复项保证彼此相邻。完整代码如下:

import Data.List

generateExponents' k l = map head . group . go $ [[x^k*y^l | x <- [1..]] | y <- [1..]] where
    go ((x:xs):xss) = x:go (insert xs xss)

速度快得多。比较:

> sum . take 400 $ generateExponents 2 3
5994260
(8.26 secs, 23,596,249,112 bytes)
> sum . take 400 $ generateExponents' 2 3
5994260
(0.01 secs, 1,172,864 bytes)
> sum . take 1000000 {- a million -} $ generateExponents' 2 3
72001360441854395
(6.99 secs, 13,460,753,616 bytes)