有哪些方便的 Haskell 概念可以生成 2^m*3^n*5^l 形式的数字

Question

我正在尝试生成 2^m*3^n*5^l 形式的数字，其中 m、n 和 l 是包括 0 的自然数。

顺序如下： 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, ......

我正在通过获取百万分之一的数字来测试它。我使用列表理解和排序来实现它，但是花费的时间太长。我想要一个更快的解决方案。我花了好几天的时间尝试这样做，但没有成功。

我不想要一个完整的解决方案。我只是想知道实现它需要哪些 Haskell 概念。

Answer 1

这是一种不需要任何 Haskell 概念，只需要一些数学和计算机科学的方法。

获取一个提供优先级队列的库。

初始化一个仅包含数字 1 的优先级队列。

无限循环以下操作：从队列中提取最小值。将其放在输出列表中的下一个。将该数字乘以 2、3 和 5 作为三个单独的条目插入队列中。确保队列插入函数合并重复项，因为由于乘法的交换性，将会有很多重复项。

如果您已达到最大值，则可以使用它来修剪队列中的插入作为较小的优化。或者，您可以利用实际的 Haskell 属性，并使用惰性返回一个无限列表。

Answer 2

首先，编写一个类型的函数Int -> Bool，该函数确定给定的整数是否在您定义的序列中。它会尽可能多次地将数字除以 2（不创建分数），然后尽可能多次除以 3，最后尽可能多次除以 5。毕竟，如果数字大于 1，则无法将其表示为二、三和五的乘积，因此该函数将返回 false。否则，该数字在您的序列中，因此该函数返回 true。

然后取大于0的整数的无限序列，并使用上面的函数过滤掉所有不在序列中的数字。