Haskell实现generateExponents：生成有序唯一x^k*y^l流的问题

我们需要实现Haskell函数generateExponents k l，功能是生成按升序排列的所有唯一数值x^k * y^l的无限流，例如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)

两种写法的问题解析 #

第一种写法的核心问题：无限列表的排序无法终止 #

Haskell的[1..]是惰性求值的无限列表，列表推导式[x^k*y^l | x <- [1..], y <- [1..]]会先遍历完所有x=1的情况（生成1^k*y^l即y^l的无限序列），永远不会推进到x>1的取值。更关键的是，sort函数需要遍历整个列表才能完成排序，但这个列表是无限的，程序会直接陷入死循环，永远输出不了任何结果。

第二种写法的问题：效率低下+重复输出 #

1. 重复计算导致效率极低：对于每个自然数n，你都要重新生成xs n、ys n，再计算所有乘积组合，最后检查n是否在其中。随着n增大，计算量会指数级增长，且大量乘积组合会被重复计算多次。
2. 无法保证数值唯一性：比如数值64可以表示为8^2*1^3、4^2*2^3、2^2*4^3甚至1^2*8^3，你的写法会把64多次加入结果列表，不符合“唯一数值”的要求。
3. 虽然这种写法能输出升序序列（因为n是从1开始递增的），但本质是逐个试错，完全没有利用x^k*y^l的生成规律，性能极差。

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